by Robert Sedgewick

The idea behind public-key cryptosystems is to use a phone book of encryption keys. Everyone's encryption key (public key) is public knowledge. We denote a persons public key byP. Everyone also has a secret key (private key) used to decrypt a message. We denote the secret key byS. The secret key is not know to anyone else but the owner of the public/private key pair.

To transmit a messageM, the sender looks up the receivers public key, uses it to encrypt the message, and then transmits the message. We can denote the encrypted message (ciphertext) by:C = P(M). When the receiver receives the message, he uses his private key (secret decryption key) to decrypt and read the message. For this system to work all of the following conditions must be satisfied:

S(P(M)) = Mfor every messageM.

- All
(S,P)are distinct.- Deriving
SfromPis as hard as readingM.- Both
PandSare easy to compute.The first of these is a fundamental cryptographic property, the second two provide the security, and the forth makes the system feasible to use.

The general scheme was first outlined by W. Diffie and M. Hellman in 1976, but they had no method which satisfied all of the above conditions. Soon afterwards R.Rivest, A. Shamir and L. Adleman came up with a scheme know today as the RSA public-key cryptosystem. This method is based on arithmetic algorithms performed on very large numbers. The public keyPis the integer pair(N,p)and the decryption keySis the integer pair(N,s). These numbers are intended to be very large.Nis typically 200 digits long whilepandsare usually 100 digits.

The first step in the process is to break up the messageMinto numbers less thanN. For example, by takinglg Nbits at a time from the binary string corresponding to the character encoding of the message. Then take these numbers and independently raise them to a powermodulo N. The steps now to encrypt the messageM(actually a piece ofMat a time) is:

C = P(M) = M.^{p}mod NTo decrypt the ciphertext

C, compute:

M = S(C) = C.^{s}mod N

Here's how it all works: First, generate three large (approximately 100-digit) "random" prime numbers: the largest will besand we'll call the other twoxandy. ThenNis chosen to be the product ofxandy, andpis chosen so that

ps mod (x-1)(y-1) = 1.It is possible to prove that, with

N,pandschosen in this way, we have

M^{ps}mod N = Mfor all messages

M.

For example, with our standard encoding , the messageATTACK AT DAWNmight correspond to the 28-digit number:

0120200103110001200004012314 (where A=01, B=02, C=03, D=04, E=05, F=06, etc).

Now to keep the example small, we start with some two digit primes (rather than the 100-digit required): take

x= 47,y= 79 ands= 97. These values lead toN= 3713) the product ofxandy) andp= 37 (the unique integer which gives a remainder of 1 when multiplied by 97 and divided by 3588). Now, to encode the message, we break up the message into 4-digit chunks and raise to thepth power (moduloN). This gives us the encoded version:

1404293235360001328422802235. That is, 0120

^{37}mod 3713 = 1404, 2001^{37}mod 3713 = 2932, 0311^{37}mod 3713 = 3536, etc. The decoding process is the same, usingsrather thanp. Thus, we get the original message back because 1404^{97}mod 3713 = 0120, 2932^{97}mod 3713 = 2001, etc.

Recall that the decryption key s (and the factorsxandyofN) are to be kept secret, and that the success of the method depends on the cryptanalyst not being able to find the values ofs, givenNandp. Now, for our small example, it is easy to discover that 3713 = 47 * 79, but ifNis a 200-digit number, one has little hope of finding its factors. That is,sseems to be difficult to compute from knowledge ofp(andN), though no one has been able to prove that to be the case. Apparently, findingpfromsrequires knowledge ofxandy, and apparently it is necessary to factorNto calculatexandy. But factoringNis thought to be very difficult: the best factoring algorithms known would take millions of years to factor a 200-digit number using current technology.