Diffie-Hellman key agreement

Diffie-Hellman protocol.

Diffie-Hellman key agreement is a technique [1] / protocol that allow to two parties establish a shared secret key by exchanging messages over an insecure open channel. The security of this protocol rests on the Diffie-Hellman problem and the problem of computing discrete logarithms.

This protocol need as input an number prime $p$ and a generator $g$ of $p$, that are known by everyone in the communication channel. We have two users, called Alice and Bob. Alice chooses a random secret $x, 1 < x < p - 1$ and computes $f(x) = g^x\mod p$, and Bob chooses a random secret $y, 1 < y < p - 1$ and computes $f(y) = g^y\mod p$.

Later both Alice and Bob shared their $f(x)$ and $f(y)$ to each other and computes $f(y)^x\mod p$ and $f(x)^y\mod p$, respectively. If the protocol was computes correctly, then $f(x)^y\mod p = f(y)^x\mod p$, that it will be the shared key of Alice and Bob.

Now I imagine that I am a man-in-the-middle who wants hack the communication channel of Alice and Bob, whose $p$ and $g$ are publicly known. Because the channel is insecure, I intercepted $f(x)$ and $f(y)$. Now I want search the values of $x$ and $y$ to obtain the shared key of Alice and Bob.

I know that $\textbf G = \mathbb(Z_{p} - 0, *)$. A brute-force attack to Diffie-Hellman protocol involves iterate the generator and computes $\forall k \in \textbf G: g^k \mod p$ until that the outputs be $f(x)$ or $f(y)$. If it matches to anyone of the two, then $k$ is $x$ or $y$, respectively. Now it is possible for me compute the shared key.

My own implementation of this protocol only receives as input the value of $p$ and computes on its own the generator $g$. Because I just want to show how the protocol works, the program chooses a random $x$ and $y$. Later my implementation hacks the protocol.

The full program (GitHub link) does the following:

• Primality test of $p$. If $p$ is prime, then the protocol continues.
• Computes all the generators of $p$ and chooses a random $g$.
• Chooses a random $x$ (Alice private key) and a random $y$ (Bob private key), $x \neq y$.
• Computes $f(x) = g^x\mod p$ and $f(y) = g^y\mod p$.
• Computes $f(x)^y\mod p$ and $f(y)^x\mod p$ (Alice and Bob shared key).
• If $f(x)^y\mod p = f(y)^x\mod p$, then this output is the $key$.
• $\forall k \in G$ computes $g^k \mod p$ until it matches $f(x)$ or $f(y)$.

Main function Function that computes $f(x)$, $f(y)$ (evaluarLlave) and the $key$ (construirLlave) Function that hacks the protocol Results References
[1] Menezes et. Al, "Handbook of Applied Cryptography", 1996