In 1976, Diffie and Hellman described the concept of public key cryptography, though at that time no realizations of the concept were publicly known (as mentioned in the introduction to this chapter, Clifford Cocks of the British cryptographic agency CESG had invented a secret version of RSA in 1973). In this section, we give the general theory of public key systems.

There are several implementations of public key cryptography other than RSA. In later chapters we describe three of them. One is due to ElGamal and is based on the difficulty of finding discrete logarithms. A second is NTRU and involves lattice methods. The third is due to McEliece and uses error correcting codes. There are also public key systems based on the knapsack problem. We don’t cover them in this book; some versions have been broken and they are generally suspected to be weaker than systems such as RSA and ElGamal.

A public key cryptosystem is built up of several components. First, there is the set $M$ of possible messages (potential plaintexts and ciphertexts). There is also the set $K$ of “keys.” These are not exactly the encryption/decryption keys; in RSA, a key $k$ is a triple $(e\text{,}d\text{,}n)$ with $ed\equiv 1(\text{mod}\varphi (n))$. For each key $k$, there is an encryption function $E_k$ and a decryption function $D_k$. Usually, $E_k$ and $D_k$ are assumed to map $M$ to $M$, though it would be possible to have variations that allow the plaintexts and ciphertexts to come from different sets. These components must satisfy the following requirements:

1. $E_k(D_k(m))=m$ and $D_k(E_k(m))=m$ for every $m\in M$ and every $k\in K$.

2. For every $m$ and every $k$, the values of $E_k(m)$ and $D_k(m)$ are easy to compute.

3. For almost every $k\in K$, if someone knows only the function $E_k$, it is computationally infeasible to find an algorithm to compute $D_k$.

4. Given $k\in K$, it is easy to find the functions $E_k$ and $D_k$.

Requirement (1) says that encryption and decryption cancel each other. Requirement (2) is needed; otherwise, efficient encryption and decryption would not be possible. Because of (4), a user can choose a secret random $k$ from $K$ and obtain functions $E_k$ and $D_k$. Requirement (3) is what makes the system public key. Since it is difficult to determine $D_k$ from $E_k$, it is possible to publish $E_k$ without compromising the security of the system.

Let’s see how RSA satisfies these requirements. The message space can be taken to be all nonnegative integers. As we mentioned previously, a key for RSA is a triple $k=(e\text{,}d\text{,}n)$. The encryption function is

where we break $m$ into blocks if $m\ge n$. The decryption function is

again with $m$ broken into blocks if needed. The functions $E_k$ and $D_k$ are immediately determined from knowledge of $k$ (requirement (4)) and are easy to compute (requirement (2)). They are inverses of each other since $ed\equiv 1(\text{mod}\varphi (n))$, so (1) is satisfied. If we know $E_k$, which means we know $e$ and $n$, then we have seen that it is (probably) computationally infeasible to determine $d$, hence $D_k$. Therefore, (3) is (probably) satisfied.

Once a public key system is set up, each user generates a key $k$ and determines $E_k$ and $D_k$. The encryption function $E_k$ is made public, while $D_k$ is kept secret. If there is a problem with impostors, a trusted authority can be used to distribute and verify keys.

In a symmetric system, Bob can be sure that a message that decrypts successfully must have come from Alice (who could really be a group of authorized users) or someone who has Alice’s key. Only Alice has been given the key, so no one else could produce the ciphertext. However, Alice could deny sending the message since Bob could have simply encrypted the message himself. Therefore, authentication is easy (Bob knows that the message came from Alice, if he didn’t forge it himself) but non-repudiation is not (see Section 1.2).

In a public key system, anyone can encrypt a message and send it to Bob, so he will have no idea where it came from. He certainly won’t be able to prove it came from Alice. Therefore, more steps are needed for authentication and non-repudiation. However, these goals are easily accomplished as follows.

Alice starts with her message $m$ and computes $E_{k_b}(D_{k_a}(m))$, where $k_a$ is Alice’s key and $k_b$ is Bob’s key. Then Bob can decrypt using $D_{k_b}$ to obtain $D_{k_a}(m)$. He uses the publicly available $E_{k_a}$ to obtain $E_{k_a}(D_{k_a}(m))=m$. Bob knows that the message must have come from Alice since no one else could have computed $D_{k_a}(m)$. For the same reason, Alice cannot deny sending the message. Of course, all this assumes that most random “messages” are meaningless, so it is unlikely that a random string of symbols decrypts to a meaningful message unless the string was the encryption of something meaningful.

It is possible to use one-way functions with certain properties to construct a public key cryptosystem. Let $f(m)$ be an invertible one-way function. This means $f(x)$ is easy to compute, but, given $y$, it is computationally infeasible to find the unique value of $x$ such that $y=f(x)$. Now suppose $f(x)$ has a trapdoor, which means that there is an easy way to solve $y=f(x)$ for $x$, but only with some extra information known only to the designer of the function. Moreover, it should be computationally infeasible for someone other than the designer of the function to determine this trapdoor information. If there is a very large family of one-way functions with trapdoors, they can be used to form a public key cryptosystem. Each user generates a function from the family in such a way that only that user knows the trapdoor. The user’s function is then published as a public encryption algorithm. When Alice wants to send a message $m$ to Bob, she looks up his function $f_b(x)$ and computes $y=f_b(m)$. Alice sends $y$ to Bob. Since Bob knows the trapdoor for $f_b(x)$, he can solve $y=f_b(m)$ and thus find $m$.

In RSA, the functions $f(x)=x^e(\text{mod}n)$, for appropriate $n$ and $e$, form the family of one-way functions. The secret trapdoor information is the factorization of $n$, or, equivalently, the exponent $d$. In the ElGamal system (Section 10.5), the one-way function is obtained from exponentiation modulo a prime, and the trapdoor information is knowledge of a discrete log. In NTRU (Section 23.4), the trapdoor information is a pair of small polynomials. In the McEliece system (Section 24.10), the trapdoor information is an efficient way for finding the nearest codeword (“error correction”) for certain linear binary codes.