martes, 11 de septiembre de 2012

RSA Authentication

RSA Authentication

Hi, the homework of this week is implement RSA authentication in Python for a client-server system with sockets.

RSA (Rivest, Shamir, Adlemna) algorithm is an algorithm for public-key criptography that is based on the presumed difficulty of factoring large integers, the factoring problem.

RSA Algorithm basicly consists in this:

A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message.


So, we (my partners and me) must to implement an authentication using RSA algorithm, and this authnetication will be between a server and a client sockets.

Ok, im going to explain whit an example how works RSA Authentication, let's supose Alice wants to establish a communication with Bob and Alice sends to Bob a communication request, so, Bob responds to Alice sending a random number, lets called x, and Bob generates a "p" and "q" values too (p and q are primes), whit that values he will obtain the value of "n", n = pq.

Ok, Bob will generate "Phi(x)" and "e" value too, Phi(x) = (p-1)(q-1) and "e" value must be a number that is not divisible by a prime number.

So, "e" value will be our public key, we can share "e" value with everyone.

And then from "e" value and Phi(n) Bob must to obtain "d" value, d value is a private key, he don't must to share that value. The value of "d" can be determinated by Euclidean extended algorithm (link for more information:

Ok.... then Alice receives that random value (x) and makes a hash called f(x) or "y", the funtion "y" could be whatever, like f(x) = 3x+5, then with "y" and public key (e) value makes the cyphred message or the cyphred value, with this formula: r = ( y^e) mod (n), and then Alice sends to Bob the value of "r"(message or value cyphred).

Finally Bob decrypts the value using "r" and his public key by the next formula : y = (r^d)mod (n), then if the y decrypted is equal than "y" value generated by Alice, Bob sends to Alice the "Flag" or signal that the request communication is acepted :), if the "y" values are different, Bob will denied the access to Alice :(.

Ok, i made all the algorithm in paper and pencil, including Euclidean extended algorithm, just to probe that all my calculation were good, and mi calculations were good :)

The next image is my calculation of p, q, n, Phi(n), e, and d(using Euclidean extended algorithm):

As you can see, "e" is a value between 1 and Phi(n), so  1=>e>=192, e = 53, n = 221, p = 13, q = 17.

All the next is the Euclidean extended algorithm, and finally beside of "e" value(53) is the "e" value(private key), e = 29.
To probe that "d" is the correct value we can use this formula: e*d = 1mod(Phi(n)). Where the  = operator means "The result to 1mod(Phi(n)) must be the same using (ed)mod(Phi(n))".

In my example "d" value was correct :).

Now with e(public key) and d(private key) values we can make the example of Client-Server (or Alice Bob example :P)

In this example Alice is the client and Bob the server:

As you can see, p, q, Phi(n), n, e and d values are the same that in the past exercise (Euclidean extended algorithm, my idea is to connect all the problem).

So, here in this example is all the theory that i explained  previously.

1 - First the client (Alice) is sending a request to the server (Bob).
2 - Server sends to Client the public key that he generates, and sends the x value too (random value).
3 - Then client generates the f(x) = 3x+5, and x = 2(for this example), so f(x) = 3(2) + 5 = 11.
4 - Then with "y" value the client calculates the r, r = (y^e) mod (n), we must to remember that e is the public key.
5 - Client sends to the sever the value of r and f(x), or y.
6 - Server calculates y, by this formula: y = (r^d) mod (n), d is the private key, the "d"value is just to Server or the person who must to decrypt the values or messages.
7 - If "y" value calculated is the same that the "y" value sent by Client, the communication request is accepted :). If not , the server sends to client the message of "Request denied".

As you can see, my y's values are the same, "y" calculated by Server and "y" sent by Client are 11, that is the reason why i put "Access Acepted".

Next is the same exercise, but in Python code, using sockets:   



But, i have some problems running my code, in specific this: ValueError: invalid literal for int() with base 10.(I will fix this problems, and i will upload the correct code in this post)

These are the screen shots of the program running:

I probe this code of sockets with my partner Pedro, and it works, but you must to change of the ip address, from: "localhost", to: the ip address of your partner.
Any doubt you can leave it in comments.

Cheers ;)

1 comentario:

  1. Los valores de p,q,d & e son independientes de x, por lo cual debería funcionar con cualquier x si funciona en general. También hay alguna confusión sobre tu función f(x). Va 5 pts.