Question

Suppose I a black hat hacker. Can you think of a way to that I can figure out the secret key that Alice and Bob are calculating. Suppose that I know how the algorithm works as well as the values used for p and g.

Answer 1

Diffie–Hellman key exchange

The Diffie–Hellman key exchange algorithm solves the following dilemma. Alice and Bob want to share a secret key for use in a symmetric cipher, but their only means of communication is insecure. Every piece of information that they exchange is observed by their adversary Eve. How is it possible for Alice and Bob to share a key without making it available to Eve? At first glance it appears that Alice and Bob face an impossible task. It was a brilliant insight of Diffie and Hellman that the difficulty of the discrete logarithm problem for F ∗ p provides a possible solution. The first step is for Alice and Bob to agree on a large prime p and a nonzero integer g modulo p. Alice and Bob make the values of p and g public knowledge; for example, they might post the values on their web sites, so Eve knows them, too. For various reasons to be discussed later, it is best if they choose g such that its order in F ∗ p is a large prime.

The next step is for Alice to pick a secret integer a that she does not reveal to anyone, while at the same time Bob picks an integer b that he keeps secret. Bob and Alice use their secret integers to compute

A ≡ g ^a (mod p) , Alice computes this and

B ≡ g ^b (mod p) , Bob computes this .

They next exchange these computed values, Alice sends A to Bob and Bob sends B to Alice. Note that Eve gets to see the values of A and B, since they are sent over the insecure communication channel.

Finally, Bob and Alice again use their secret integers to compute A ' ≡ B ^a (mod p) Alice computes this and

B ' ≡ A ^b (mod p) ,Bob computes this .

The values that they compute, A' and B' respectively, are actually the same, since A ' ≡ B ^a ≡ (g ^{b ) a} ≡ g ^ab ≡ (g ^{a ) b} ≡ A ^b ≡ B ' (mod p).

Example - Alice and Bob agree to use the prime p = 941 and the primitive root g = 627. Alice chooses the secret key a = 347 and computes A = 390 ≡ 627³⁴⁷ (mod 941). Similarly, Bob chooses the secret key b = 781 and computes B = 691 ≡ 627⁷⁸¹ (mod 941). Alice sends Bob the number 390 and Bob sends Alice the number 691. Both of these transmissions are done over an insecure channel, so both A = 390 and B = 691 should be considered public knowledge. The numbers a = 347 and b = 781 are not transmitted and remain secret. Then Alice and Bob are both able to compute the number 470 ≡ 627^347·781 ≡ A ^b ≡ B ^a (mod 941), so 470 is their shared secret. Suppose that Eve sees this entire exchange. She can reconstitute Alice’s and Bob’s shared secret if she can solve either of the congruences 627^a ≡ 390 (mod 941) or 627^b ≡ 691 (mod 941), since then she will know one of their secret exponents. As far as is known, this is the only way for Eve to find the secret shared value without Alice’s or Bob’s assistance. Of course, our example uses numbers that are much too small to afford Alice and Bob any real security, since it takes very little time for Eve’s computer to check all possible powers of 627 modulo 941. Current guidelines suggest that Alice and Bob choose a prime p having approximately 1000 bits (i.e., p ≈ 2 1000) and an element g whose order is prime and approximately p/2. Then Eve will face a truly difficult task. In general, Eve’s dilemma is this. She knows the values of A and B, so she knows the values of g a and g b . She also knows the values of g and p, so if she can solve the DLP, then she can find a and b, after which it is easy for her to compute Alice and Bob’s shared secret value g ab. It appears that Alice and Bob are safe provided that Eve is unable to solve the DLP, but this is not quite correct. It is true that one method of finding Alice and Bob’s shared value is to solve the DLP, but that is not the precise problem that Eve needs to solve. The security of Alice’s and Bob’s shared key rests on the difficulty of the following, potentially easier, problem.