Diffie-Hellman protocol

Some theory....

This protocol is a key agreement protocol, and also is called exponential key agreement. This protocol was developed by Diffie-Hellman in 1976 and was published in the ground-breaking paper "New Directions in Cryptography.

This protocol allows two users to exchange a secret key over an insecure medium without any prior secrets. For this protocol it's necessary to use two system parameters p and g, this parameters are both public and may be used by all the users in a system. Parameter p is any prime number and parameter g (usually known as a generator) is an any integer that has to be less than p-1 inclusive. Also there is a property that must be satisfied: for every number n between 1 and p-1 inclusive, there is a power k of g such that n = g^k mod p.

Let's see an example to understand better.

Suppose Alice and Bob want to agree on a shared secret key using the Diffie-Hellman protocol. They proceed as follows: 

• First of all they have to agree in a prime number p and in a integer g less than p-1 inclusive. 
• Then, Alice generates a random private value x and Bob generates a random private value y. Both x and y are any integer and this values are private, this means that nobody has to know them. 
• After this, Alice sends a public value X that is g^x mod p and also Bob has to send a public value Y that is g^y mod p. They exchange this public values. 
• Finally, Alice calculates K = (Y^x)% p, and Bob computes K = (X^y)% p. If those are equal, Alice and Bob now have a shared secret key k.

Here is an image that explains what I said above:

We can think that this protocol is vulnerable because p and g are public, but the truth is that even if the attacker knew these values and also captures the messages, he won't be able to know the secret key. This protocol can be broken if we use small values for p and g but current implementations of this protocol use very large numbers that prevents an attack

Exercise for this week

In this assignment we have to hack the Diffie-Hellman protocol. Two classmates (Pedro Miguel and Alejandro Avendaño) were Alice and Bob and I act as an eavesdropper (let's call me Eve); they encrypt their "message" using the following data:

• P = 13
• g = 9
• Y = 1
• X= 3

The formulas that I can use to hack this protocol are:

• X = (g^x)%p
• Y = (g^y)%p
• K = (Y^x)%p
• K = (X^y)%p

The goal was to recover x and y and K

Well to hack this protocol I used the brute force attack strategy and also some reverse engineering.

• First, I calculate X and Y.

n = (9²) % 13

n = 81 % 13

n = 3 = X

n = (9³) % 13

n = 729 % 13

n = 1 = Y

With this two calculates I thought that I have hacked my classmates because:

(Y^x)%p = (X^y)%p

(1²)%13 = (3³)%13

1 = 1

But I get x wrong, so I did more calculates

n = (9⁴) % 13

n = 6561 % 13

n = 9

n = (9⁵) % 13

n = 59049 % 13

n = 3 = X

I found that also x = 5 gets the same K, and know it was correct!

(Y^x)%p = (X^y)%p

(1⁵)%13 = (3³)%13

1 = 1

Sources

• rsa.com
• mathworld.wolfram
• javiercampos