Diffie Hellman

Diffie-Hellman Key Exchange The Definition The Diffie-Hellman is a key exchange protocol that allows two users to exchange a secret key over an insecure medium. The Requirements The system has got two parameters suppose p and g. Both of them are made public i.e. they are visible to all users in the system. Parameter p is a large prime number and parameter g (usually called a generator) is an integer less than p, with the following property: for every number n between 1 and p-1 inclusive, there is a power k of g such that n = gk mod p. The Users Two people suppose Alice and Bob who wish to establish a secure communications between them in an insecure circuit. The Process 1) The users agree on two large positive integers p and g with the stipulation that p is a prime number and g is a generator of p. 2) Alice randomly chooses another large positive integer, XA, which is smaller than p. XA will serve as Alice's private key. 3) Bob similarly chooses his own private key, XB. 4) Alice computes her public key, YA, using the formula YA = (g^XA) mod p. 5) Bob similarly computes his public key, YB, using the formula YB = (g^XB) mod p. 6) Alice and Bob exchange public keys over the insecure circuit. 7) Alice computes the shared secret key, k, using the formula k = (YB ^XA) mod p. 8) Bob computes the same shared secret key, k, using the formula k = (YA ^XB) mod p. 9) Alice and Bob communicate using the symmetric algorithm of their choice and the shared secret key, k, which was never transmitted over the insecure circuit.

Diffie-Hellman in ECC In case of elliptic curve cryptography, the Diffie-Hellman can be established in the following manner. The parameters Here the users (Alice & Bob) get settled with the following parameters which are considered to be visible to all in the network. a) A large prime integer q. b) Elliptic curve parameters (a, b) for y2 mod q = x3 + ax + b mod q that defines the elliptic group of points Eq(a, b). c) A base point G = (x1, y1) in Ep(a, b) is considered whose order is a very large value n. The Key Exchange 1) Alice selects an integer nA less then n. This is Alice’s private key. 2) Bob selects an integer nB less then n. This is Bob’s private key. 3) Alice generates a public key PA = nA x G; the public key is a point in Eq(a, b). 4) Bob generates a public key PB = nB x G; the public key is a point in Eq(a, b). 5) Alice generates the secret key K = nA x PB . ( Multiplying its private key with Bob’s public key.) 6) Bob generates the secret key K = nB x PA ; ( Multiplying its private key with Alice’s public key.) Calculations shown in steps 5 and 6 are same as shown below: nA x PB = nA x (nB x G) = nB x (nA x G) = nB x PA An Example Let the value of q be taken as 27, the parameters of the curve i.e. (a, b) be (1, 1) and lastly point G on curve be represented as (3, 10). Suppose Alice and Bob chooses 3 and 5 as their private keys respectively. Therefore PA = 3 x (3, 10) = (19, 5) which is Alice’s public key. PB = 5 x (3, 10) = (9, 16) which is Alice’s public key. Secret key for Alice is thus 3 x (9, 16) and that for Bob is 5 x (19, 5) Both 3 x (9, 16) and 5 x (19, 5) yields the same result (1, 16).