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:

x	g^x	g^x % p = X
1	14	14 % 17 = 14
2	14*14 = 196	196 % 17 = 9
3	14*14*14 = 2744	2744 % 17 = 7
4	14*14*14*14 = 38416	38416 % 17 = 13
5	14*14*14*14*14 = 537824	537824 % 17 = 12
6	14*14*14*14*14*14 = 7529536	7529536 % 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:

y	g^y	g^y % p = Y
1	14	14 % 17 = 14
2	196	196 % 17 = 9
3	2744	2744 % 17 = 7
4	38416	38416 % 17 = 13
5	537824	537824 % 17 = 12
6	529536	7529536 % 17 = 15
7	105413504	105413504 % 17 = 6
8	1475789056	1475789056 % 17 = 16
9	20661046784	20661046784 % 17 = 3
10	289254654976	289254654976 % 17 = 8
11	4049565169664	4049565169664 % 17 = 10
12	56693912375296	56693912375296 % 17 = 4
13	793714773254144	793714773254144 % 17 = 5
14	11112006825558016	11112006825558016 % 17 = 2
15	155568095557812224	155568095557812224 % 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.