Diffie–Hellman key exchange

Diffie–Hellman key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman.

The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p–1.

Step 1: Both users publicly agree to use the value of the prime number, p, and the primitive root (or the base), g.

Step 2: The users, secretly choose their respective secret integer values, a and b.

Step 3: Subsequently, they calculate g^a (mod p) and g^b (mod p) respectively and share with each other.

Step 4: At the end, both calculate the key by taking the modular exponentiation with the received value as the base and their respective secret integer values (a, b) as exponent.

Difficulty for Eavesdropper : The protocol is considered secure against eavesdroppers if p and g are chosen properly. In particular, p must be large. The eavesdropper has to solve the Discrete Logarithm problem to obtain a and b from g^a (mod p) and g^b (mod p) respectively. This is currently considered difficult for large p. An efficient algorithm to solve the discrete logarithm problem would make it easy to compute a or b and solve the Diffie–Hellman problem, making this and many other public key cryptosystems insecure.

Conclusion: Thus using primitive roots the users can generate a secret key over a public channel.

References: Wikipedia