Emmanuel García: 4th Assignment: RSA Authentication

For this week, we had to do the following:

Implement RSA authentication in Python for a client-server system with sockets.

For this I implemented this in two different ways:

A password verifying one, where the server sends the client the public key, the client encrypts its password with that, and sends it back. Then the server deciphers it with the private key and searches in a file for a match.
The method explained in class where the server sends a random number, the client calculates a function from that number and encrypts it with its private key to send it to the server. The server will now use the host name of the client to search the public key and decipher it. If it matches, the client is authenticated, otherwise the connection closes.

RSA

RSA is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers, the factoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman.[1]

So, the algorithm, as stated in the class pdf, is pretty much:

Generate n = p × q, where both p and q are prime.
(e, n) is the public key; c = m^e mod n.
e is to be relatively prime with ɸ(n)
(d, n) is the private key; m = c^d mod n.

Requirement: e × d ≣ 1 mod ɸ(n) (or in other words d needs to be the inverse multiplicative of e);

ɸ(n) = (p - 1) × (q - 1).
m^(e×d)≣ m mod n due to Euler’s theorem.

Method 1 (Not the one explained in class)

So initially I understood the homework differently so I did the client-server program in a different way, but because I didn't want all that time spent go to waste I'll just go ahead and explain it anyway.

For this method, I first tried to make a diagram sort-of thing to manage the interactions between the client and server, and what would each instance do. I did it first in paper, but then to make it more easy to understand I also did it on Cacoo:

Then, the process would be:

The server generates p and q, calculates n and ɸ(n).
The server chooses an e which is relatively prime to ɸ(n).
The server computes d, which is the inverse multiplicative of e (with the extended euclidean algorithm).
The server sends the public key (n, e) to the client who wants to authenticate.
The client encrypts its password with said public key, and sends the cipher text to the server.
The server will now use the private key (n, d) to recover the password from the cipher text, and searches for the password in a certain file.
6.1. If there is a match, the server authenticates the client, and the communication can begin.

I will now explain step by step how I did this on Python.

Note: I will not explain here how the client-server communication with sockets works, because this post is dedicated to the RSA Authentication part.

Step 1. The server generates p and q, calculates n and ɸ(n).

First we need to choose a pair of prime numbers p and q, which need to be different. For security purposes, these numbers need to be random, so I did a small pair of functions, one which will verify if a determined number is prime, and another which generates two random prime numbers. Combined we should get a nice pair of p and q random primes.

Now with p and q, we calculate n = p x q, and ɸ(n) = ( p - 1) x ( q - 1).

Step 2. The server chooses an e which is relatively prime to ɸ(n).

Two numbers are said to be relative prime or co-prime if the only number that divides both of them is 1. So we need e to be relatively prime ɸ(n). To generate a valid e, I also did a simple function which checks if two numbers are co-prime.

Step 3. The server computes d, which is the inverse multiplicative of e.

To do this,we need to use the extended euclidean algorithm. For example, if we have e = 3 and ɸ(n) = 11, first we do a table like this:

We make the first α the value of ɸ(n) (in this case 11), and the first β the value of e(3). γ will be the result of the operation α % β, but we need to keep the values of the multiplication. The next pair of α-β will be the previous β and the previous γ respectively.The table finishes when we reach zero.

After this, starting from 1, we need to change each multiplier in the terms of the previous residue. This means that, first we will clear 1, and then we will replace the 2 in that for the terms of the previous 2, until we're done:

Now we pair up the similar terms. To verify the equality we could apply modulo of 11 to everything, but to find d, first we eliminate the numbers multiple of 11(equal to zero).

Then we should have something like (e)(d) % 11= 1, where the e will be the value we already know, and d the multiplicative inverse of e.

d = 4, e = 3

Step 4. The server sends the public key (n, e) to the client who wants to authenticate.

Now the server will send the public key values "n" and "e" to the client via sockets. Nothing more.

Step 5. The client encrypts its password with said public key, and sends the cipher text to the server.

The client uses "n" and "e" to encrypt his/her password, and then send that cipher text back to the server. The encryption will be done using c = (m^e) % n, where m is the password, "e" and "n" are the public key and c is the resulting cipher text.

It should be noted that, if the password is going to be a combination of words and letters, each word should be ciphered individually but working carefully with the modulo because the password could be lost.

Step 6. The server uses the private key (n, d) to recover the password from the cipher text, and searches for the password in a certain file.

The server now uses the previously generated d, and n, as the private key to recover the message(in this case a password). So, m = (c^d) % n. This password will be searched in a file to verify if the client already exists(we could also use a host name for the client to use as an index in this search).

Step 6.1. If there is a match, the server authenticates the client, and the communication can begin.

If the password was found in the previous step, then the server acknowledges the client as trustworthy and whatever communication was supposed to happen can now happen. Otherwise the communication can end because the password was wrong.

Example of the process:

Calculating the Public Key

Encrypt m:

Decipher c:

Code:

The program bellow simulates an rsa authentication using a client-server protocol. First the server generates the random primes p and q, then it calculates n and ɸ(n) with said values. Then it generates the e (coprime to ɸ(n)). The server will send the public key (e, n) to the client, which will use it to encrypt a password. The resulting cipher text will be sent back to the server, which will decipher it and compare it with stored passwords in a file. If it matches a password, the authentication is correct, and the client is trusted. Otherwise it will terminate the communication.

The code consists of 3 files: rsa_client.py, rsa_server.py and rsa_operations.py. I did the last one to gather all the common operations needed to calculate stuff for the rsa algorithm, like the euclidean algorithm, exponentiation by squaring, simple prime verificators and such.

Client Side

Server Side

Screen Captures:

Correct Authentication

Incorrect Authentication (Wrong Password)

Password file:

Method 2:

Now the real method which was explained in class is this one. I didn't write it down from a scratch, I just modified the previous one because that way was easier (and it's my code after all). This method consists in:

The server generates a random number x.

The server sends x to a connected client.

The client calculates y = f(x) where this function can be pretty much anything, in my case is just 2x+1.

The client encrypts y using its private key (which will be generated previously in a file)
The client sends the encrypted y to the server.

The server receives the encrypted y and searches for a public key for the host name of the client.

If there is a match, the server retrieves the public key, deciphers the encrypted y, and compares with f(x)
If f(x) is equal to the deciphered y, then the client is welcomed.

Otherwise the communication is over.

Code:

Using the example that I explained on the previous method, I created the public key (e, n) = (7, 187) and stored in in the users.dat file for the server. I also did the same with the client, storing the private key (d, n) = (23, 187) in the emmanuel.dat file. So for any random that the server generates, the client emmanuel should be able to get authenticated.

Client Side:

Server Side:

Screen Captures: Correct Authentication