Alice and Bob perform Diffie-Hellman over a public channel. Eve observes g, p, g^a mod p, and g^b mod p. To compute the shared key g^{ab} mod p, what problem must Eve solve?
AThe integer factorization problem — Eve must factor p to recover a and b
BThe discrete logarithm problem — Eve must compute a from g^a mod p (or b from g^b mod p)
CThe Computational Diffie-Hellman (CDH) problem — Eve must compute g^{ab} mod p given g^a and g^b, without necessarily finding a or b individually
DThe RSA problem — Eve must find the private exponent d
The CDH problem is precisely: given g, g^a, g^b in a group, compute g^{ab}. This is believed hard in well-chosen groups. Note that CDH is potentially easier than the discrete logarithm problem (DLP) — if Eve could solve DLP, she could find a from g^a and compute (g^b)^a, but CDH might be solvable without finding either discrete logarithm. In practice, we use groups where both CDH and DLP are hard. The Decisional Diffie-Hellman (DDH) assumption — that (g^a, g^b, g^{ab}) is indistinguishable from (g^a, g^b, g^c) — is an even stronger assumption used to prove semantic security of ElGamal encryption.
Question 2 Short Answer
Diffie-Hellman by itself is secure against passive eavesdroppers but vulnerable to active man-in-the-middle attacks. Describe the attack.
Think about your answer, then reveal below.
Model answer: An active attacker Mallory intercepts the exchange. When Alice sends g^a, Mallory blocks it, picks her own secret m1, and sends g^{m1} to Bob. When Bob sends g^b, Mallory blocks it, picks m2, and sends g^{m2} to Alice. Now Alice computes key1 = g^{a*m2}, and Bob computes key2 = g^{b*m1}. Mallory knows both keys. She decrypts messages from Alice with key1, reads them, re-encrypts with key2, and forwards to Bob. Neither party detects the interception.
The vulnerability exists because basic DH provides no authentication — neither party can verify who they're communicating with. The fix is to authenticate the DH exchange using digital signatures (as in the Station-to-Station protocol), certificates (as in TLS), or pre-shared keys. Authenticated DH is the standard in all modern protocols.
Question 3 Short Answer
The Diffie-Hellman key exchange was published in 1976, one year before RSA. Why is it historically significant that DH solved key distribution without requiring a prior shared secret?
Think about your answer, then reveal below.
Model answer: Before DH, all known encryption required both parties to share a secret key in advance — the key distribution problem. If Alice and Bob wanted to communicate securely, they needed a secure channel to exchange keys first, creating a chicken-and-egg problem. DH solved this by allowing secure key agreement over a completely public channel, using only publicly known parameters. This breakthrough enabled secure communication between parties who had never met, which is the foundation of internet security (HTTPS, SSH, etc.).
The key distribution problem was considered the fundamental limitation of cryptography. DH showed that public-key techniques could solve it, opening the era of public-key cryptography. Every secure connection on the internet ultimately relies on some form of DH or its elliptic curve variant for session key establishment.
Question 4 True / False
Choosing a safe prime p = 2q + 1 (where q is also prime) for Diffie-Hellman is important because it ensures the group of order q has no small subgroups that would weaken the discrete logarithm problem.
TTrue
FFalse
Answer: True
If p - 1 has small prime factors, the multiplicative group mod p contains small subgroups. An attacker can exploit the Pohlig-Hellman algorithm to decompose the discrete logarithm into smaller problems in each subgroup. With p = 2q + 1, the order of the multiplicative group is p - 1 = 2q, and working in the subgroup of order q (a large prime) eliminates all small-subgroup attacks. This is why safe primes are standard for DH parameter selection.
Question 5 True / False
In Elliptic Curve Diffie-Hellman (ECDH), a 256-bit key provides security comparable to a 3072-bit classical DH key.
TTrue
FFalse
Answer: True
Elliptic curve groups lack the index calculus algorithms that accelerate discrete logarithms in multiplicative groups mod p. The best known attack on well-chosen elliptic curves is Pollard's rho, which runs in O(sqrt(n)) time where n is the group order. A 256-bit elliptic curve group provides approximately 128 bits of security (2^128 operations). Achieving 128-bit security with classical DH requires a ~3072-bit prime because the Number Field Sieve for discrete logarithms runs in sub-exponential time. This efficiency advantage makes ECDH the default choice in modern protocols like TLS 1.3.