Diffie-Hellman Key Exchange

Diffie-Hellman key exchange is a method that allows two parties to securely share a secret key over a public channel. This shared secret key can be used for encrypted communication using Symmetric Cryptography.

Discrete Logarithm Problem (DLP)

According to the trapdoor property, it is computationally infeasible to compute the discrete logarithm equation below, where $g$, $p$ and $y$ are given, $g$ is a primitive root of $p$, and $p$ is extremely large (greater than 2048 bits to represent $p$). $y=g^x\mathrm{mod}p$

Key exchange process

The key exchange leverages the finite fields and primitive roots (generator) mathematical concepts.

1. Public parameters
   • Two numbers are agreed upon by both, which is known in the public:
     • A large prime number $p$ (a prime number is the one only divisible by 1 or itself)
     • A large prime root (generator) $g$
2. Private key selection
   • Alice choose a private key $a$, where $1\le a<p$
   • Bob choose a private key $b$, where $1\le b<p$
3. Public key computation
   • Alice computes her public key $X$ as: $X=g^a\mathrm{mod}p$
   • Bob computes his public key $Y$ as: $Y=g^b\mathrm{mod}p$
4. Public key exchange
   • Alice sends her public key $X$ to Bob
   • Bob sends his public key $Y$ to Alice
5. Shared secret key computation
   • Alice computes the shared secret key: $K=Y^a\mathrm{mod}p=(g^b\mathrm{mod}p{)}^a\mathrm{mod}p=(g^b{)}^a\mathrm{mod}p$
   • Bob computes the shared secret key: $K=X^b\mathrm{mod}p=(g^a\mathrm{mod}p{)}^b\mathrm{mod}p=(g^a{)}^b\mathrm{mod}p$

Both parties end up with the same secret value $K=g^{ab}\mathrm{mod}p$, which they can use as a shared key for symmetric encryption.

Security

• Discrete Logarithm Problem: The security of the Diffie-Hellman key exchange relies on the difficulty of the discrete logarithm problem. Given $g$, $p$, and $g^x\mathrm{mod}p$, it is computationally infeasible to determine aaa if $p$ is a large enough prime and $g$ is a suitable primitive root.
• Eavesdroppers: An eavesdropper who intercepts $g$, $p$, A, and B cannot determine the shared secret $K$ without solving the discrete logarithm problem, which is considered computationally hard.

Man-in-the-middle attack

The key exchange protocol is vulnerable to man-in-the-middle attack because it does not authenticate the participants. The solution to such vulnerability is to use Digital Signature and public-key certificate.

---

Back to parent page: Symmetric Cryptography

Cyber_Security Network_Security INFO2222 Key_Exchange DiffieHellman_Key_Exchange Symmetric_Cryptography CSEC3616 DLP