Diffie-Hellman

Introduction

In this post you can find an implementation of Diffie-Hellman protocol as well as a brute-force attack against it, which try to recover a private key.

At least in this method has 2 users that will establish a communication in an insecure channel. First they need to generate their keys (never share with someone) and a shared private key. Key is necessary for interchange information in a "secure" way.[1]

I said secure, because the security is based in the computational complexity to realize the inverse operation.

Functions

First Alice and Bob choose together a prime number (p). The value of p is between numMin(implementation used 1000000) and numMax(99999999). The reason for I used that numbers is because when I used larger numbers time increased.
This table shows an example of time using differents min,max numbers.

min	max	time users*	time hacker*	x	y
1000000	99999999	0.000108957290649	13.1109771729	2985883	5265807
10000000	999999999	8.70227813721e-05	1.526652813	110939030	188011157
100000000	9999999999	0.000119924545288	312.937700033	4988719808	3646574494
1000000000	99999999999	0.000176906585693	? more than 20 minutes	3254651267	7594893842

*time in seconds

def genNumPriRan(numMin,numMax):
    while True:
        num = random.SystemRandom().randint(numMin,numMax)
        if esNumeroPrimo(num) == 1:
            return num
 

After they will choose a generator of p (g ∈ Zp). The way to create a generator is:

1. Get the factors of g (Fi, where i = n-element)
2. g raised to the power of each factors.  g^Fi mod p
3. If  g^Fi is different to 1 is a generator.

 

def esGenerador(p,g):
    i = 2
    while i < (p - 1):
        if (p - 1) % i == 0: #prueba con todos los factores de p
            if expModRap(g,i,p) == 1:
                return 0 # no es generador
        i =+ 1
    return 1 # si es generador

Each one (Alice and Bob) chooses a private number.

def clavePrivada(self):
        return random.SystemRandom().randint(999,(self.p - 1))

Alice and Bob send for a insecure channel the result of:
Alice to Bob

f(x) =  g^x mod p

Bob to Alice

f(y) =  g^y mod p

def generarFXFY(self, pot):
        return funciones.expModRap(self.g, pot, self.p)

expModRap calculates in a fast way the exponentiation.

def expModRap(a,b,n):
    res = 1
    pot = a % n
    while b > 0:
        if (b % 2) == 1: # si es impar
            res = (res * pot) % n
        b = b / 2
        pot = (pot * pot) % n
    return res

When Alice and Bob have f(x) and f(y), calculate K,shared private key.

def generarClave(self,funcion,pot):
        return funciones.expModRap(funcion, pot, self.p)

Brute-force attack

For get private keys (K and x or y), the hacker only has: g,p, f(x),f(y). So, he tries to get f(x) or f(y) doing:

f(n) =  gⁱ mod p

where:

i = 1, ..., p - 1 (x, y < p - 1)

f(n) = f(x) or f(y)

def buscarClavePrivada(self, fx, fy):
   for i in xrange(2,(self.p - 1)):
       privada = funciones.expModRap(self.g, i, self.p)
       if privada == fx:
           clvPrv = funciones.expModRap(fy, i, self.p)
           print "K = ",clvPrv,"\nx = ", i
           return 0
       if privada == fy:
           clvPrv = funciones.expModRap(fx, i, self.p)
           print "K = ",clvPrv,"\ny = ", i
           return 0

Code
Basic functions funciones.py
Diffie-Hellman functions difhel.py
Main function principal.py

 

Implementation 

Alice key x =  5639834 
Bob key y =  28315101
Shared private key = 11351414
Hacker found:
K =  11351414, x =  5639834

Alice key x =  26265031 
Bob key y =  22491049
Shared private key = 8590783
Hacker found:
K =  8590783, y =  22491049

Bibliography

1. S/A WolframMathWorld [online] Updated: 2014. [Accessed: October 8th 2014]. Available in: http://mathworld.wolfram.com/Diffie-HellmanProtocol.html
2. Elisa Schaeffer. Class presentation [online] Slides: 77,78. [Accessed: October 8th 2014]. Available in: http://elisa.dyndns-web.com/teaching/comp/sec/diap.pdf