miércoles, 5 de septiembre de 2012

Diffie-Hellman Protocol

Hacking to my partners 

Hi, in the past week class, we saw some key changes algorithms and the homework is about a protocol called Diffie-Hellman Protocol, this protocol is a key establishment between parties who have had no previous contact, using an insecure channel, and an anonymous (unauthenticated).
It is generally used as a means to agree to be symmetric keys used for encryption of a session (session key establishment). Unauthenticated being, however, provides the basis for various protocols authenticated.
The safety is in the extreme difficulty (conjectured, not proven) to compute discrete logarithms in a finite field.

Ok, the protocol consists in 2 persons (or machines, whatever) and one Hacker, so one of the 2 persons (any person) establishes a number "p"(prime number) and a number g( 0, p-1), these numbers must be known also by the other person (Bob), and the Hacker, and then chose a number(any number) called private key(0=>x<=p-1), and generate X (public key) to share it to Bob, and Hacker, this person generally is called Alice, the other person (Bob) must to invent a private key too (y) and genarate Y (public key), then Bob shares X value to Alice and Hacker (hacker generally is called "Eve").

Alice gets the value of X by this formula: X = (g^x) mod (p)
Bob gets the value of Y by this formula: Y = (g^y) mod (p)

Finally when both get the X and Y values, they calculate K value, K value is the number of the key that they will use to establish the secure session (K value must be the same for Alice and Bob, obviously hehe).

Alice get the value of K by this formula: K = (Y^x)mod(p)
Bob get the value of K by this formula: K = (X^y)mod(p)

So my homework is about to get the x,y values (private keys), and K value too.
The method that i used to find all this values was the brutal force.

The values used by my partners were:

p = 7, g = 5, X = 6, Y = 3  

And all the steps that i followed are in the next images (this homework should be on paper and pencil).

In this picture i got the values of X (and Y too) with the possibles values of x(and y too), the possible values of x,y are: 0,1,2,3,4,5,6. Because p = 7, and x,y must be in the range [0, p-1]. After i calculated all the values of X,Y, I quickly realized by comparison (comparing the values ​​of X and Y that I got my team mates) what were the values ​​of x, y. In the next step I checked just getting the values ​​of K.

And in this image i got the values of K, whit the values of x,y that corresponding to X and Y. After I got the values ​​of K, and make sure they were the same, I warned my friends (Alice and Bob :P) that had the values ​​of K, x, y and then they told me I got the values ​​were correct :)


So, final results:

p = 7, g = 5, X = 6, Y = 3
private keys: x = 3, y = 5
K = 6 

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

Any doubt leave it in comments.
Sorry for my bad english.

Cheers :)

1 comentario: