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, a^{2}
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 ^{i} 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_{1}, y_{1})
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}.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security : Diffie-Hellman Key Exchange |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.