Seguridad de la Información y Criptografía
Homework 3

For this week, the homework is:
Hack manually (pencil and paper) a very-short keyed Diffie-Hellman of your choice.

Definition of Diffie–Hellman Key Exchange

Diffie–Hellman key exchange is a specific method of exchanging cryptographic keys. It is one of the earliest practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher. [1]

In the next image we can see how is the channel of communication between Alice and Bob, and like our next example, if we are another person named Eve, we can get the g, p, A, B, and try to hack they key.

[http://upload.wikimedia.org/wikipedia/commons/a/a3/Diffie-Hellman-Schl%C3%BCsselaustausch.png?uselang=es]

My Hacking

Like the example of the image, we have one of our classmates that represents "Alice" and other who is "Bob", I will be "Eve".

Here is the screenshot from Facebook where my classmates published the p, g, X, Y, and I need to get the x and y, and then a key k.

I did the hack manually in my notebook, here is a capture.

If you check in the image, I started doing divisions only changing the dividend per a potency of 10 with n, where n start with one and increment in each division, when I finish the fourth division I noticed that in the dividend is only necessary to add a zero, so I did a big division, in the right of the paper I wrote a table, and in the first column I put the number of n, that represents x and y, and the second column is the result of (10^n)mod(19).

When I tried the potency of 17 and 18, I found the same X and Y that my classmates wrote in the publication in Facebook, so I check if the two numbers, one for x, and the other for y, give me the same key k.

I get x=17, y=18 and k=1.

Then I posted the x, y and the k, in a comment in the same post, and my classmates, verify if I was correct, and yes, I was correct.

After that, I did a program that do the same thing that I did manually, isn't a method that found the key when someone use this protocol, is only a sequential program that increment x and y, and verify if are the correct values for get the correct key.

Here is the code:

An example of the execution in the terminal, with the same p, g, X, Y, of the example that I did manually.