[SC] 5. RSA Authentication

For this homework, we have to implement the RSA Authentication in python for a client-server system using sockets.

Introduction

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, who first publicly described it in 1977. Clifford Cocks, an English mathematician, had developed an equivalent system in 1973, but it was classified until 1997. 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. Whether breaking RSA encryption is as hard as factoring is an open question known as the RSA problem.

From http://en.wikipedia.org/wiki/RSA_(algorithm)

The implementation consist in two parts, the key generator and the client-server system.

Key Generator

For the RSA Authentication we need two keys, a public key and a private key. The public key can be know to everyone. The private keys is only know by the user. A message encrypted with the public key can only be decrypted with the private key.

For the Key generator I followed 3 steps:

• Request an username
• Generate a key
• Save (e and n) in a file named public.txt, save (d and n) in a file named private.txt

The algorithm to generate the keys is as follows:

1. Generate two different random integers and prime numbers p and q of 4 digits
2. Calculate n = p * q
3. Calculate φn = (p - 1)(q - 1)
4. Generate a random integer e between 1 and φn-1
5. Use the Extended Euclidean Theorem to calculate GCD(e, φn) and verify if e and φn are coprimes. The Extended Euclidean Theorem returns 3 values
• x and y are values ​​that satisfy the expresion ax + by = GCD(a,b)
• a is the result of GCD(a,b)
6. If a = 1 then e and φn are coprimes and now d = x, where d ≡ e^-1 mod(φn)
7. (For some reason, sometimes the value of d is negative, a while loop convert it in positive adding φn to d )
8. At this point we have calculated e (public), d (private) and n

Code

RSA Authentication

For this part I wrote a script in python implementing sockets. The programs expect 3 parameters

• User type, could be -C to client or -S to server.
• Host direction
• Port number

The script creates a server socket and a client socket, the execution of the script is as follows.

1. Get the 3 parameters, if missing one, close and exit.
2. If the 3 parameter are defined, according to the parameter 1 the scripts creates a server socket or a client socket.
3. The server sockets binds the host and port and wait (listen) for a connection. The client takes the host and port and attempt to connect to the server.
4. If the connection between then server and the client is sucessfull, the server send to the client a random value x. The server calculates the value of F(x) and the client calculates y using the same function as the server.
5. The client request a username for the authentication. The client search for the client data in the file private.txt. If the user is in the file, the subroutine returns a list containing the username, d and n, otherwise, the routine shows an exception, returns False and the client closes the connection.
6. The client uses d and n to calculate r = y^d mod (n). The calculations involve very large number, so, I wrote a subroutine based in modular exponentiation named Memory Efficient Method.
• Memory Efficient Method reduce the amount of resources needed to calculate a modulus reducing the operation to n operations, where n = exponent of the modulus. Three parameters are needed: base, exponent and modulus.
• Starts with x = 1 and n = exponent, then x = (x * base) mod modulus. The operation is repeated n amount of times.

• 
  def modularPower(base, exponent, modulus):
      c = 1
      for a in range(exponent):
          c = (c * base)%modulus
      return c
  
  

7. With r computed, the client respond to the server with the username and the value of r
8. The server also search for the user data using the same subroutine as the client. This time the subroutine returns a list containing the username, e and n.
9. The server computes y = r^emod (n).
10. If the computed value of y is equals to the computed value of F(x) and these values are equals to the y value computed by the client, the server responds "Welcome!!!" to the client indicating that the authentication was passed, otherwise responds "Failure!!!".
11. The execution ends at this point.

NOTE**: The values of e, d and n are read directly from the file, so, we need to edit the files containing the keys to cause a failure.

Code

Execution Video

References

• http://en.wikipedia.org/wiki/Modular_exponentiation
• http://www.todopic.com.ar/foros/index.php?topic=37484.0
• http://www.robolabo.etsit.upm.es/asignaturas/sctr/apuntes/motor_dc.pdf
• http://www.slideshare.net/fabricio_salgado_diaz/control-de-velocidad-de-mquinas-de-corriente-continua
• http://www3.fi.mdp.edu.ar/maquinas-electricas/Teorias%20PDF/MEII/PDF%20Presentaciones%20en%20Impress%20(.odp)/T10%20-%20Control%20de%20velocidad.pdf