RSA (with sockets)

The homework for this week, was "Implement RSA authentication in Python for a client-server system with sockets"

 So, this is my work: 

RSA, is an algorithm for cryptography and consist in generate two keys (public and private key) one pair for participant, for encrypt one message.

Basically the steps for create the keys are:

• Choose two prime numbers, p and q.
• Calculate n = p*q
• Calculate φ(n) = (p-1) * (q-1)
•  Choose e, such that : 1<e<φ(n) and e, φ(n) are coprimes
• Calculate : Inverse mod of e mod φ(n)

  

• The public key are (n, e)
• The private key are (n, d)

For encrypt the message, first we need to convert this to a integer number n then calculate:

For decrypt the message, first we need to recuperate the plain number this calculating:

then convert the plain number to the message.

For convert the message to a number and a number to a message, i used the ascii code from every character in the message.

For choose the value of e and calculate d, i used the extended euclidean algortihm, i wrote something about this in Extended Euclidean Algorithm, (originally thist post was for cripto, but i had an error choosing the correct blog ) and the library gmpy2, for calculate the modular inverse for obtain the value of d.

Here is are my codes:

script for the server:

import socket
import random
import gmpy2

def enviar(algo, server_c):
 #algo = str(algo)
 server_c.send(str(algo))  #enviar algo al cliente conectado
 return 

def recibir(server_c):
 algo = server_c.recv(2048)  #recibir algo del cliente (maximo en bytes a recibir)
 #algo = int(algo)
 return algo

def encriptar(np, e_r, n_r):
 ne_e = (pow(np, e_r)) % n_r
 return ne_e

def desencriptar(ne_r, d, n):
 ne_r = int(ne_r)
 np_r = (pow(ne_r, d)) % n
 return np_r

def crear_primo(longitud):
    #longitud en bits, es necesario que sea parecida entre p y q
    primo = random.randint(2**(longitud-1),2**longitud)
    primo |= 1 #lo hacemos impar
    return primo

def extended_gcd(a, b):
    x, ant_x = 0, 1
    y, ant_y = 1, 0
 
    while b:
        cociente = a // b
        a, b = b, a % b
        x, ant_x = ant_x - cociente*x, x
        y, ant_y = ant_y - cociente*y, y
 
    return (ant_x, ant_y, a)

def f(x):
 y = x*31
 
def main():
 server = socket.socket()  #iniciar el servidor
 server.bind(("localhost", 9999))  #establecer (nombre host, puerto)
 server.listen(1)  #numero de conexiones entrantes
 print "Esperando conexion una entrante...  "
 server_c, direccion = server.accept()  #aceptar conexion con un cliente
 print "Conectado!...  "
 
 p = crear_primo(8) 
 #p = 283
 q = crear_primo(8)
 #q = 163
 n = p*q
 phi = (p - 1)*(q - 1)
 
 gcd = 0
 while (gcd != 1):  #buscar el exponente publico e
   e = crear_primo(random.randint(8, 15))
   x, c, gcd = extended_gcd(e, phi)  
   d = gmpy2.invert(e, phi)
            
 #se forma clave publica  (n, e)
 #se forma la clave privada  (n, d)
 
 enviar(n, server_c)#se envia la clave publica
 enviar(e, server_c)
 print "Clave publica enviada...  "
 print n, e

 usuarios = ["alex", "david", "ale"]
 x = random.randint(0, 50)
 X = f(x)
 
 
 enviar(x, server_c)
 print "x enviado : "
   
 usuario = recibir(server_c)
 x_r = recibir(server_c)
 x_r = int(x_r)

 if (usuario in usuarios):
  print " User : ", usuario, " correcto... "

  y = desencriptar(x_r, d, n)
  if (X==y):
   print "Bienvenido!!......"
  else:
   "Numero incorrecto..."
 else:
  print " User incorrecto..." 

 server.close()
 server_c.close() 
 
main() 

script for the client:

import socket

def enviar(algo, client):
 #algo = str(algo)
 client.send(str(algo))  #enviar algo al cliente conectado
 return 

def recibir(client):
 algo = client.recv(2048)  #recibir algo del cliente (maximo en bytes a recibir)
 #algo = int(algo)
 return algo

def encriptar(np, e_r, n_r):
 ne_e = (pow(np, e_r)) % n_r
 return ne_e

def desencriptar(ne_r, d, n):
 ne_r = int(ne_r)
 np_r = (pow(ne_r, d)) % n
 return np_r

def f(x):
 y = x*31
 
def main():
 client = socket.socket()  #iniciar el cliente
 client.connect(("localhost", 9999))  #establecer conexion a (nombre host, puerto)
 print "Conectado!...  "
 
 n_r = recibir(client) #se recibe la clave publica
 e_r = recibir(client)
 print "Clave publica recibida...  "
 n_r = int(n_r)
 e_r = int(e_r)
 print n_r, e_r
  
 x_r = recibir(client) #se recibe el numero x
 x_r = int(x_r)
 X = f(x_r)

 user  = raw_input("Ingrese su usuario: ")
 y = encriptar(int(X), e_r, n_r)
 
 enviar(user, client) #se envian los datos
 enviar(y, client)
    
 usuario = recibir(server_c)
 x_r = recibir(server_c)
 x_r = int(x_r)

 client.close() 
 
main() 

Here the captures of this running:

 

 

Then, just for fun, i try to write a code for  emulate a simple chat or somethin like that.

The code for the server version:

import socket
import random
import gmpy2

def enviar(algo, server_c):
 #algo = str(algo)
 server_c.send(str(algo))  #enviar algo al cliente conectado
 return 

def recibir(server_c):
 algo = server_c.recv(2048)  #recibir algo del cliente(max en bytes)
 #algo = int(algo)
 return int(algo)

def msg_num(mensaje_e):
 np_e = 0
 for char in mensaje_e:
  np_e <<= 8
  np_e += ord(char)
 #print np_e
 return np_e

def num_msg(np_r):
 nm = []
 while np_r > 0:
  #nm >>= 8
  nm.insert(0, chr(np_r & 255))
  np_r >>= 8
 mensaje_r = "".join(nm)
 #print mo
 return mensaje_r

def encriptar(np, e_r, n_r):
 ne_e = (np ** e_r) % n_r
 return ne_e

def desencriptar(ne_r, d, n):
 ne_r = int(ne_r)
 np_r = (ne_r ** d) % n
 return np_r

def crear_primo(longitud):
    #longitud en bits, es necesario que sea parecida entre p y q
    primo = random.randint(2**(longitud-1),2**longitud)
    primo |= 1 #lo hacemos impar
    return primo

def extended_gcd(a, b):
    x, ant_x = 0, 1
    y, ant_y = 1, 0
 
    while b:
        cociente = a // b
        a, b = b, a % b
        x, ant_x = ant_x - cociente*x, x
        y, ant_y = ant_y - cociente*y, y
 
    return (ant_x, ant_y, a)
 
def main():
 server = socket.socket()  #iniciar el servidor
 server.bind(("localhost", 9999))  #establecer (nombre host, puerto)
 server.listen(1)  #numero de conexiones entrantes
 print "Esperando conexion una entrante...  "
 server_c, direccion = server.accept()  #aceptar conexion con un cliente
 print "Conectado!...  "
 
 p = crear_primo(8) 
 q = crear_primo(8)
 n = p*q
 phi = (p - 1)*(q - 1)
 
 gcd = 0
 while (gcd != 1): #buscar el exponente publico e 
                          #(menor que phi y que sea coprimo de phi)
   e = crear_primo(random.randint(8, 15))
   x, c, gcd = extended_gcd(e, phi)  
   d = gmpy2.invert(e, phi) #calcular el exponente privado d
            
 #se forma clave publica  (n, e)
 #se forma la clave privada  (n, d)
 
 enviar(n, server_c)#se envia la clave publica
 enviar(e, server_c)
 print "Clave publica enviada...  "
 print n, e

 n_r = recibir(server_c) #se recibe la clave publica
 e_r = recibir(server_c)
 print "Clave publica recibida...  "
 print n_r, e_r

 mensaje_r = "-"
 print "Iniciando el envio de mensajes... "
 while  (mensaje_r != "fin") : #mantener la conexion y el envio de mensajes

  #enviar mensajes
  mensaje_e = raw_input("Ingrese el mensaje a enviar: ")
  np_e = msg_num(mensaje_e)
  print "numero plano a enviar : ", np_e 
  ne_e = encriptar(np_e, e_r, n_r)
  enviar(ne_e, server_c)
  print "numero encriptado a enviar : ", ne_e
  print "Mensaje enviado...  "
  
  #recibir mensajes
  ne_r = recibir(server_c)
  print "numero encriptado recibido : ", ne_r
  np_r = desencriptar(ne_r, d, n)
  print "numero plano recibido : ", np_r
  mensaje_r = num_msg(np_r)
  print "Mensaje recibido:  ", mensaje_r

 server.close()
 server_c.close() 
 
main() 

The code for the client version, practically are the same that the server version, just change in the part of the sockets, the functions for recive, send, encrypt, decrypt are the same.

 client = socket.socket()  #iniciar el cliente
 client.connect(("localhost", 9999))  #establecer conexion 
 print "Conectado!...  "

Here an capture from the codes running:

Unfortunately, the programs don´t run at 100%, i have troubles with the decryption of the number and for consequence the message don´t shows like the original message, i´m not sure what i´m doing wrong :/.

________________________________________________________________________________
References:
http://en.wikipedia.org/wiki/RSA_%28algorithm%29
http://en.wikipedia.org/wiki/Coprime
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
http://temasinteligencia.blogspot.mx/2012/08/algoritmo-de-euclides-extra.html