Overview

Unlike RSA, where you can send messages of your choice, the DHKE is used to generate a secret number shared between Alice and Bob. This shared secret is then used as the key for a symmetric cryptosystem like AES.
The Key Exchange
A large prime ppp
 and a generator g∈Fp,g≠0g \in \mathbb{F}_p, g \neq 0g∈Fp​,g=0
 are made public.
Alice and Bob choose their secret integers aaa
 and bbb
 respectively. They then compute the following:
A=gamod  pB=gbmod  pA = g^a \mod p \\
B = g^b \mod pA=gamodpB=gbmodp
These numbers AAA
 and BBB
 are exchanged between Alice and Bob over a public channel. Once the other person's number is received, they then put it to the power of their secret integer, i.e. Alice computes BaB^aBa
 and Bob computes AbA^bAb
, both modulo ppp
. Note that:
Ba=(gb)a=gab=(ga)b=AbB^a = (g^b)^a = g^{ab} = (g^a)^b = A^bBa=(gb)a=gab=(ga)b=Ab
This means that once they do this, they are in possession of the same number, which they can then use as a shared secret.
The Discrete Logarithm Problem
The safety of the Diffie-Hellman Key Exchange is grounded on he difficulty of solving the discrete logarithm problem - the difficulty of computing xxx
 given
gx≡amod  pg^x \equiv a \mod pgx≡amodp
You can see this in Overview presented above - the values gamod  pg^a \mod pgamodp
 and gbmod  pg^b \mod pgbmodp
 are sent over a public channel, but because we cannot solve the DLP efficiently an attacker is unable to retrieve aaa
 or bbb
. We say that the DLP is DHKE's trapdoor function.
As you may expect from here, many attacks on Diffie-Hellman rely on situations in which you can efficiently compute the discrete logarithm.
Last modified 1yr ago