Cryptography: Diffie-Hellman Key Exchange

Topics

• Extended Euclidean Algorithm
• Modular Arithmetic
• Diffie-Hellman Key Exchange 🢀
• Public Key Cryptography

Introduction

Suppose that Alice wants to communicate with Bob over an unsecure channel such that nobody can read the messages. So, she encodes her message M using some (public) encryption method E and a secret key K to produce a cipher text C :

Bob receives the cipher text C and decrypts it using the corresponding (public) decryption method D to get the plain message M :

The problem is how can Alice and Bob agree on the common key. In the past the key exchange had to occur over a special additional secure channel. In fact, it is difficult to imagine that the key agreement is indeed possible over the unsecure channel.

In 1976, Whitfield Diffie and Martin Hellman published a radically new method for the key exchange. Their algorithm even intialized the public key cryptography which is indispensable in modern digital communication. The method is based on preliminary studies of Ralph Merkle and should perhaps be called Diffie-Hellman-Merkle Key Exchange.

Diffie-Hellman Key Exchange

The basic protocol works like this:

1. Alice and Bob exchange publicly two prime numbers g and p.
2. Alice chooses a secret number a, computes
   
   A = g^a mod p
   and sends A to Bob.
3. Bob chooses a secret number b, computes
   
   B = g^b mod p
   and sends B to Alice.
4. Alice receives B and computes using her secret number a
   
   B^a mod p = (g^b mod p)^a = g^ba mod p = g^ab mod p = K.
5. Bob receives A and computes using his secret number b
   
   A^b mod p = (g^a mod p)^b = g^ab mod p = K.
6. Alice and Bob possess the same number K
   
   K = g^ab mod p.
   that becomes their secret key K.

Security

The attacker Mallory got g, p, A, B . He can compute K only if he can compute a from

(and similarly b from B = g^b mod p).

This is the discrete logarithm problem, which is computationally infeasible for large p. Computing the discrete logarithm of a number modulo p takes roughly the same amount of time as factoring the product of two primes the same size as p, which is what the security of the RSA public cryptosystem relies on. Thus, the Diffie-Hellman protocol is roughly as secure as RSA.
Current guidelines suggest that the prime p is greater than 2048 bits, i.e. p > 2²⁰⁴⁸ , the number g is relatively prime to p and approximately p/2.

More on security:

• Stackexchange