3.3. Asymmetric Ciphers

One of the problems with symmetric ciphers is that they require both parties to the exchange of encrypted messages to have access to a shared secret: the key. If we think in terms of a typical application, encrypted email, we see immediately why this is a problem: We must give every possible correspondent a key to use when corresponding with us. Furthermore, this key must be different for each correspondent so that one can't read the messages of another. Because for n correspondents, each able to communicate privately with any other, this requires ½ (n² - n) keys, the number of keys grows quadratically in the number of correspondents.

Sometimes, sharing a secret isn't possible. Consider the typical application of securing a Web transaction (see Chapter 6). Because an online merchant doesn't know a priori who its customers will be, it is not possible to use a shared secret to secure the transaction. There are many other situations in which it is impractical or impossible for both parties to use a preassigned key.

In this section, we consider algorithms that enable two parties to communicate securely without such problems. For reasons that will become clear shortly, this is usually called public key cryptography.

Asymmetric ciphers are those that have different keys for encryption and decryption. The idea goes back to [Diffie and Hellman 1976] and, independently, [Merkle 1978].

The GCHQ (Government Communications Headquartersthe British equivalent of the American National Security Agency) also has some claim to the idea of asymmetric ciphers, but its work was classified and unpublished until after the Diffie-Hellman and Merkle papers.

The notion was that keys would come in pairsone each for encryption and decryptionand that one key could not be derived from the other. These algorithms are important for public key cryptography, in which one key is public and used by anyone to encrypt a message that can be decrypted only by the holder of the other, secret, key. Because only the recipient has the secret key, the messages cannot be read by anyone else.

Asymmetric ciphers are based on one-way trapdoor functions, which are easy to compute but difficult to invert. It is the trapdoor function that makes it difficult to obtain one key from the other. See [Schneier 1996] for a discussion of many of these algorithms and the trapdoor functions on which they are based. Here, we consider only two of the asymmetric algorithms: RSA and ElGamal.

RSA

The RSA algorithm was invented by Ron Rivest, Adi Shamir, and Ken Adleman and described in their 1978 paper [Rivest, Shamir, and Adleman 1978]. RSA is based on the difficulty of factoring large numbers. Given two large prime numbers, p and q, the trapdoor function is to multiply p and q to obtain the product n. Obviously, this is trivial to compute, but the difficulty of factoring n into p and q makes it very hard to invert. The mathematics required to understand RSA is modestmostly some facts about modular arithmeticand, except for the proof that it works, is probably familiar to most of us. For an excellent review of the necessary mathematics, see [Ferguson and Schneier 2003]; a slightly more comprehensive review is given in [Menezes, Oorschot, and Vanstone 1996].

The description of RSA is simple. Pick two large random numbers, p and q, of about the same size. They should be at least 1,024 bits long, with larger numbers being more secure. Then choose a number e for the encryption key such that e has no factors in common with (p - 1)(q - 1). Popular choices for e are 3, 5, 17, and 65,537.

These values are chosen because they make it easier to perform the calculations discussed below. In practice, e is often chosen first, and p and q are chosen to ensure that (p - 1)(q - 1) has no factors in common with it.

Next, choose the decryption key d such that ed = 1 mod (p - 1)(q - 1). The condition on e and (p - 1)(q - 1) ensures that this is possible. We say that d is the multiplicative inverse of e mod (p - 1)(q - 1) and sometimes write d = 1/e mod (p - 1)(q - 1). The public key is the pair (n, e), and we can make it known to anyone who might wish to send us a message. The numbers p, q, and d are secret and should not be revealed. Only d is necessary to decrypt messages, so p and q could be discarded, but retaining them allows us to build more efficient implementations of the decryption algorithm.

Given a message m, thought of as a single large integer, such that m < n, we encrypt it as

Equation 4

where c is the encrypted message. We decrypt it as

Equation 5

We should take note of two things here. First, given that we choose p and q to be on the order of 1,024 bits, n 2,048 bits long. Thus, we can't encrypt a message longer than about 256 characters. Second, making these calculations requires working with huge numbers, so in general, we will need to use an arbitrary-precision math library for the calculations.

It's not difficult to see why (4) and (5) work:

Equation 6

The only step that's not completely obvious is (6). This follows from Fermat's little theoremthe details are in [Menezes, Oorschot, and Vanstone 1996], but we don't need to understand any of that to use the algorithm.

A simple example will make these ideas clear. Let us choose two primes of 4 bits eachsay, 5 and 11for our p and q, and let's choose 3 for e. Next, we need to find a number d such that 3d = 1 mod (p-1)(q-1) = 1 mod 40. It is easy to check that 27 satisfies this condition.

In this case, the numbers are small enough that we can just search for d directly. In general, the easiest way to find d is to use the extended Euclidean Algorithm [Knuth 1998], but we needn't worry about this unless we are trying to implement the RSA algorithm. See Appendix A for bc and python scripts that calculate these inverses.

We now have everything we need to encrypt a message. The public key is (55, 3), and the secret key is 27. Let us encrypt the message 1101₂ (decimal 13):

c = 13³ mod 55 = 2197 mod 55 = 52

To decrypt this, we use the secret key as in equation (5):

m = 52²⁷ mod 55

Even with these small numbers, the calculations can get out of hand. Although we could calculate 52²⁷ by hand (the result is 47 digits), it's easier to use an arbitrary-precision calculator, such as the UNIX utility bc for this:

$ bc -q
52^27%55
13

As expected, we get our original message, 13, back.

An algorithm that encrypts messages that are limited to 5 bits is not particularly useful, of course, but even with the more typical implementation, we are still limited to about 256 bytes. We could solve this problem by partitioning our messages into blocks of 5 bits and encrypting each block independently, as we do for block ciphers, but RSA is very slowthe typical software implementation of RSA runs at about 1 percent of the speed of DES [Schneier 1996]so RSA is almost never used this way.

Instead, we combine RSA with one of our symmetric ciphers. Recall that a problem with symmetric ciphers is that they require both parties to an exchange of encrypted messages to have access to the key. Public key systems, such as RSA, solve this problem as follows. Suppose that Alice wants to send an encrypted message to Bob.

The names Alice and Bob are traditionally used in cryptographic literature to refer to two people who wish to communicate with each other.

Alice picks a random number as a one-time session key for a symmetric cipherAES, sayand encrypts it, using Bob's public key. Alice then encrypts the message itself with AES, using the random session key, and sends both the RSA encrypted key and the AES encrypted message to Bob.

The actual process is a bit more complicated. An AES key, K, of 256 bits is too small to encrypt securely with RSA because for a public key of, say, (n, 3), where n has about 2,048 bits, we have K^e < n. Therefore, K^e mod n = K^e, and an attacker can recover K by merely taking the e^th root. To avoid this, Alice can choose a large random number to encrypt with RSA. Both Alice and Bob then use this random number to generate the actual key, K. Another method is for Alice to pad K with random bits so that the total message has about the same number of bits as n. Other methods of encoding K and, more generally, any message m, are given in PKCS #1 [RSA Laboratories 2002]. The encoding methods in PKCS #1 add security because they use hash functions (Section 3.4) and pseudorandom masking functions that ensure that two similar or identical messages will have dissimilar encodings. At the same time, the encodings have a structure that the receiver can check to avoid certain chosen ciphertext attacks. See [Bleichenbacher, Kalisky, and Staddon 1998] and [Kaliski and Robshaw 1995] for details on how PKCS #1 encoding prevents many attacks on RSA-encoded messages.

When Bob receives these, he first uses his secret RSA key to recover the AES session key, and then uses that to decrypt the message. If several messages will be exchanged in a session, the same session key is used for each message, thereby avoiding the relatively slow RSA step for all messages but the first. We will see this same patternusing an asymmetric cipher to exchange session keys for a symmetric ciphermany times as we study VPNs and related security protocols.

ElGamal

If p is prime, and g, y {1, 2, . . . , p - 1}, the discrete logarithm problem is to find an integer x such that y = g^x mod p. In the real numbers, R, this is merely the normal logarithm, and x is easily determined, although it may not be an integer, of course. In the finite field Z_p, which is what we are discussing, this is a problem on the same order of difficulty as factoring the prime p. Therefore, for large p, modular exponentiation is a suitable trapdoor function for an asymmetric cipher algorithm: It is trivial to perform modular exponentiation, but inverting it requires finding its discrete logarithm.

The ElGamal encryption algorithm [ElGamal 1985] is based on the difficulty of computing a discrete logarithm. We must use some care in picking p and g. Generally, we want p = 2q + 1, where q is also prime, and we want p to be on the order of 2,048 bits or more. [Ferguson and Schneier 2003] suggests the following method for picking g: Choose a random number a {2, 3, . . . , p - 2}, and compute g = a² mod p. If g = 1 or g = p - 1, pick another a and try again. Otherwise, g, which is called the group generator, is suitable.

Next, pick a random number x, and compute y = g^x. The public key is the triple (y, g, p). The private key is x.

To encrypt a message m, choose a random number k that has no factors in common with p - 1, and compute the two numbers:

a = g^k mod p

b = y^km mod p.

The encrypted message is the pair (a, b). To decrypt the message, compute

m = b/a^x mod p

Note that

a^x mod p =(g^k )^x mod p = g^kx mod p = g^xk mod p = (g^x)^k mod p = y^k mod p

Thus, dividing b by a^x (modulo p) yields the original message m.

To see how this works in practice, let q be 3 so that p = 7. Choose g = 2. Because 2 = 3² mod 7, g is a suitable choice for the generator. Let's use 4 for our secret key, so that y = 2⁴ mod 7 = 2.

Suppose that we want to encrypt the message 110₂ (decimal 6). First, we choose a random k with no factors of 2 or 3; let's say 5. We compute

a = 2⁵ mod 7 = 4

b = 2⁵ · 6 mod 7 = 3

To recover the message, we compute

a^x mod 7 = 4⁴ mod 7 = 4

b/a^x mod 7 = 3 · 2 mod 7 = 6

where 1/a^x = 2 mod 7.

Diffie-Hellman Key Exchange

ElGamal encryption is closely related to the Diffie-Hellman key-exchange algorithm [Diffie and Hellman 1976]. Diffie-Hellman enables two parties to dynamically agree on a shared secret over an insecure transmission medium without any previously shared information. Even if their entire session is captured, an attacker will not be able to discover the shared secret. This seemingly impossible task is in fact quite simple. The process is illustrated in Figure 3.8.

To produce the shared secret, Alice chooses a prime p and generator g, just as in ElGamal. Then Alice chooses a random private key x_A, calculates mod p, and sends the triple (p, g, y_A) to Bob. Bob chooses his own random private key x_B, calculates mod p, and sends it to Alice. Note that it is impractical for an attacker to recover the two private keys x_A and x_B, because of the difficulty of the discrete logarithm problem.

Next, Alice generates her secret key, K_A, as mod p. Likewise, Bob calculates his own secret key as mod p. But now we have

so Alice and Bob have, in fact, calculated the same key independently.

In many situations, Alice and Bob will have agreed on p and g in advance, so Alice need send only y_A to Bob instead of the triple (p, g, y_A). In some applications, such as IPsec, there are a small number of primes and generators that most implementations choose from, and Alice need send only an indication of which set she wishes to use, rather than the entire prime and generator.

ElGamal and Diffie-Hellman over Elliptic Curves

The ElGamal and Diffie-Hellman algorithms that we've discussed involve calculations over the finite field Z_p, using the normal field operations, such as addition, multiplication, and exponentiation. It is possible to define an elliptic curve over Z_p or GF(2ⁿ), and then implement the ElGamal and Diffie-Hellman algorithms as calculations on the points of the curve. The mathematics are considerably more demanding than what we have been using, so we will omit the details. A reasonably accessible introduction to elliptic curve cryptography and its application to Diffie-Hellman is in [Davis 2001].

The advantage of elliptic curve cryptography is that the discrete logarithm problem is considerably more difficult over an elliptic curve than it is in Z_p, so smaller values of p can be used, with a consequent increase in speed and decrease in the amount of data that needs to be exchanged between peers during key negotiation. For example, Diffie-Hellman over Z_p with a 1,024-bit prime has about the same security as Diffie-Hellman over an elliptic curve on the finite field GF(2ⁿ) with a prime of 185 bits [Doraswamy and Harkins 1999].