COSC3325 Program-2B Due: 4/19/2007

Diffie-Hellman Key Exchange Scheme

Backgrounds:

nFirst published Public-Key cryptosystem in 1976.

nA number of commercial products employ this technique.

nIts effectiveness and security depends on the difficulties of computing Discrete Logarithms.

nDiscrete Logarithm:

1. Each prime has one or more Primitive Roots less than itself.

Example: 19 has 2, 3, 10, 13, 14, and 15 as its P.R.

2 mod 19, 2² mod 19, 2³ mod 19, 2⁴ mod 19, …, and 2¹⁸ mod 19 cover {1,2,…,18}

2. The Discrete Logarithm of a number b for the base a (mod p)

Any integer b can be represented by:

b = r mod p where 0<=r<=p-1 for a given prime p.

Now, for a given primitive root a of this prime, we have a unique number d

(between 0 and p-1) such that b = a^d (mod p) where 0<= d <= (p-1)

3. This exponent d is called the “Index” or the D.L. of the number b for the base a (mod p).

Example:

For p=19 and a=2. 100 = 2¹⁶ (mod 19)

200 = 2¹⁷ (mod 19)

300 = 2¹¹ (mod 19) and 50 = 2¹⁵ (mod 19)

Key Exchange algorithm.

n Step-1: Choose two global public elements:

a prime p and a primitive root r of p.

You can use 997 as the prime p, but you need to find a primitive root of this

Prime.

n Step-2: User A public key generation.

Select private key X_a < p and calculate public key Y_a = r^Xa mod p

n Step-3: User B public key generation.

Select private key X_b < p and calculate public key Y_b = r^Xb mod p

n Step-4: User A Secret key generation:

K_a = Y_b^Xa mod p

n Step-5: User B Secret key generation:

K_b = Y_a^Xb mod p (Both keys, K_a and K_b should be the same.)

Output Requirements:

Your program should output the following:

1. The prime number used like 997 or any one else you used.

2. Its primitive root

3. User-A private key selected and public key calculated.

4. User-B private key selected and public key calculated.

5. User-A secret key calculated and User-B secret key calculated.

(They must be the same)