Fast Learner Module: Diffie-Hellman Key Exchange

Objective: 

To understand how the Diffie-Hellman key exchange works to derive a shared secret key across a public medium.

View

*Public Key Cryptography: Diffie-Hellman Key Exchange video *[5 mins] (for the transcript, click the transcript icon  on the YouTube page)

After viewing the video, use the following to practice and review: 

	Practice with the Diffie-Hellman Example Calculator
	Review questions

See Fast Learner Modules for additional modules.

Diffie-Hellman Key Exchange Resources

• Wikipedia article on Diffie-Hellman key exchange
• The original 1976 paper from IEEE Transactions on Information Theory
• Bing search for "Diffie-Hellman"
• Google search for "Diffie-Hellman"

Review Questions

1. What is the central problem that the Diffie-Hellman key exchange is trying to solve?

2. Describe how the Diffie-Hellman method uses a one-way function to easily create the secret key, but makes it very difficult for an eavesdropping attacker to determine the secret key.

3. What does the attacker (Eve) know?

4. Why can't the attacker (Eve) determine the secret key?

For the answers to these review questions, click here.

Answers to Review Questions

1.  What is the central problem that the Diffie-Hellman key exchange is trying to solve?

Answer:  How does a pair of communicators exchange public information and use that information to derive a mutual, secret key that cannot be determined by an attacker who intercepts the exchanged public information?

2.  Describe how the Diffie-Hellman method uses a one-way function to easily create the secret key, but makes it very difficult for an eavesdropping attacker to determine the secret key.

Answer: Alice and Bob determine a secret key through simple modular arithmetic, calculating (g^x mod p), in which p is the prime modulus and g is the cyclical generator.

Eve must determine the value of y based on known values of g, p, and (g^y mod p). This is difficult because of the relationship between g and p and the rules of modular arithmetic (g is a primitive root of p), especially when g and p are large numbers. This is known as the discrete logarithm problem.

3.  What does the attacker (Eve) know?

Answer:  

• p, the prime modulus (17 in the example)
• g, the cyclical generator (3 in the example)
• (g*^a* mod p) (15 in the example) (a is Alice's chosen exponent, which is 54 in the example)
• (g*^b* mod p) (16 in the example) (b is Bob's chosen exponent, which is 24 in the example)

4.  Why can't the attacker (Eve) determine the secret key?

Answer: To obtain the secret key, the attacker has to determine one of the following:

• a from the known result (g*^a* mod p). If she can determine a, then she can calculate the secret key from the formula (((g*^b* mod p)^a) mod p). From the example, the secret key is (16⁵⁴ mod 17) or 1.
• b from the known result (g*^b* mod p). If she can determine b, then she can calculate the secret key from the formula (((g*^a* mod p)^b) mod p). From the example, the secret key is (15²⁴ mod 17) or 1.

The attacker has to solve one of two discrete logarithm problems.

Note that the video does not make the following distinction:

(((g*^b* mod p)^a) mod p) = ((g*^b)^a* mod p) [by the rules of modular arithmetic]

((g*^b)^a* mod p) = (g*^ba* mod p)

Similarly,

(((g*^a* mod p)^b) mod p) = ((g*^a)^b* mod p) [by the rules of modular arithmetic]

((g*^a)^b* mod p) = (g*^ab* mod p) = (g*^ba* mod p)

Therefore, from the example, in which:

• p = 17
• g = 3
• (g*^a* mod p) = 15
• a = 54
• (g*^b* mod p) =16
• b = 24

From (((g*^b* mod p)^a) mod p) = ((g*^b)^a* mod p):

• ((16)⁵⁴ mod 17) = ((3²⁴)⁵⁴ mod 17) = 1

Note that this equation is not saying that 16⁵⁴ = (3²⁴)⁵⁴. It's saying that ((16)⁵⁴ mod 17) = ((3²⁴)⁵⁴ mod 17).

From (((g*^a* mod p)^b) mod p) = ((g*^a)^b* mod p):

• (((15)²⁴) mod 17) = ((3⁵⁴)²⁴ mod 17) = 1