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:
- choose two large primes, p and q, each
greater than 10 to the power 100.
- compute n = pq and z = (p - 1)(q - 1)
- chose d not a factor of z
- find e such that ed(mod z) = 1
- divide the message bit stream into blocks of k bits such that
2 to the power k is less than n
- to encrypt a block of the message, m, compute
P(m) = m to the power e (mod n)
- 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
PGP Security .
(Note: American government regulations prohibit export of cryptographic software,
however there are
distribution centers
outside the United States.)
Source code is available so you can
check it yourself if you think there is a "back door."
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.
Last Modified:
access.
Bruce A. Peterson peterson@mso.anu.edu.au