Last time, we explored the RSA Cryptosystem. We observed that its security is reliant upon the difficulty of factoring large integers, but advances in computing are making this simplistic approach untenable. To make RSA secure against these advances, we must keep increasing the number of bits we use—upwards of 4096 bits and beyond. At some point, the number of bits we need will exceed our ability to use them effectively and efficiently. That said, big integers are still critical to today’s asymmetric ciphers.
Big integers aside, the other major problem with RSA is that it can be made vulnerable. To use RSA, we must exchange a public key, but this public key can be used to break the entire system relatively easily. That’s a major security liability. The goal, therefore, is to determine a system to securely exchange keys—this is the perennial problem for encryption. There are at least two solutions to this problem: Diffie-Hellman Key Exchange (DH) and the ElGamal Cryptosystem.
The Curious Case of the Discrete Logarithm
Before we dive in, let’s take a quick look at the underlying mathematics. Rather than rely only on big integers, DH exploits the difficulty of the Discrete Logarithm Problem (DLP). As the name suggests, we are concerned with discrete logarithms. We normally define a logarithm with base b such that logbx = bx. The DLP takes this one step further by using modular arithmetic instead of normal arithmetic.
The DLP can be defined quite simply. Suppose we’re given a large prime integer p, a nonnegative integer β, and a primitive element α. To solve the DLP, we must find an x such that β ≡ α x mod p. This may seem simple, but it’s actually computationally difficult to solve for sufficiently large integers. How does the DLP relate to encryption?
Diffie-Hellman Key Exchange
Although not a form of encryption, Diffie-Hellman Key Exchange is an asymmetric method to exchange keys. Alice and Bob do not directly share public keys as with RSA. Rather, Alice and Bob exchange key fragments derived from common, public parameters. Those fragments are then used to derive the same encryption key on either end. Without the DLP, though, DH wouldn’t be secure (more on this later). Let’s see how Alice and Bob may exchange keys using DH.
Alice and Bob start by agreeing upon a large prime integer p and a nonnegative integer α. These can come from a trusted public source, or Alice and Bob can publish them for anyone to use. Suppose Alice and Bob agree upon p = 619 and α = 2.
Next, Alice and Bob independently choose their private keys. Alice chooses a nonnegative integer a less than p, and Bob chooses a nonnegative integer b less than p.[i] These are Alice and Bob’s respective private keys. Suppose Alice chooses a = 212 , and Bob chooses b = 136. Bear in mind that Alice doesn’t know b, and Bob doesn’t know a. Alice and Bob use these private keys to compute their respective public keys.
Alice and Bob use modular exponentiation to compute the public keys. Alice computes A ≡ α a mod p ≡ 2212 mod 619 ≡ 521 mod 619, and Bob computes B ≡ α b mod p ≡ 2136 mod 619 ≡ 190 mod 619. Alice’s public key is A = 521, and Bob’s public key is B = 190. Up to this point, Alice and Bob can’t communicate securely with each other because they’ve yet to exchange public keys. Alice sends A to Bob, and Bob sends B to Alice. These public keys are meaningless on their own, so Alice and Bob must complete one more step.
The final step of DH establishes the actual encryption key (call it KAB). Alice can combine Bob’s public key B with her private key a to derive the encryption key: KAB ≡ Ba mod p ≡ 190212 mod 619 ≡ 30 mod 619. Bob performs a similar computation: KAB ≡ Ab mod p ≡ 521136 mod 619 ≡ 30 mod 619. Thus, Alice and Bob now have the same encryption key, KAB ≡ 30 mod 619 (or more simply, KAB = 30).[ii]
The key KAB can be used to securely encrypt messages. For example, Bob can encrypt a message with the AES cipher using KAB as the key. Alice can then decrypt Bob’s ciphertext using KAB. This whole process can happen without Alice and Bob having ever publicly exchanged their encryption key. This solves the key-exchange problem.
We would really like to develop an asymmetric encryption scheme that exploits the DLP and DH. One option is to use the encryption key KAB derived by DH. We could, for example, encrypt a message x by calculating the following: y ≡ x * KAB mod p. We could then decrypt the ciphertext y by multiplying it by the inverse of KAB—remember that decryption is the inverse of encryption. We would calculate x ≡ y * KAB-1 mod p. As it turns out, there’s a cryptosystem that follows a very similar process.
The ElGamal Cryptosystem
The ElGamal Cryptosystem is a popular approach to DLP-based encryption and is very similar to DH in principle. We’ve already seen how DH works, so let’s see how ElGamal is different.
Suppose Bob wants to communicate with Alice using ElGamal. The first step is for Alice to establish her public and private keys. She chooses a large prime integer p and a primitive element α.[iii] Suppose Alice chooses p = 421 and α = 2. She then chooses a nonnegative integer d less than p.[iv] Let’s say she chooses d = 203 (her private key). Next, she computes β ≡ α d mod p ≡ 2203 mod 421 ≡ 148 mod 421. Alice can send her public key β = 148 to Bob. However, since Bob doesn’t know p and α, Alice must also send these. So, she sends (β, p, α) = (148, 421, 2) to Bob.
Now it’s Bob’s turn to encrypt his message using Alice’s public key. If Bob wants to encrypt his message “HELLO”, he’ll use the decimal equivalent: {72, 69, 76, 76, 79}. First, he chooses a secret, random nonnegative integer i less than p.[v] Let’s say Bob chooses i = 324. Next, he computes a masking key: M ≡ β i mod p ≡ 148324 mod 421 ≡ 354 mod 421. He uses the masking key to encrypt his message: y ≡ x * M mod p. His ciphertext will be the sequence y = {228, 8, 381, 381, 180}. Bob could stop here, but he doesn’t want to send his masking key directly to Alice.[vi] Rather, he wants to obscure it in some way to preserve security.
Bob wants to keep his masking key secret. So, he computes an ephemeral key: E ≡ α i mod p ≡ 2324 mod 421 ≡ 308 mod 421. The masking and ephemeral keys should change each time Bob sends a message to Alice because he should choose a new i each time. Bob sends his ciphertext y and ephemeral key E to Alice so she can decrypt his message.
Recall that Bob used his masking key M to encrypt his message. Alice doesn’t have M, but she does have Bob’s ephemeral key E. Luckily for Alice, she can compute M by using E and d. That is, Alice computes M ≡ Ed mod p ≡ 308203 mod 421 ≡ 354 mod 421. Since decryption is the inverse of encryption, Alice must use the inverse of M to decrypt Bob’s message. In our example, M-1 ≡ 377 mod 421.[vii] She computes x ≡ y * M-1 mod p. This gives her Bob’s decrypted message, all without them having to directly exchange the encryption key.[viii]
There are a number of advantages to ElGamal. First, ElGamal is actually intended for encryption, whereas DH is intended for just key exchange. Second, Alice’s public key β is fixed, so she doesn’t need to compute a new one for each person with whom she communicates. Third, Alice chooses p and α, which eliminates the need for two people to agree upon these values. Finally, because Bob computes a new i each time he encrypts, the same plaintext will produce different ciphertexts, which reduces the likely success of known-plaintext attacks.
Security and Alternatives
We’ve established Diffie-Hellman Key Exchange and the ElGamal Cryptosystem on the assumption that the Discrete Logarithm Problem is computationally difficult. But is that a safe assumption? Does the DLP really make DH and ElGamal secure? The short answer: Yes, to an extent.
With DH, the attacker Eve has access to the public parameters (α and p) and Alice and Bob’s public keys (A and B). The problem for Eve is to compute the encryption key KAB without access to Alice and Bob’s private keys (a and b, respectively). This is possible, but Eve must compute a ≡ logα A mod p, which she can use to compute KAB ≡ Ba mod p. In effect, she must solve the DLP. Remember that computers aren’t great at handling large integers, so one solution is to choose sufficiently large integers for α and p to make Eve’s computations temporally impractical.[ix]
The same applies to the ElGamal Cryptosystem. Eve doesn’t know Alice and Bob’s private keys (d and i, respectively), but she does know β, p, and α. Eve could compute d ≡ logα β mod p, which would allow her to compute M after Bob sends E to Alice. Alternatively, Eve could compute i ≡ logα E mod p. Remember that Bob uses i to compute M and E. Unfortunately for Bob, Eve can use her computed i to solve for M and therefore break his communications with Alice. As with DH, Alice and Bob can mitigate this attack by choosing sufficiently large integers (e.g., 2048 bits). However, this is only one attack in Eve’s arsenal.
A more realistic fault in ElGamal lies in the nature of the private exponent i. Ideally, Bob would use a different random i for each message he encrypts. Sometimes this doesn’t happen, either due to human error or nonrandomness. Eve may observe that E doesn’t change each time Bob communicates with Alice. Since E is dependent upon i, Eve may deduce that i isn’t changing. Recall that M (the actual encryption key) also depends upon i. If i isn’t changing, then M isn’t changing either! Eve may use this information to execute a known-plaintext attack to break Alice and Bob’s communications.[x]
Not all hope is lost. Fortunately, these cryptographic schemes can be difficult to break using commonly available computers. Although quantum computers represent a looming threat, they don’t quite yet pose a real concern. Nevertheless, best practice isn’t to rely on one encryption scheme or another; rather, we should combine our securest symmetric and asymmetric schemes. This is an imperfect solution, however. Until we figure out a way to realize the perfect secrecy of the One-Time Pad, we’ll have to rely upon these imperfect schemes.
[i] Specifically, Alice and Bob choose a, b ∈ {2, 3, …, p-2}.
[ii] You may be questioning the legitimacy of this claim. Well, we can mathematically prove the result. Alice computes KAB ≡ Ba mod p, but B ≡ α b mod p. By substitution, we have KAB ≡ (α b)a mod p, which is equivalent to KAB ≡ (α a)b mod p. Recall that A ≡ α a mod p. So, by substitution, KAB ≡ Ab mod p. This is exactly what Bob computes. Hence, Alice and Bob compute the same encryption key KAB. QED
[iii] Unlike in Diffie-Hellman Key Exchange, p and α are not public parameters in ElGamal. Bob doesn’t know which p and α Alice chooses.
[iv] Similarly to Diffie-Hellman Key Exchange, Alice actually chooses d ∈ {2, 3, …, p-2}.
[v] Again, Bob actually chooses i ∈ {2, 3, …, p-2}.
[vi] Remember that this is one of the weaknesses of RSA. If we have the modulus and public exponent, we can use them to discover the private key.
[vii] We can find this by determining the modular multiplicative inverse.
[viii] Just as with Diffie-Hellman Key Exchange, we can mathematically prove this result. The process is similar, and we’ll leave it as an exercise for the reader.
[ix] Note that no encryption system (except the One-Time Pad) is perfectly secure. For Diffie-Hellman Key Exchange and ElGamal, there are algorithms that can solve the Discrete Logarithm Problem in square-root time. The Baby-step, Giant-step Algorithm and Pollard’s Rho Method are much faster than naïve bruteforce attacks. By way of comparison, a bruteforce attack would need up to 280 steps to break an 80-bit integer. These square-root attacks need up to √280 = 240 steps, which is feasible on today’s computers. The point here is that we can’t necessarily stop these attacks, but we can delay them by choosing sufficiently large integers.
[x] Assume Eve knows one plaintext (x1) but not the other (x2). Assume she also has their corresponding ciphertexts (y1 and y2, respectively). Eve can compute x2 ≡ y2 * y1-1 * x1 mod p for any plaintext message until Bob changes his secret exponent i. That’s a huge security liability for Alice and Bob!
