DIFFIE-HELLMAN KEY EXCHANGE
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 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)
exponent „i‟ is referred to as discrete logarithm. With this background, we can
key exchange as follows:
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
side. User A computes the key as K = (YB)XA mod q
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
= (α XA)XB
= (α XA
mod q)XB mod
q = (YA)XB
result is that two sides have exchanged a secret key.
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
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:
prepares for the attack by generating two random private keys XD1
and XD2 and then computing the corresponding public keys YD1
transmits YA to Bob.
intercepts YA and transmits YD1 to Bob. Darth also calculates K2 = (YA)XD2
receives YD1 and calculates K1 = (YD1)XE
mod q. 5. Bob transmits XA to Alice.
intercepts XA and transmits YD2 to Alice. Darth
calculates K1 =D1 mod q.
receives YD2 and calculates K2 = (YD2)XA
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.
future communication between Bob and Alice is compromised in the following way:
sends an encrypted message M: E(K2, M).
intercepts the encrypted message and decrypts it, to recover M.
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.
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 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
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
similarly selects a private key nB and computes a public key PB.
generates the secret key K = nA x PB. B generates the
secret key K = nB x PA.