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: <49480@sun.uucp>
Date: 14 Apr 88 05:08:03 GMT
References: <6053@watdragon.waterloo.edu> <114@cvbnet2.UUCP>
Distribution: na
Organization: Sun Microsystems, Inc. - Mtn View, CA
Lines: 86
Keywords: RSA algorithm wanted

In article <114@cvbnet2.UUCP>, gdelong@cvbnet2.UUCP (Gary Delong x5232) writes:
> 
> The following is my submission for dumb question of the month:
> 
> Having heard much about the "Public Key Crytosystem" for many years, I have
> yet to see the algorithm.
> 
> Could someone e-mail me the information, or perhaps even post it?


Since nobody else has said anything, I guess I will.  Here's a summary of
the introduction to Rivest, Shamir & Adlemen's original paper:

	M := plaintext message
	C := encrypted message
	E := encryption function
	D := decryption function

	so, C=E(M) and M=D(C)

It is (hopefully) impossible to derive D even if you know E.  As an
added bonus, it is impossible to derive E from D.  The idea is that
I invent functions E and D that are unique to me (call them Em and Dm).
I now *publish* Em.  In this way, anybody can send a message to me
by using C=Em(M) and mailing C to me over any unsecure channel.  I
use M=Dm(C) to read the message.  Since nobody can derive Dm from Em,
my mail is safe even though Em and C were transmitted through unsafe
channels.

As an added bonus, the RSA algorithm is commutitive.  In other words, 
not only does

	M = D(E(M))

but

	M = E(D(M))

This means you can "sign" messages to guarentee authenticity.  For instance,
if you have your own functions, Ey and Dy you can encrypt a message
like this:

	C = Dy(Em(M))

I then use

	M = Dm(Ey(M))

If the message is legible, then I know that (a) nobody but me could have
read it, and (b) nobody but you could have sent it.

That's the idea behind public-key cryptosystems.  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.

The rest of the paper is devoted to deriving e and d from p and q,
effecient algorithms for raising large numbers to large powers modulo
other large numbers, finding large primes and so on.

You could probably still order a copy from MIT press or LCS

	Laborator for Computer Science
	545 Technology Square
	Cambridge, Massachusetts
	02139

	"A Method for Obtaining Digital Signatures and Public-Key
	Cryptosystems"; Ronald Rivest, Adi Shamir, Len Adleman;
	LCS/TM82; April 4, 1977 (revised Dec 12, 1977)
-- 
		-ed falk, sun microsystems
		 sun!falk, falk@sun.com
terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.