miércoles, 5 de septiembre de 2012

3rd Assignment: Diffie-Hellsman Key Exchange

For the second assignment, we were tasked to do groups of 3 or more, in order to practice the Diffie-Hellsman Key Exchange, with one of the members being Alice, one being Bob, and one Eve, and then changing roles so everyone gets to be Eve one time.

With that said, when my turn to be Eve came, Victor was Alice, and Rene was Bob. They talked in secret generating the values of p and g. Then they made said values, and their respectives X and Y public:
  • p = 17
  • g = 14
  • X = 15
  • Y = 11
With this then I had to start to "hack" to obtain the values of x and y, and therefore the key. So I started first with obtaining x from the X function:
To get x, I just brute-forced my way with every number lower than p. In other cases this may not be really hard(here it is also not hard), but because I was doing it with pencil, without the use of a computer-calculator, this was pretty annoying. 

So what I did, was the following:


As it can be seen, I just multiplied the current power of 14 by 14 again, and then divided by 17, to check the residue(module). If it wasn't equal to 15, the value of X, then I had to multiply again until it did. To see this in a more clean fashioned way, here's a table:

xg^xg^x % p = X
11414 % 17 = 14
214*14 = 196196 % 17 = 9
314*14*14 = 27442744 % 17 = 7
414*14*14*14 = 3841638416 % 17 = 13
514*14*14*14*14 = 537824537824 % 17 = 12
614*14*14*14*14*14 = 75295367529536 % 17 = 15

Now, we can try the same with y. There was a probability that y was already in the previous table, but I didn't get any luck with that, so I continued from where I left. Unfortunately this wasn't any short, as it can be seen:


Another table for better understanding:

yg^yg^y % p = Y
11414 % 17 = 14
2196196 % 17 = 9
327442744 % 17 = 7
4 3841638416 % 17 = 13
5537824537824 % 17 = 12
65295367529536 % 17 = 15
7 105413504105413504 % 17 = 6
814757890561475789056 % 17 = 16 
9 2066104678420661046784 % 17 = 3
10289254654976289254654976 % 17 = 8
1140495651696644049565169664 % 17 = 10
12 5669391237529656693912375296 % 17 = 4
13793714773254144793714773254144 % 17 = 5 
14 1111200682555801611112006825558016 % 17 = 2 
15155568095557812224155568095557812224 % 17 = 11

And that was getting y. With both x and y, now I just had to generate two K's separatedly, one using Y-x, and another one using X-y, with the formulas:
Then: 

K = X^y % p = (15^6) % 17 =  (15*15*15*15*15*15) % 17 = 8
K = Y^x % p = (11^15) % 17 = (11*11*11*11*11*11*11*11*11*11*11*11*11*11*11) % 17 = 8

So I concluded that the Key was 8, wth x = 6, and y = 15. Victor and Rene confirmed this.

1 comentario: