Path: utzoo!mnetor!uunet!rlgvax!dennis
From: dennis@rlgvax.UUCP (Dennis.Bednar)
Newsgroups: sci.crypt
Subject: Re: RSA Discussion and Speculation
Message-ID: <921@rlgvax.UUCP>
Date: 15 Apr 88 23:03:08 GMT
References: <6053@watdragon.waterloo.edu> <114@cvbnet2.UUCP> <49480@sun.uucp>
Distribution: na
Organization: Computer Consoles Inc, Reston VA
Lines: 55
Keywords: RSA algorithm wanted

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.

Please clear up my misconfusion, if you could.  Thanks.

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)!

-- 
FullName:	Dennis Bednar
UUCP:		{uunet|sundc}!rlgvax!dennis
USMail:		CCI; 11490 Commerce Park Dr.; Reston VA 22091
Telephone:	+1 703 648 3300