Diffie-Hellman hack

Para ésta entrada nos toco realizar una actividad en la que consistía tratar de sacar el mensaje y la clave emitidos por Alice & Bob.

Variables o valores a usar:
p: Es un número primo emitido por Alice & Bob (público)
g: Es un número cualquiera que pertenece a p (público)
X: Es el valor que obtiene Bob apartir de un x que el define (público)
Y: Es el valor que obtiene Alice apartir de un y que el define (público)

x: Es el valor definido por Bob (privado)
y: Es el valor definido por Alice (privado)
k: Es la clave (privada)

Fórmulas:

Actividad:

p = 29
g = 19
X = 21
Y = 6

Para ésta actividad, realice un programa en python en la cuál me devuelve el valor de x, y & k. Así que la idea para sacarlas emplie fuerza bruta buscando el valor y comprobando ésta con X o Y y una vez tenidas éstas sustitui en la fórmula.

x = g ^ (i) mod p
y = g ^ (i) mod p


e i comprobábamos que fuera igual a X & Y y una vez tenidos éstas sustituiamos en la fórmula para obtener k

Programa:

def sacarX(p,g,x):
    for i in range(p):
        newX = (g**i)%p
        if newX == x:
            print "x: "+str(i)
            return i

def sacarY(p,g,y):
    for i in range(p):
        newX = (g**i)%p
        if newX == y:
            print "y: "+str(i)
            return i

def sacarK(g,p,x,y):
    k = (g**(x*y))%p
    print "K vale: "+str(k)


p = 29
g = 19
x = 21
y = 6

x = sacarX(p,g,x)
y = sacarY(p,g,y)
sacarK(g,p,x,y)

Resultados:

Referencias:

http://es.wikipedia.org/wiki/Diffie-Hellman