Cryptography

Diffie- Hellman Key Agreement Protocol

Diffie-Hellman Key Agreement protocol [7] can be used to exchange keys for a symmetric cryptosystem over an insecure channel

Setup

• p is a large prime number called the public prime

• s is a number in the range of 2 to p-1, called the public base

• Alice chooses a number a at random in the range of 2 to p-2, then calculates A = s^a mod p and sends it to Bob

• Bob chooses a number b at random in the range of 2 to p-2, then calculates B = s^b mod p and sends it to Alice

Key Retrieval

• Alice calculates k = B^a mod p = (s^b)^a mod p = s^ba mod p

• Bob calculates k = A^b mod p = (s^a)^b mod p = s^ab mod p

Now both Alice and Bob have the same key k and they can use it in a symmetric cryptosystem like DES. Since Alice knows a and B and Bob knows b and A,  both of them can calculate s^ab. But someone with the knowledge of p, s, A, B will not be able to calculate the key k

The Diffie- Hellman Problem

Find s^ab mod p from s^a and s^b in a time-efficient manner.

It is obvious that for an eavesdropper, Eve, to find the key k, she has to find a and b given s^a = A mod p and  S^b = B mod p . There is no such efficient algorithm to solve for a and b. The Diffie- Hellman problem is still an open question without an efficient solution. You might want to try to crack it, rest assured you and your algorithm will be more famous than any of the existing algorithms related to cryptography. Good luck!

Example

• Public prime p = 79

• Public base   s = 56

• Alice chooses a= 35

• Alice calculates A  = s^a mod p = (56)³⁵ mod 79 =  15366711764103772265936719131269189389773889471090594389426176 mod 79 = 24

• Bob chooses b= 12

• Bob calculates B  = s^b mod p  =  (56)¹² mod 79 = 951166013805414055936 mod 79 = 1

• Alice calculates key  k =  B^a mod p = (1)³⁵ mod 79 = 1 mod 79 = 1

• Bob calculates key k = A^b mod p  =  (24)¹² mod 79 = 36520347436056576  mod 79 = 1