Diffie-Hellman Protocol

For this week the homework are “Hack manually (pencil and paper) a veryshort keyed Diffie-Hellman of your choice”.

We play a game, where the rules or steps are:
•    3 players are necessary (Alice, Bob and Eve).
•    For finish the game, 3 rounds are needed cycling the names (Alice, Bob, Eve)
•    Every players need to be Alice almost one time.
•    In every round :

•   The player 1(Alice) chooses a prime number (p), one number (g) in the range (0, p-1) and other number (x) in the range (0, p-1).
•    Then, Alice, calculate (X = g^x mod p) and send all the values (except x) to Bob.
•    Bob receives the values and choose one number (y) in the range (0, p-1), then calculate (Y=g^y mod p) and send the value to Alice.
•    With the respective values, Alice calculates (K=Y^x mod p) and Bob calculate (K=X^y mod p), then Alice and Bob check that K´s result are the same (Kb = Ka).
•    In this step, Alice and Bob send to Eve the values of : p, g, X, Y.
•    Eve needs to find (by brute force) the value of the x or y with (X = g^x mod p  or Y = g^y mod p ).
•    Eve with the value of x or y, needs to calculate (K=Y^x mod p  or K=X^y mod p) and compare that value with the Alice´s and Bob´s K.
•    If the value of K are the same, Eve hacks the the protocol Diffie-Hellman.

In my case, when I was Eve, the values are:
p = 13
g = 10
X = 9
Y = 4

The calculation with brute force (with pencil and paper):

And the results are:
y = 5
x = 2
K = 3

The values was verified with the original values (from Marco and Cristhian) and all are correct.
So, I can said : “I win :P”

Just for check my answer, I wrote a little script in python.
This script show all the possible values of x or y and calculate the value of K.

def obt_y(p, g, Y):
 for i in range(p):
  n= (g**i) % p
  print n
  if (n == Y):
   print "El valor probable de y es = ", i
   yf = i
 return yf

def obt_x(p, g, X):
 for j in range(p):
  n= (g**j) % p
  print n
  if (n == X):
   print "El valor probable de x es = ", j
   xf = j
 return xf
   
def obt_k(p, x, y, X, Y):
 k1 = (X**y) % p
 k2 = (Y**x) % p
 print "Las kas : ", k1, k2

 
def main():
 p = input("Ingresa el valor de p ")
 g = input("Ingresa el valor de g ")
 Y = input("Ingresa el valor de Y")
 X = input("Ingresa el valor de X")
 y = obt_y(p, g, Y)
 x = obt_x(p, g, X)
 obt_k(p, x, y, X, Y)

main ()

One capture of the script running and calculating my case(when I was Eve):

Other example of the script running:

That’s all…