Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!falk
From: falk@sun.uucp (Ed Falk)
Newsgroups: sci.crypt
Subject: Re: RSA Discussion and Speculation
Message-ID: <49704@sun.uucp>
Date: 16 Apr 88 02:07:53 GMT
References: <6053@watdragon.waterloo.edu> <114@cvbnet2.UUCP> <49480@sun.uucp> <921@rlgvax.UUCP>
Distribution: na
Organization: Sun Microsystems, Inc. - Mtn View, CA
Lines: 76
Keywords: RSA algorithm wanted
Summary: 0 <= M <= n-1

In article <921@rlgvax.UUCP>, dennis@rlgvax.UUCP (Dennis.Bednar) writes:
> In article <49480@sun.uucp>, falk@sun.uucp (Ed Falk) writes:
> > 
> > Here is how RSA works:
> > 
> > You come up with two very large primes, p and q.  I take their product
> > and call it n.  I use some other cute math to derive e and d from p and
> > q.  Now:
> > 
> > 		e
> > 	E(M) = M  mod n
> > 
> > 		d
> > 	D(C) = C  mod n
> > 
> > For instance, if you choose 100-digit numbers for p and q, then n will
> > be about 200 digits.  Take your message and break it into 200-digit chunks
> > and raise it to the e power, mod n.  This gives you another 200-digit
> > encrypted number which you send to me.
> 
> Ed, thanks very much for the lucid explanations.  But I have
> a simple question.  In order to better understand what you
> were saying, I tried picking small prime numbers, say p=3, and q=7.
> Each is a 1-digit number, and the product, n, is 21, which is 2 digits.
> So take the message and break it into 2 digit chunks.  Lets look
> at what happens to an arbitrary two-digit chunk. Well, a two
> digit number is a number between 00 and 99.  The problem is that
> 	            e
> 	C = E(M) = M mod n
> 
> will always return a number between 0 and 21, and therefore
> so will the D() function, since both functions return a number
> mod 21.  Therefore if you encrypt a clear message M whose value
> was bigger than 21, you will never be able to decode it back
> to the original clear text, because the D() function will never
> return more than 21.

Good point.  I went back to the original paper and it said that both
the plaintext (M) and the cypertext (C) are integers between 0 and
n-1.

> 
> By the way, your discussion did not mention what d and e were,
> or how they were related to the original chosen p and q.
> I assume that they were numbers chosen, such that the the
> functions D and E were inverses of one another, ie that
> 
> 	M = D(E(M))
> 	C = E(D(C))
> 
> for all clear text messages M and all encoded messages C.
> The fact that such numbers d and e exist, and can be found
> for all M and all C is incredible (to me)!

To be honest, I don't understand the math behind this part.

Apparently, there are a large number of d and e for each (p,q).  According
to R,S,A, you choose any d such that d is relatively prime to (p-1)*(q-1).

	gcd( d, (p-1)*(q-1) ) = 1

Any prime greater than max(p,q) will do here.

e is simply the "multiplicitive inverse" of e, mod (p-1)*(q-1).

	(e*d) mod (p-1)*(q-1) = 1

They give an iterative algorithm for computing e which I'm not going to
bother repeating here.  It's similar to Euclid's algorithm for computing
the gcd of (p-1)*(q-1) and d.


-- 
		-ed falk, sun microsystems
		 sun!falk, falk@sun.com
terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.