HDTenEightyP/NetNews huggingface dataset:
From: schneier@chinet.chi.il.us (Bruce Schneier)
Subject: Re: More RSA questions
Organization: Chinet - Public Access UNIX
Date: Sun, 20 Dec 1992 05:55:47 GMT

In article <AfATsxL0Bwx2F93KFX@transarc.com> Pat_Barron@transarc.com writes:
>I was tinkering around with the RSA algorithm last night, using really
>small primes (e.g., 13 and 17) to generate keys.  The idea was that I
>only wanted to use a 16-bit modulus, so I could avoid doing any
>extended precision arithmetic, and so I could do the exponentation via
>a naive "compute x^y by looping and multiplying by x, y times
>(remember, this is just a toy implementation, and it's not intended
>to do any "real" work).  But I ran into a few snags:
>
>1)  During the exponentiation, the numbers get *really* big.  Like, I
>was shocked at how quickly they got big.  Is there any shortcut for
>computing m^e mod n, without actually computing m^e first?  Like, can
>I loop somehow, accumulating partial results, until at the end I have
>the value m^e mod n, without having actually computed m^e first?  Even
>if I choose, say, 3 or 5 as the private key, the public exponent tends
>to be big enough that m^e is way beyond the capacity of a 32-bit
>unsigned integer.
>
Take the modulus after each multiplication, not once after you are finished
with all the multiplications i the exponentiation.

>2)  I chose the private key and public exponent by brute force.  Is
>a better way to choose the private key than to factor (p-1)(q-1) and
>choose something with no common factors?  Is there a better way to
>find the public exponent than just trying all the possible values
>until you find it (which is what I did)?
>
Use Euclid's algorithm; it's easy.

I have a suggestion.  I wrote an article in the May 92 issue of Dr. Dobbs
Journal about public-key cryptography.  It discusses how to do RSA.  There's
one realy irritating typo in the second column of page 26, but other than
that the article gives a good description of how RsA works.

Bruce

Xref: sparky sci.crypt:5695 alt.security.pgp:183
From: vince@ghost.dsi.unimi.it (David Vincenzetti)
Subject: sci.crypt archive
Organization: Computer Science Dep. - Milan University
Date: Fri, 18 Dec 1992 23:11:02 GMT

I'm archiving the articles from this newsgroup.

Directory: ftp@ghost.dsi.unimi.it:/pub/crypt/sci.crypt

Regards,
David
-- 
David Vincenzetti, system administrator
Department of Computer Science,         Email: vince@ghost.dsi.unimi.it
via Comelico 41, 20135 Milan, ITALY     Phone: ++39 2 55006 39{1,2}
$PUBLIC KEY available by finger(1)$     Fax  : ++39 2 55006 373
Newsgroups: sci.crypt
Subject: Re: PKP/RSA comments on PGP legality
From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
Date: 17 Dec 92 18:15:08 GMT
 <1992Dec17.002347.19216@netcom.com> <MOORE.92Dec16192825@defmacro.cs.utah.edu> <1992Dec17.031421.15578@qualcomm.com>
Organization: Beckman Instruments, Inc.

In <1992Dec17.031421.15578@qualcomm.com> karn@servo.qualcomm.com (Phil Karn) writes:

>A part of the ITARs not quoted by PKP exempts from control any
>"technical data" that is in the public domain, with "public domain"
>having a broader meaning than the same term as used in copyright law.
>Here it refers to anything that is freely and widely available to the
>public in libraries, magazines, books, etc, as opposed to proprietary
>information available only under non-disclosure agreement.  So
>"technical data" published in, say, Aviation Week can be exported
>anywhere in the world, regardless of what it relates to. It also means
>that you can export articles and books describing DES or RSA.

>Now the question arises, is software "technical data" that would be
>subject to the public domain exemption? Some have claimed it is, which
>would make any public domain crypto code freely exportable (even as a
>proprietary implementation of the same algorithms would require an
>export license). But other legal interpretations of the ITARs claim
>that software is a "defense article", not "technical data", and the
>public domain exemptions apply only to the latter. By this theory you
>can't export even a widely available public domain encryption package.

Does anyone (the law, the regulations, a court case?) define "software" to
specifically include source code?  If not, one could make a good case that
well-documented source code more closely resembles "technical data" than
"software".  (Even if so, as you point out later, the law/regulations are
absurd, but, if not, there is no need to go further...the law doesn't apply
to the source code of a cryptographic program.)

For that matter, have there been any court cases related to ITAR and
software.

--
Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
My opinions are my own, and do not represent those of my employer.
My interaction with our news system is unstable; please mail anything important.
From: zeke@fasttech.com (Bohdan Tashchuk)
Newsgroups: sci.crypt
Subject: Re: Spies using PGP
Date: 14 Dec 92 05:43:04 GMT
Article-I.D.: fasttech.1992Dec14.054304.1311
Organization: Fast Technology

In <hmiller.724028396@lucpul.it.luc.edu> hmiller@lucpul.it.luc.edu (Hugh Miller) writes:

>>>    Other interesting note.  He spoke with the FBI  about the matter and
>>>    they indicated that they have also run into PGP. Once case involving
>>>    espionage.

>>In hindsight, I guess this is quite obvious.

>>If he sticks to PGP, which is in relatively widespread use, what's on his
>>laptop is much less incriminating than if he had a custom encrypt/decrypt
>>application.

>    I do not find this story obvious at all.  Unless we are talking about
>Burkina Fasso or Sudan, I doubt that any country would trust its diplomatic or
>intelligence traffic to a product like PGP.  Real intelligence and diplomatic
>services have had practically secure computer crypto for quite a while now.
>If most American corporations won't let their employees use software that
>hasn't been vetted by the folks in their MIS department, I can't imagine that
>an intelligence agent of a decent government would be permitted to wing it
>with PGP.

>    It would not be above some folks at State or the FBI to circulate such a
>rumor.  Absent any specifics, which you are not going to get, consider this
>story nothing but the usual _desinformatsiya_.

>    _Industrial_ espionage, now -- that's a real possibility.

It's important for a spy to not be obvious. A custom crypto program is more
obvious than one in "widespread" use. Mailing to boris@kremvax.Xussr is more
obvious than posting GIFs (as someone else suggested). You didn't comment on
this aspect. For a fictitious example, The Cardinal of the Kremlin disguised
his messages as diary entries. That way he could plausibly deny that they
were anything more than diary entries.

We (readers of sci.crypt) have a belief that PGP is secure because we believe
that very large numbers are "impossible" to factor, and that IDEA is difficult
to break given frequent key changes. Perhaps the NSA and its counterparts have
reached the same conclusions. In that case, it would be quite reasonable to
have lower level spies (perhaps only industrial ones as you suggest) use PGP.

I'm not really a student of bureaucracy but I'll suggest that Not Invented
Here would be a bigger obstacle keeping an agency from adopting PGP than any
weaknesses in it. There is a general consensus that real spooks disparage the
use of factoring based cryptosystems, but perhaps *that* is disinformation.
Newsgroups: sci.crypt
From: phr@telebit.com (Paul Rubin)
Subject: Re: RSA questions
Organization: Telebit Corporation; Sunnyvale, CA, USA
Date: 14 Dec 92 20:28:39

    I read the article in popular mechanics and have a few questions
    about how RSA works.  You take the ASCII value of the number,
    raise it to an arbitrary high power, and mod it by the public key,
    correct?  But how do you decrypt it?

The message "x" is just a number, not an ascii value.

RSA works like this:
1. Pick two large primes p and q (with certain extra properties). Let N=pq.
2. Pick random exponent s.  The pair (N, s) will be the public key.
3. Compute secret key t, so that st = 1 mod (p-1)(q-1).  You can do
   this efficiently if you know p and q, but it is intractable otherwise.
4. To encrypt: E(x) = x^s mod N.
5. To decrypt: D(y) = y^t mod N.

From number theory, it turns out that x^st mod N is just x.
(This is because st = 1 mod phi(N), where phi(N) is the Euler
totient function, equal to (p-1)(q-1) when N=pq.)

Thus, D(E(x)) = x.
Newsgroups: sci.crypt
From: smb@research.att.com (Steven Bellovin)
Subject: Re: Status of DES, or "Is the DES Standard PD?"
Date: Thu, 17 Dec 1992 00:37:01 GMT
Organization: AT&T Bell Laboratories

In article <1992Dec16.161414.22709@guinness.idbsu.edu>, betz@gozer.idbsu.edu (Andrew Betz) writes:
> i would agree.  if the government "pushes" a particular encryption
> scheme, it's probably because they're able to crack it.

Remember that at the time, there were two competing interests, even
in the government.  Sure, part of NSA wanted to be able to read DES.
But another part really wanted to guard commercial American communications
from the Soviets -- remember those microwave antennas on top of their
embassy?  (The balance seems to have shifted, with things like civilian-
grade STU-IIIs in sealed boxes being pushed.)

> seems like i 
> remember reading somewhere that one of the criticisms of DES is
> that nobody's quite sure where the S-boxes came from...furthermore,
> they're non-random, leaving a possible trapdoor somewhere.

We now know -- they were designed by IBM, not NSA, to resist
differential cryptanalysis.
Newsgroups: sci.crypt,alt.society.civil-liberty
From: karl@ddsw1.mcs.com (Karl Denninger)
Subject: Re: Limits on the Use of Cryptography?
Date: Mon, 14 Dec 1992 01:59:20 GMT
Organization: MCSNet, Chicago, IL

In article <1992Dec10.182022.9173@netcom.com> strnlght@netcom.com (David Sternlight) writes:
>
>Iain McCord raises the possibiity that the police will "plant" an
>encrypted file, or worse, plant an incriminating encrypted file of 
>their own design.
>
>This is not a cryptographic issue. They could do the same with any
>other kind of evidence. One's protections against this are also
>the same, including the ability to challenge the 'chain of evidence'
>in court, the ability to introduce contrary evidence, etc.
>
>David

Oh, but it IS a cryptographic issue.

With a public key system you can be ABSOLUTELY certain that a particular
ciphertext was created with one key if you can decode it with the other.
Therefore, if the keys are not compromised you can, with certainty,
prove whether or not it was written by the individual in question.

--
Karl Denninger (karl@ddsw1.MCS.COM, <well-connected>!ddsw1!karl)
Data Line: [+1 312 248-0900] Anon. arch. (nuucp) 00:00-06:00 C[SD]T
Request file: /u/public/sources/DIRECTORY/README for instructions
Newsgroups: sci.crypt,alt.security.pgp
From: vancleef@ohstpy.mps.ohio-state.edu
Newsgroups: sci.crypt
Subject: PGP is dope
Date: 19 Dec 92 01:39:02 EST
Organization: The Ohio State University, Department of Physics

My guess would be that using PGP is similar to smoking pot.

-Garrett



Newsgroups: sci.crypt
From: robert.heuman@rose.com (robert heuman)
Subject: PGP as a World Standa
Organization: Rose Media Inc, Toronto, Ontario.
Date: Sat, 19 Dec 1992 03:58:44 GMT
X-Gated-By: Usenet <==> RoseMail Gateway (v1.70)


Date Entered: 12-18-92 22:51
moore@cs.utah.edu (Tim Moore) writes:

M(> The IDEA cipher is patented in Switzerland.  I admit that I don't 
know
M(> if Switzerland is considered part of the EC or not.

Answer: Switzerland has chosen to stay out of the EEC. 

Bob Heuman <robert.heuman@rose.com>
---
   RoseReader 1.70 P001886: This Canadian has an Opinion...His Own!
   RM 2.00 : RoseNet<=>Usenet Gateway : Rose Media 416-733-2285
From: woody@cs.utexas.edu (James Woodgate)
Newsgroups: sci.crypt,alt.security.pgp
Subject: Re: PKP/RSA comments on PGP legality
Date: 15 Dec 1992 15:52:31 -0600
Organization: CS Dept, University of Texas at Austin
NNTP-Posting-Host: cash.cs.utexas.edu

In article <1galtnINNhn5@transfer.stratus.com> cme@ellisun.sw.stratus.com (Carl Ellison) writes:
[stuff deleted]
>
>NOTE: The pgp documentation states that PKP acquired the patent rights
>to RSA "... which was developed with your tax dollars..." This is very
>misleading.  U.S. tax dollars only partially funded researchers at MIT
>who developed RSA. The U.S. government itself received royalty-free
>use in return.  This is standard practice whenever the government
>provides financial assistance.  The patents on public-key are no
>different and were handled no differently than any others developed at
>universities with partial government funding. In fact, almost every
>patent granted to a major university includes government support,
>returns royalty-free rights to the government, and is then licensed
>commercially by the universities to private parties.
>

So taxpayers pay for research, if it doesn't amount to anything, they
just lose the money.  If it does amount to anything, they get to pay
twice, once for the research, and then again when someone gets an 
exclusive patent by the University and charges licensing fees.  

If the government gets royalty-free use, then so should the people
who put up the money in the first place, US taxpayers...

BTW-The January issue of Popular Science has an article on encryption
    It states: "The computer industry would like NIST to
    adopt the RSA technology, but that isn't likely to happen.  One
    reason:  If the privately developed technology becomes a standard,
    the government will have to pay royalties for its use."



-- 
-----------------------------------------------------------------
  Linux Rules!                              woody@cs.utexas.edu
		           pgp key available -> finger woody@cs
-----------------------------------------------------------------
Newsgroups: sci.crypt
From: jac54@cas.org ()
Subject: Re: Chosen crypto-text attack on RSAREFRESH
Organization: Chemical Abstracts Service, Columbus, Ohio
Date: Wed, 16 Dec 1992 17:54:44 GMT

In article <1992Dec11.195931.8855@netcom.com> strnlght@netcom.com (David Sternlight) writes:
>
>Perhaps someone who knows and is not in the U.K. might like to summarize
>or quote the offending material in "Spycatcher" that caused the ban
>in Britain.
>
>If so, perhaps they'd like to do so by starting another topic, os
>U.K. readers don't inadvertently import that material.
>
>If a reader who knows thinks the matter won't be of general interest,
>or thinks posting it might create an opportunity for U.K. authorities
>to interfere with the net, and would like to e-mail it to me (I'm
>in the U.S. where the book is both published and legal), that
>would be fine, too.
>
	There really isn't anything in "Spycatcher" that wasn't
	fed to Chapman Pincher for his books "Their Trade is Treachery"
	and "Too Secret too Long".  Read those two and you'll have
	everything except Peter Wrights name and his complaints about
	his pension.  There was a posting on soc.culture.british a
	couple of days ago saying that the ban had been lifted.  In that
	case, I would guess the government hasn't told anybody.

	Alec Chambers
Newsgroups: sci.crypt
Subject: Re: PKP/RSA comments on PGP legality
From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
Date: 17 Dec 92 17:50:38 GMT
 <MOORE.92Dec16192825@defmacro.cs.utah.edu> <1992Dec17.031421.15578@qualcomm.com> <1992Dec17.094354.19214@netcom.com>
Organization: Beckman Instruments, Inc.

In <1992Dec17.094354.19214@netcom.com> strnlght@netcom.com (David Sternlight) writes:


>In response to Phil Karn, cryptographic software is specifically
>defined as matter that's not exportable or importable without a
>license. It is NOT the same thing as an algorithm, in the
>specific language of the regulations.

Ah, but _source code_ is, in fact, technical data.  Unless the regulations
specifically (not solely by reference to "software") define it otherwise.
--
Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
My opinions are my own, and do not represent those of my employer.
My interaction with our news system is unstable; please mail anything important.
From: mrr@cl.msu.edu (Mark Riordan)
Newsgroups: sci.crypt
Subject: Re: alt.privacy
Date: 20 Dec 92 23:34:57 GMT
Distribution: na
Organization: Michigan State University
NNTP-Posting-Host: scss3.cl.msu.edu
X-Newsreader: TIN [version 1.1 PL6]

In article <1992Dec20.180814.18991@dogface.austin.tx.us> Bob wrote:
: 	I'd like to read the applicable U.S. regulations on export of crypto-
: graphic software.  Have they been put up for ftp anywhere?  If not, pointers
: to which government agency to call would be good.

Bob (also posted to net):

This isn't exactly what you asked for, but the May/June 92 issue
of INFOSecurity Product News has an article entitled
"The rules for exporting encryption software".  It's written
by a lawyer and an export consultant, and is as in-depth as
you're likely to find in a magazine article anywhere.

Mark R.
From: leonard@qiclab.scn.rain.com (Leonard Erickson)
Newsgroups: sci.crypt
Subject: Re: GWBASIC Encryption
Date: 19 Dec 92 12:19:58 GMT
Article-I.D.: qiclab.1992Dec19.121958.13079
Reply-To: Leonard.Erickson@f51.n105.z1.fidonet.org
Organization: SCN Research/Qic Laboratories of Tigard, Oregon.

frasertw@newton.ccs.tuns.ca (Terrance W Fraser) writes:

>kocherp@leland.Stanford.EDU (Paul Carl Kocher) writes:

>>In article <1992Dec8.022439.24913@newton.ccs.tuns.ca> frasertw@newton.ccs.tuns.ca (Terrance W Fraser) writes:
>>>Does anyone know what GWBASIC for msdos uses to 'encrypt' a program

>>It's a substitution cipher with period 143, probably meaning that there
>>is an 11-byte key and a 13-byte key that get xored/added/etc in some
>>combintation, though after a ten-minute look at it wasn't immediately
>>obvious what steps were used.  It also looks possible that the plaintext
>>might be multiplied by an odd number as part of the encryption.

>I played with it for a while. Your right about the 143 byte period. It
>appears that
>  1) each byte gets encypted separately.
>  2) it's not self-reversing.
>  3) the substitution table changes from byte to byte but repeats
>     every 143 bytes.
>Probably the easiest thing to do is find the code that does it, but
>BASIC is a *big* program.

>Anyone know of one of those PC books that goes into this?

The "back door" approach is *much* faster. You create a short binary file.
(I'd have to look up the exact contents, but it's something like 3 bytes
long). You name it UNPROT.BAS.

Then you load *any* "protected" BASIC file. It won't be LISTable nor can you
SAVE it. 

Now load UNPROT.BAS. 

Voila! You can now LIST the file, or SAVE it or whatever.

UNPROT is the "header" for an *unprotected* BASIC program. But there's
no program attached. BASIC cheerfully loads it into RAM over the header
for the current program....


-- 
Leonard Erickson		      leonard@qiclab.scn.rain.com
CIS: [70465,203]			 70465.203@compuserve.com
FIDO:   1:105/51	 Leonard.Erickson@f51.n105.z1.fidonet.org
(The CIS & Fido addresses are preferred)
Newsgroups: sci.crypt,alt.security.pgp
From: strnlght@netcom.com (David Sternlight)
Subject: Re: Chosen crypto-text attack on RSAREFRESH
Organization: Netcom - Online Communication Services (408 241-9760 guest)
Date: Fri, 11 Dec 1992 19:59:31 GMT


Perhaps someone who knows and is not in the U.K. might like to summarize
or quote the offending material in "Spycatcher" that caused the ban
in Britain.

If so, perhaps they'd like to do so by starting another topic, os
U.K. readers don't inadvertently import that material.

If a reader who knows thinks the matter won't be of general interest,
or thinks posting it might create an opportunity for U.K. authorities
to interfere with the net, and would like to e-mail it to me (I'm
in the U.S. where the book is both published and legal), that
would be fine, too.

Thanks;
David
Newsgroups: sci.crypt
From: betz@gozer.idbsu.edu (Andrew Betz)
Subject: Re: Status of DES, or "Is the DES Standard PD?"
Organization: SigSauer Fan Club 
Date: Wed, 16 Dec 1992 16:14:14 GMT

In article <9212142000.AA46814@chaos.intercon.com> amanda@intercon.com (Amanda Walker) writes:
>This seems fairly simple to me.  With the ability to build fast custom 
>hardware (certainly within the NSA's capabilities :)), a brute-force search 
>of the keyspace of DES is *much* more computationally tractable than it is 
>for RSA.  That is to say, DES does not represent a strategic barrier to an 

i would agree.  if the government "pushes" a particular encryption
scheme, it's probably because they're able to crack it.

>DES was never billed as anything more than a cipher system that was good 
>enough for most applications.  I think it still serves as such, and at this 
>point I, at least, am confident that it's exactly what it's advertised to be.  
>I am also confident that the NSA and many of their international counterparts 
>can routinely read DES-encoded traffic.
>
DES is certainly good enough to stop casual snooping, but i wouldn't
trust it if *i* were running a big corporation.  it does make me wonder
how fast the NSA gang can crack DES stuff, though.  seems like i 
remember reading somewhere that one of the criticisms of DES is
that nobody's quite sure where the S-boxes came from...furthermore,
they're non-random, leaving a possible trapdoor somewhere.  if *that*
was true, no wonder NSA wants us all using DES!

>Generally speaking, I find that this does not matter to me.  But make no 
>mistake, I do feel that legal restraints against the use of strong 
>cryptosystems by private citizens should be opposed, for much the same 
>reasons that I support the right to keep and bear firearms and other weapons.
>
yep.  

drew 
--
betz@gozer.idbsu.edu
*** brought into your terminal from the free state of idaho ***
"Now I am become death, destroyer of worlds." - Oppenheimer

Newsgroups: sci.crypt,alt.security.pgp
From: sowa@netcom.com (Erik Sowa)
Subject: Re: RSA Data Security Not All Bad
Organization: Wahoo 5
	<SOWA.92Dec17133825@netcom.com> <1992Dec17.221652.4507@netcom.com>
Date: Fri, 18 Dec 1992 18:30:51 GMT


>>>>> Regarding Re: RSA Data Security Not All Bad; strnlght@netcom.com (David Sternlight) adds:

> In article <SOWA.92Dec17133825@netcom.com> sowa@netcom.com (Erik Sowa) writes:
>Then the export restriction isn't protecting much, either.

David> referring to piracy of products overseas.

David> I don't know if I understand him correctly, but it seems to me
David> that's arguing that if there are lots of thieves one shouldn't
David> bother with locks.

Geez, David, I thought I was in your kill file. Anyway, what I meant was
in the context of munitions control. Those folks overseas already have
strong crypto software. Whether or not it was obtained legally and/or
"ethically" is not important in that context. The export restrictions
are only harming U.S. companies who would like to sell such software
legally to legitimate customers, U.S. businesses who would like to
protect proprietary information relevant to international transactions,
and ordinary U.S. citizens who would like to protect their privacy for
various reasons. They are certainly *not* keeping crypto capabilities
out of the hands of the "bad guys," whoever they may be. The export
restrictions accomplish nothing of value and make U.S. businesses less
competitive. So, yes, in the context of munitions control I do think it
is a waste of time, money, and effort to continue to bother with locks
that don't keep out the bad guys but make life harder for the good guys.

-- 
Erik Sowa (sowa@netcom.com)
Newsgroups: sci.crypt,alt.society.civil-liberty