## Public Key Cryptography

Older methods used a monoalphabetic substitution which required both the encryption and decryption keys to be kept secret because one was trivially derived from the other.

Diffie and Hellman (1976) proposed an algorithm such that deriving the decryption key given the encryption key would be impossible. The requirements are:

• S(P(m))=m
Where m is the plaintext message, P(m) is the message encrypted with the public key, P, and S(P) is P encrypted with the secret key, S. That is, the secret key, S, decrypts a message encrypted with the public key, P.
• S cannot be deduced from P

• P(m) cannot be broken by plaintext attack

One algorithm that meets these requirements was discovered by Rivest et al. (1978). It is:
1. choose two large primes, p and q, each greater than 10 to the power 100.
2. compute n = pq and z = (p - 1)(q - 1)
3. chose d not a factor of z
4. find e such that ed(mod z) = 1
5. divide the message bit stream into blocks of k bits such that 2 to the power k is less than n
6. to encrypt a block of the message, m, compute P(m) = m to the power e (mod n)
7. to decrypt a block of the cypher, P, compute m = S(P(m)) = P to the power d (mod n)
The encryption requires e and n, the decryption d and n. Because large numbers are very difficult to factor, d cannot effectively be derived from e and n, which are publicly known. Rivest et al. estimate that factoring n (which has 200 digits) would require 4 billion years of computer time.

This may be compared to the Data Encryption Standard (DES) adopted by the US government as its official standard for unclassified information (NBS 1977). Michael Wiener of Bell Northern Research has fully designed and tested a chip that tries 50 million DES keys/sec until it finds the correct key. These chips could be manufactured for US\$ 10.50 each. With US\$ 1 million, 57000 of these chips could be built into a parallel machine that can try every DES key in 7 hours. For US\$ 10 million, 21 minutes, for US\$ 100 million, 2 minutes. These figures are well within the money available to large companies and governments for monitoring DES traffic.

## Software for Public Key Cryptography

PGP(tm) (Pretty Good Privacy -- Public Key Encryption for the Masses (tm) ) by Philip Zimmermann (1995) and many others, implements public key encryption and digital signatures. Versions of the program which run on DOS, Unix, and various flavors of MS Windows are avialble from Symantec. Source code is available so you can check it yourself if you think there is a "back door".

The free software GnuPG is available under the terms of the GNU General Public License

Note: Until 1999, the United States government regulations prohibited export of cryptographic software, and PGP source code was exported as a book. Freeware PGP versions can be obtained from outside the United States here.

## References

Diffie, W., and Hellman, M. E. "New Directions in Cryptography," IEEE Trans. on Inform. Theory, vol. IT-22, pp.644-654, Nov. 1976.

National Bureau of Standards "Data Encryption Standard," Fed. Inf. Process. Stand. Publ. 46, Jan. 1977.

Rivest, R. L., Shamir, A., and Adleman, L. "On a Method for Obtaining Digital Signatures and Public Key Cryptosystems," Commun. ACM, vol. 21, pp 120-126, Feb. 1978.

Zimmerman, P. "PGP Source Code and Internals" MIT Press ISBN 0-262-24039-4 1995.

contact: Bruce A. Peterson