public key cryptosystem

Cryptosystems all involve a key--a piece of information necessary to encrypt information. This could be in the form of a one-time pad, such as the string of binary bits used by the Vernam cipher; or a 56-bit number as used in the U. S. Data Encryption Standard. For conventional cryptosystems, these keys must be kept secret--so they must be exchanged carefully. One way to do this is by the Diffie-Hellman key exchange system.

In a public key cryptosystem the key is made public. For example, with the RSA encryption system, two numbers (n, e) are made public. (A separate private key (n, d) for decryption is kept secret.) RSA, like most all of the public key cryptosystems that are regarded as secure, are based on number theory techniques that involve the multiplication of large integers [Odlyzko94]. It s known how to break these systems, but the computational burden usually can be made far beyond our current capabilities by increasing the key size.

Another advantage of public key systems is that they allow for digital signatures--ways of verifying the source of the document. Most conventional systems also allow digital signature, but usually in a more award manner.

However, conventional cryptosystems tend to be computationally easier and many times faster than most public key cryptosystems. For that reason systems such as the IS-54 authentication system for North America digital cellular systems uses a sequence of shared secrets and challenge-response techniques, rather than a public key system, to verify the identity of mobile phone units.

Many of the public key systems are also patented by private companies, this also limits their use. For example, MIT filed for a patent on RSA which was granted in 1983 (U.S. patent #4,405,829). The three founders of RSA created RSA Data Security and later the RSA patent and several other public key patents were exclusively licensed to its spin-off Public Key Partners. For several years Jim Bidzos, this last group’s president, threaten to sue Pretty Good Privacy for their use of RSA in their PGP encryption freeware. PGP claimed it used the algorithm, but not RSA code. This threat was eventually removed when RSA offered a toolkit RSA REF for the algorithm which is free for non- commercial use. PGP now uses this toolkit instead of their own code.

Related pages (outside of this work)

• RSA Laboratories' Frequently Asked Questions About Today's Cryptography
• Electronic Frontier Foundation

References:

Odlyzko94

A. M. Odlyzko, "Public key cryptology," AT\&T Tech. J., 73:5 (Sept-Oct 1994) 17-23.

Pomerance94a

C. Pomerance editor, Cryptology and computational number theory--an introduction, Proc. Symp. Appl. Math. Vol, 42, Amer. Math. Soc., Providence, RI, 1990.  pp. 1--12, MR 92e:94023

Schneier96

B. Schneier, Applied cryptography, 2nd edition, John Wiley \& Sons, 1996.  New York, NY, [A comprehensive pragmatic survey of modern cryptology--perhaps the best introduction for those actually wishing to understand the details of the usual implementations.]

Simmons91

G. Simmons editor, Contemporary cryptology -- the science of information integrity, IEEE Press, 1992.  pp. xvi+640, MR 93k:94009