Question

: Explain how the Diffie-Hellman key exchange algorithm works. For ease of grading, describe the protocol between “Alice” and “Bob” and use the notation from your book: p, g, dA (for Alice’s private key), eA (for Alice’s public key), etc. Show what is calculated, by whom it is calculated, how it is calculated, what is sent to the other party, what is kept secret, and any constraints on these values. For example, g has a particular property with respect to to p. Explain what this property means/does, even if you do not recall the name for this type of value. I’ll get you started: Alice and Bob share a number p and an integer g such that g p and g is a of p. This means that g ..

Answer 1

The heart and soul of Diffie-Hellman algorithm is Modular Arithmetic. (As a simple example, modulus of two numbers (3 % 2) gives you the remainder of (3 / 2), i.e., 1).

Let me divide the problem into a series of simple numbered steps:

1. First, Alice and Bob agrees publicly to a Prime Modulus(p) and a Generator(g):

A prime modulus can be any reasonable prime number. We select the prime number because it can't be further divided into smaller numbers.

There's a constraint imposed on the generator. The selected generator needs to be a primitive root of prime number selected.

A primitive root(g) of a prime number (p) is any number such that : 0 <= ((g^n)%p) < p. N is an integer. This is the most important point to understand. If the generator(g) is raised to any integer, it should always be the range [0, p).

Lets take p = 5 and g = 3 as an example.

2. Now, Alice generates a random private number, dA(eg: 2) and sends the result (g^dA) % p, i.e.,((3^2) % 5 == 4) to Bob publicly. Let A = 4(result)

3. Next, Bob selects his private random number dB(eg: 7) and sends the result (g^dB) % p, i.e., ((3^7) % 5 == 2) to Alice publicly. Let B = 2(result)

4. Now, Alice takes Bob's result, which was sent publicly and raises it to the power of it's private number and performs a modulus operation with the prime modulus(p): (B^dA) % p, i.e., (2^2)%5 == 4

5. Now, Bob takes Alice's public result and raises it to the power of it's private number and performs modulus operation with the prime modulus(p):  (A^dB) % p, i.e., (4^7)%5 == 4.

You can notice that they both arrived at the same secret number 4. Notice this:

Alice's Calculations:

(B^dA) % p = (((g^dB)%p) ^dA) % p = ((g ^ dB)^dA) %p = g ^(dB*dA), i.e.,

(3^7)^2 % 5 == (3 ^ 14) % 5 == 4

Bob's Calculations:

(A^dB) % p = (((g^dA)%p) ^dB) % p = ((g ^ dA)^dB) %p = g ^(dA*dB), i.e.,

(3^2)^7 % 5 == (3 ^ 14) % 5 == 4

You can see in the above illustration that even though it looks like the arithmetic operations are performed using different numbers, both Alice and Bob finally end up with the same operation (3 ^ 14) % 5 == 4. '4' Here is the secret key that is used to decrypt the message communicated.

Diffie-Hellman Key exchange is a discrete logarithmic problem and with very large numbers, it will become impossible to crack the encryption.

Hope this explanation helped you understand the problem a little better :)