Math 696 -- Public-key cryptography

Public-key cryptography

Public-key cryptography

With the growth of electronic communications, privacy has become a significant issue on the Internet. There is a newsgroup alt.privacy, a vast literature on anonymous email, and services that offer anonymous World-Wide Web surfing.

Average computer users would likely be satisfied with the capability of putting their email in an envelope. In the ordinary course of events, email is more like a postcard: it can easily be read in passing. Private email is now widely and freely available through public-key cryptography.

To use classical ciphers, the sender and recipient must exchange a common key ahead of time. The idea behind public-key cryptography is that one key can be used to encode a message, and a different key can be used to decode the message.

A user can make public one of a pair of complementary keys to enable the world to send enciphered messages that can be deciphered only by that user. Also, the user can broadcast enciphered messages that everyone can decipher and verify as coming from that user. Thus, public-key cryptography simultaneously meets the goals of privacy and of authentication.

The first mathematical implementation of a public-key cryptosystem was published by R. L. Rivest, A. Shamir, and L. Adleman in 1978, and is known as the RSA cryptosystem. The original paper, available from Rivest's home page, is very clear and is well worth reading. The basis of the method is Fermat's theorem from number theory.

According to Euler's generalization of Fermat's "little" theorem, if a and n are positive integers that have no common factors, and if phi(n) denotes the number of integers between 1 and n that have no factors in common with n, then a^phi(n) is congruent to 1 modulo n. For example, if p is a prime number, then phi(p) = p-1, and so a^p-1 is congruent to 1 modulo p if a is not divisible by p. If n is the product pq of two distinct prime numbers p and q, then phi(n) = (p-1)(q-1), and so a^(p-1)(q-1) is congruent to 1 modulo n if neither p nor q divides a.

The proof of Fermat's little theorem is not difficult. You can find the proof in almost any book on number theory. (Do not confuse this theorem with Fermat's "last" theorem, which was proved to great acclaim in the 1990s.)

To use the RSA cryptosystem, you choose two large prime numbers p and q. Because it is very difficult to factor large numbers, you can safely make the product n public without worrying that someone will be able to recover your secret numbers p and q. You also choose and make public a large number d that has no factors in common with the integers (p-1) and (q-1). You compute and keep secret a number e with the property that the product ed is congruent to 1 modulo (p-1)(q-1). (You can find e by using the Euclidean algorithm.)

To send you a private message, your correspondent first converts the alphabetic message into a number M by a simple substitution scheme (such as a->1, b->2, ...) and then sends you the number M^d modulo n. You--and only you--can recover the original number M by raising M^d to the power e and reducing modulo n. This works because, by construction, the product ed can be written in the form 1 + k(p-1)(q-1) for some integer k, so by Fermat's theorem M^ed, which equals M ×M^k(p-1)(q-1), is congruent to M modulo n.

Similarly, you can send a "signed" message to the world by raising your message to the power e modulo n. Anyone can decode the message by raising it to the power d modulo n. It is certain that the message originated with you, because nobody else knows the encoding key e.

Philip R. Zimmermann implemented the RSA cryptosystem in a program called PGP (Pretty Good Privacy), which is freely available for noncommercial use. For some years this software had an underground status, but now there is a commercial supported version.

To use PGP, you must first generate your pair of keys. On a Unix system, create a private directory to store your keys by executing the following command at the prompt in a terminal window:

mkdir ~/.pgp; chmod 700 ~/.pgp

Next execute the command pgp -kg and follow the instructions to generate your keys. You will then want to publicize your public key, perhaps by linking it to your home page. You can extract your public key and store it in an ASCII text file my-public-key.asc by executing the command pgp -kxa "user ID" my-public-key (where user ID is the ID you used in generating the key).

To communicate privately with other PGP users, you will need to obtain their public keys (perhaps from their World-Wide Web pages). If you obtain a public key file, then you can execute the command pgp -ka keyfile to add that key to your "keyring." Now to encrypt a plaintext file to send by email to a user whose public key is on your keyring, execute the command pgp -eat textfile "recipient user ID" to produce an ASCII file textfile.asc looking something like this:

You can include this file in email. The recipient might save your message to a file ciphertext and then decipher it with the command pgp ciphertext.

Incidentally, some mail tools are beginning to support PGP internally to facilitate the encryption and decryption steps. Also, PGP is a pretty good way to send binary files through email channels. The command pgp -a binary-file creates (without using any public-key enciphering) an ASCII encoding of the file binary-file that is suitable for emailing. The recipient recovers the binary file by executing the command pgp filename.

For a summary of PGP commands, type pgp -h at a command prompt. For further information, read the manual page via man pgp. There is also a comp.security.pgp newsgroup hierarchy. For even more information, see the links at the MIT distribution site. (Users in the Department of Mathematics at Texas A&M University can view local information on using PGP.) The user's manual is Zimmermann's Official PGP User's Guide.

Public-key cryptography