Prior to Shannon’s work, cryptology can better be described as an art rather than a science. The best cryptographic algorithms in the pre-1949 era were developed in an ad hoc fashion, with cryptographers haphazardly permuting and convoluting the input until it seemed unfathomable that anybody could unravel the process without knowing the key. Of course, without any basis for this belief, cryptographers had no way of assessing their position. Usually it was only a matter of (sometimes brief) time before a clever cryptanalyst broke the code and the cryptographers had to start all over again.
With Shannon’s work, for the first time we had a theory upon which to base the development of cryptographic algorithms. A cryptographers job is to find one-way trap-door functions. A one-way function is a computable function for which the inverse cannot be computed. The inverse of a function, f, is normally denoted by f-1 and it is the “undo” relation. In other words, for any value of x, f-1(f(x)) = x. Now f-1 won’t always be a function; sometimes it will map more than one input to the same output. In other words, there are two distinct values, x and y, such that f(x) = f(y), and therefore f-1(f(x)) is undetermined because it may be either x or y.
A one-way trap-door function is a function that is not actually one-way at all; it has an inverse, and the inverse is itself a function, but the inverse function is difficult to compute (without the key). It is important that the inverse be a function and be computable, because the recipient of an encrypted message has to have some way to decrypt it (the “undo”).
So how difficult is it to compute the inverse of a one-way trap-door function? Mathematicians are able to classify the difficulty of solving a problem by ranking the efficiency of the best (known) algorithms for solving the problem. A one-way trap-door function is a function that can be computed efficiently but for which the inverse function cannot be computed efficiently.
Cryptographic hash functions are one-way functions, with the added requirement that they be collision-free. Suppose h is a cryptographic hash function. Because h is one-way, it is easy to compute y = h(x) for all x, but hard to compute x = h-1(y) for any y. The collision-free requirement means that given the value y0 = h(x0), it is computationally infeasible to find x1 != x0 such that h(x1) = y0, even if such an x1 exists.
As important as Shannon’s work was, it did not have an immediate impact. It is only now, in retrospect, that we recognize and appreciate the importance of that paper. It established the necessary ground-work that we rely upon today but did not excite sufficient interest to spur further activity in the field. It wasn’t until 1976 that the field really took off. In that year W. Diffie and M. E. Hellman published their revolutionary work entitled New Directions in Cryptography. The significance of this work is that it showed for the first time that private communication was possible even when the communicating parties shared no prior secrets. In other words, encryption did not require a “key” in the traditional sense. Up until 1976, all encryption algorithms relied upon a secret key that the two parties shared prior to exchanging encrypted messages. This “key” might be the secret algorithm, as in the case of a Ceaser cipher, or more recently SkipJack and Clipper. Or, it might be a one-time pad, as in the case of a Vernam cipher.
The traditional crypto-systems with a single key are called symmetric-key systems. In their 1976 paper, Diffie and Hellman introduced a new kind of crypto-system with two keys; one private key and one public key. The private key, which is not shared with anybody and is known only to the encrypting party, is used to encrypt messages. the public key, which is known to everybody, contains all the information needed to decrypt that message.
Suppose Alice wants to send a private message to Bob (it is customary when giving examples of cryptography to use Alice and Bob). With symmetric-key encryption, Alice and Bob would have to first agree on a key to use to encrypt and decrypt the message. But with public-key encryption Alice can use Bob’s public key. There is no need to meet in person or exchange by some other means a shared secret key. There is no boot-strapping problem. Once Alice has encrypted the message using Bob’s public key, only Bob knows how to decrypt the message. Even Alice cannot decrypt the message (of course, she has no need to do so since she knows the plain-text anyway, having created it herself). Bob uses his private key, which he divulges to nobody, to decrypt the message and recover the plain-text. If Bob wants to send a reply, he uses Alice’s public key to encrypt a message for her eyes only. She then uses her own private key, known only to her, to decrypt Bob’s reply.
By far the most common public-key algorithm in use today is RSA, which was invented in 1978 by R. L. Rivest, A. Shamir, and L. Adleman (hence the name, derived from the last initials of the three inventors). The RSA trapdoor one-way function is the discrete exponentiation