Diffie-Hellman key exchange

History

Published in 1976 by Whitfield Diffie and Martin Hellman, the Diffie-Hellman key exchange is the first public key cryptography algorithm. Previously, in order to communicate securely over an insecure communications channel, a secret had to be shared between the parties involved out of band (for example by trusted courier on paper). This new algorithm allowed for two parties who have no prior relationship to establish such a shared secret over the existing insecure channel.

Axioms

The DH key exchange assumes that the discrete logarithm problem is indeed hard. That is, modulus exponentation is fast to compute by slow to reverse.

In addition, this key exchange relies on generating some random numbers. This process must have sufficient real randomness to be considered secure. This is because any predictability can greatly reduce the search space of brute-force attacks

Algorithm

Assume there are two parties, Alice and Bob, who wish to establish a shared secret with eachother. They can only communicate over an insecure communications channel on which a third party, Eve, is actively listening.

1) Alice & Bob will publically agree on a large prime \(p\) and generator \(g\). Typically the prime will be on the order of 2048 bits to be considered secure, while the generator may be small while remaining secure. Eve will be aware of these values.

2) Alice generates a random number \(a\), and Bob generates a random number \(b\). These are the private keys and will not be shared.

3) Alice computes her corresponding public keys using the formula: \(A = g^a\ mod\ p\). Likewise Bob computes his public key using \(B = g^b\ mod\ p\)

4) Alice & Bob transmit their public keys \(A\) and \(B\) over the insecure communications channel. Eve will also learn of these values.

5) Alice can now calculate the shared secret as \(s = g^{aB}\ mod\ p\)

6) Bob can calculate the shared secret as \(s = g^{bA}\ mod\ p\)

7) Eve is unable to calculate the shared secret while only knowing \(p, g, A, B\)