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 *log _{b}x *=

*b*. The DLP takes this one step further by using modular arithmetic instead of normal arithmetic.

^{x}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* ≡ 2

^{212}

*mod*619 ≡ 521

*mod*619, and Bob computes

*B ≡ α*2

^{ b}mod p ≡^{136}

*619*

^{ }mod*≡*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 *K _{AB}*). Alice can combine Bob’s public key

*B*with her private key

*a*to derive the encryption key:

*K*≡

_{AB}*B*≡ 190

^{a}mod p^{212}

*mod*619 ≡ 30

*mod*619. Bob performs a similar computation:

*K*≡

_{AB}*A*≡ 521

^{b}mod p^{136}

*mod*619 ≡ 30

*mod*619. Thus, Alice and Bob now have the same encryption key,

*K*≡ 30

_{AB}*mod*619 (or more simply,

*K*= 30).[ii]

_{AB}

The key *K _{AB}* can be used to securely encrypt messages. For example, Bob can encrypt a message with the AES cipher using

*K*as the key. Alice can then decrypt Bob’s ciphertext using

_{AB}*K*. This whole process can happen

_{AB}*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 *K _{AB}* derived by DH. We could, for example, encrypt a message

*x*by calculating the following:

*y*≡

*x**

*K*

_{AB}*mod p*. We could then decrypt the ciphertext

*y*by multiplying it by the inverse of

*K*—remember that decryption is the inverse of encryption. We would calculate

_{AB}*x*≡

*y * K*. As it turns out, there’s a cryptosystem that follows a very similar process.

_{AB}^{-1}mod p

**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 *≡ 2

^{203}

*≡*

^{ }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*≡ 148

^{324}

*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*≡ 2

^{324 }

*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* ≡ *E*^{d}*mod* *p* ≡ 308^{203 }*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 *K _{AB}* without access to Alice and Bob’s private keys (

*a*and

*b*, respectively). This is possible, but Eve must compute

*a*≡

*log*, which she can use to compute

_{α }A mod p*K*≡

_{AB}*B*. 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

^{a}mod p*α*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*. Remember that Bob uses

_{α }E mod p*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 *K _{AB }*≡

*B*, but

^{a}mod p*B*≡

*α*. By substitution, we have

^{ b }mod p*K*≡

_{AB }*(α*, which is equivalent to

^{ b})^{a }mod p*K*≡

_{AB }*(α*. Recall that

^{ a})^{b }mod p*A*≡

*α*. So, by substitution,

^{ a}mod p*K*≡

_{AB}*A*. This is exactly what Bob computes. Hence, Alice and Bob compute the same encryption key

^{b}mod p*K*. QED

_{AB}[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 2^{80} steps to break an 80-bit integer. These square-root attacks need up to √2^{80} = 2^{40} 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 (*x _{1}*) but not the other (

*x*). Assume she also has their corresponding ciphertexts (

_{2}*y*and

_{1}*y*, respectively). Eve can compute

_{2}*x*≡

_{2}*y*for

_{2 }* y_{1}^{-1 }* x_{1 }mod p*any*plaintext message until Bob changes his secret exponent

*i*. That’s a huge security liability for Alice and Bob!