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:

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.

Digital Signatures

Public key cryptography can be used for authenticating signatures in electronic messages because of the property m = P(S(m)) as well as m = S(P(m)). Suppose you must send a signed message so that the recipient, say your bank, can be certain the message came from you and is not a forgery. You encrypt your signature message with your secret key to obtain S(m). You append this to your plain text message to the bank, and encrypt the entire message with the bank's public key. The bank decrypts the message with it's secret key, reads the plaintext, and finds your encrypted signature at the end. The bank then applies your public key to your signature message, which you encrypted with your secret key, and obtains your signature message in plaintext. Only your secret key can encode your signature message so that your public key decrypts it into plain text.

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
2426th access Last modified: Sat 7 Nov 2015