PGP: The Gory Details

Reference: Algorithms in C
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 by P. Everyone also has a secret key (private key) used to decrypt a message. We denote the secret key by S. The secret key is not know to anyone else but the owner of the public/private key pair.

To transmit a message M, 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)) = M for every message M.
• All (S,P) are distinct.
• Deriving S from P is as hard as reading M.
• Both P and S are 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 key P is the integer pair (N,p) and the decryption key S is the integer pair (N,s). These numbers are intended to be very large. N is typically 200 digits long while p and s are usually 100 digits.

The first step in the process is to break up the message M into numbers less than N. For example, by taking lg N bits 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 power modulo N. The steps now to encrypt the message M (actually a piece of M at a time) is:

C = P(M) = Mp mod N.

To decrypt the ciphertext C, compute:

M = S(C) = Cs mod N.

Here's how it all works: First, generate three large (approximately 100-digit) "random" prime numbers: the largest will be s and we'll call the other two x and y. Then N is chosen to be the product of x and y, and p is chosen so that

ps mod (x-1)(y-1) = 1.

It is possible to prove that, with N, p and s chosen in this way, we have

Mps mod N = M

for all messages M.

For example, with our standard encoding , the message ATTACK AT DAWN might 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 and s = 97. These values lead to N = 3713) the product of x and y) and p = 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 the pth power (modulo N). This gives us the encoded version:

1404293235360001328422802235.

That is, 012037 mod 3713 = 1404, 200137 mod 3713 = 2932, 031137 mod 3713 = 3536, etc. The decoding process is the same, using s rather than p. Thus, we get the original message back because 140497 mod 3713 = 0120, 293297 mod 3713 = 2001, etc.

Recall that the decryption key s (and the factors x and y of N) are to be kept secret, and that the success of the method depends on the cryptanalyst not being able to find the values of s, given N and p. Now, for our small example, it is easy to discover that 3713 = 47 * 79, but if N is a 200-digit number, one has little hope of finding its factors. That is, s seems to be difficult to compute from knowledge of p (and N), though no one has been able to prove that to be the case. Apparently, finding p from s requires knowledge of x and y, and apparently it is necessary to factor N to calculate x and y. But factoring N is thought to be very difficult: the best factoring algorithms known would take millions of years to factor a 200-digit number using current technology.