Diffie-Hellman Key Exchange

DIFFIE-HELLMAN KEY EXCHANGE

The purpose of the algorithm is to enable two users to exchange a key securely that can then be used for subsequent encryption of messages.

The Diffie-Hellman algorithm depends for its effectiveness on the difficulty of computing discrete logarithms. First, we define a primitive root of a prime number p as one whose power generate all the integers from 1 to (p-1) i.e., if „a‟ is a primitive root of a prime number p, then the numbers a mod p, a² mod p, … a^p-1 mod p are distinct and consists of integers from 1 to (p-1) in some permutation. For any integer „b‟ and a primitive root „a‟ of a prime number „p‟, we can find a unique exponent „i‟ such that

b ≡ aⁱ mod p, where 0 ≤ i ≤ (p-1)

The exponent „i‟ is referred to as discrete logarithm. With this background, we can define Diffie

Hellman key exchange as follows:

There are publicly known numbers: a prime number „q‟ and an integer α that is primitive root of q. suppose users A and B wish to exchange a key. User A selects a random integer X_A < q and computes Y_A = α ^XA mod q. Similarly, user B independently selects a random integer X_B < q and computes Y_B = α

^XB  mod q. Each side keeps the X value private and makes the Y value available publicly to the

other side. User A computes the key as      K = (Y_B)^XA mod q

and User B computes the key as       K = (Y_A)^XB mod q

These two calculations produce identical results. 

K = (Y_B)^XA mod q

= (α ^XB mod q)^XA mod

q = (α ^XB)^XA mod q

= (α ^XA)^XB mod q

= (α ^XA mod q)^XB mod

q = (Y_A)^XB mod q

The result is that two sides have exchanged a secret key.

The security of the algorithm lies in the fact that, while it is relatively easy to calculate exponentials modulo a prime, it is very difficult to calculate discrete logarithms. For large primes, the latter task is considered infeasible.

The protocol depicted in figure is insecure against a man-in-the-middle attack. Suppose Alice and Bob wish to exchange keys, and Darth is the adversary. The attack proceeds as follows:

Darth prepares for the attack by generating two random private keys X_D1 and X_D2 and then computing the corresponding public keys Y_D1 and Y_D2.

Alice transmits Y_A to Bob.

Darth intercepts Y_A  and transmits Y_D1  to Bob. Darth also calculates K2 = (Y_A)^X_D2 mod q.

Bob receives Y_D1 and calculates K1 = (Y_D1)^X_E mod q. 5. Bob transmits X_A to Alice.

Darth intercepts X_A and transmits Y_D2 to Alice. Darth calculates K1 =D1 mod q.

Alice receives Y_D2 and calculates K2 = (Y_D2)^X_A mod q.

At this point, Bob and Alice think that they share a secret key, but instead Bob and Darth share secret key K1 and Alice and Darth share secret key K2.

All future communication between Bob and Alice is compromised in the following way:

Alice sends an encrypted message M: E(K2, M).

Darth intercepts the encrypted message and decrypts it, to recover M.

Darth sends Bob E(K1, M) or E(K1, M'), where M' is any message. In the first case, Darth simply wants to eavesdrop on the communication without altering it.

In the second case, Darth wants to modify the message going to Bob. The key exchange protocol is vulnerable to such an attack because it does not authenticate the participants. This vulnerability can be overcome with the use of digital signatures and public-key certificates.

Analog of Diffie-Hellman Key Exchange

Key exchange using elliptic curves can be done in the following manner. First pick a large integer q, which is either a prime number p or an integer of the form 2^m and elliptic curve parameters a and b. This defines the elliptic group of points E_q(a, b). Next, pick a base point G = (x₁, y₁) in E_p(a, b) whose order is a very large value n. The order n of a point G on an elliptic curve is the smallest positive integer n such that nG = O. E_q(a, b) and G are parameters of the cryptosystem known to all participants.

A selects an integer n_A less than n. This is A's private key. A then generates a public key P_A = n_A x G; the public key is a point in Eq(a, b).

B similarly selects a private key n_B and computes a public key P_B.

A generates the secret key K = n_A x P_B. B generates the secret key K = n_B x P_A.