Program 3 RSA

Implementing RSA algorithm in a HTTP Server(Authentication)

Hi there, in this homework we made a HTTP authentication implementing RSA algorithm.

This homework is similar to the past homework, but in this case we implemented the RSA algorithm in a HTTP server, but both are authentications.

Ok, i'm gonna explain what i made, and what do my programs :P.

Firstly i installed LAMP in my computer, to get PHP and Apache(is the important for this homework), cause i developed almost all the homework in PHP, just the "r" generator was developed in Python.

Ok, the next are the codes of PHP, in this case, Cripto01.php, Cripto02.php and Cripto03.php.

Cripto01.php

"Cripto02.php"

"Cripto03.php"

Ok, the first code is the main page of the authentication, it just shows you the buttons of Download the code in python to get "r", and the button of Authenticate, Authenticate is the link to the Cripto02.php.

The second code shows you the x value and the textfields to set "r" and your "username".
When you push "send", the php links you to the Cripto03.php code (the last one page).

 The last code(Cripto03.php) just show you the values calculated and the state of authentication (Success or failed)

This is the Python, it is used to get r value, thanks to my friend Avendaño for the help (algoritmo de exponenciación modular).





I got mi d value from de past homework (the past post), this is an image of the calculates:

 

And this is the screen shot when i calculated "r" value.

This is the link of my work: http://alejandroave.260mb.org/triana/Triana/
I save it in the server of my friend Avendaño because i was a lot of troubles with my server, but it works anyway (i guess) XD.
 

Any doubt you can leave it in comments

Sorry for my poor english XD

Bye! 

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.

Wikipedia

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: http://es.wikipedia.org/wiki/Algoritmo_de_Euclides)

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".

Access Acepted

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

SERVER SOCKET CODE

CLIENT SOCKET CODE


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 ;)

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 :)