Home | | Cryptography and Network Security | 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.

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, a2 mod p, … ap-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 ≡ ai 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 XA < q and computes YA = α XA mod q. Similarly, user B independently selects a random integer XB < q and computes YB = α

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 = (YB)XA mod q

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

These two calculations produce identical results.

K = (YB)XA mod q

= (α XB mod q)XA mod

q = (α XB)XA mod q

= (α XA)XB mod q

= (α XA mod q)XB mod

q = (YA)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 XD1 and XD2 and then computing the corresponding public keys YD1 and YD2.

Alice transmits YA to Bob.

Darth intercepts YA  and transmits YD1  to Bob. Darth also calculates K2 = (YA)XD2 mod q.

Bob receives YD1 and calculates K1 = (YD1)XE mod q. 5. Bob transmits XA to Alice.

Darth intercepts XA and transmits YD2 to Alice. Darth calculates K1 =D1 mod q.

Alice receives YD2 and calculates K2 = (YD2)XA 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 2m and elliptic curve parameters a and b. This defines the elliptic group of points Eq(a, b). Next, pick a base point G = (x1, y1) in Ep(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. Eq(a, b) and G are parameters of the cryptosystem known to all participants.

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

B similarly selects a private key nB and computes a public key PB.

A generates the secret key K = nA x PB. B generates the secret key K = nB x PA.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Cryptography and Network Security : Diffie-Hellman Key Exchange |