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

Diffie-Hellman Protocol

For this week the homework are “Hack manually (pencil and paper) a veryshort keyed Diffie-Hellman of your choice”.

We play a game, where the rules or steps are:
•    3 players are necessary (Alice, Bob and Eve).
•    For finish the game, 3 rounds are needed cycling the names (Alice, Bob, Eve)
•    Every players need to be Alice almost one time.
•    In every round :

•   The player 1(Alice) chooses a prime number (p), one number (g) in the range (0, p-1) and other number (x) in the range (0, p-1).
•    Then, Alice, calculate (X = g^x mod p) and send all the values (except x) to Bob.
•    Bob receives the values and choose one number (y) in the range (0, p-1), then calculate (Y=g^y mod p) and send the value to Alice.
•    With the respective values, Alice calculates (K=Y^x mod p) and Bob calculate (K=X^y mod p), then Alice and Bob check that K´s result are the same (Kb = Ka).
•    In this step, Alice and Bob send to Eve the values of : p, g, X, Y.
•    Eve needs to find (by brute force) the value of the x or y with (X = g^x mod p  or Y = g^y mod p ).
•    Eve with the value of x or y, needs to calculate (K=Y^x mod p  or K=X^y mod p) and compare that value with the Alice´s and Bob´s K.
•    If the value of K are the same, Eve hacks the the protocol Diffie-Hellman.

In my case, when I was Eve, the values are:
p = 13
g = 10
X = 9
Y = 4

The calculation with brute force (with pencil and paper):

And the results are:
y = 5
x = 2
K = 3

The values was verified with the original values (from Marco and Cristhian) and all are correct.
So, I can said : “I win :P”

Just for check my answer, I wrote a little script in python.
This script show all the possible values of x or y and calculate the value of K.

def obt_y(p, g, Y):
 for i in range(p):
  n= (g**i) % p
  print n
  if (n == Y):
   print "El valor probable de y es = ", i
   yf = i
 return yf

def obt_x(p, g, X):
 for j in range(p):
  n= (g**j) % p
  print n
  if (n == X):
   print "El valor probable de x es = ", j
   xf = j
 return xf
   
def obt_k(p, x, y, X, Y):
 k1 = (X**y) % p
 k2 = (Y**x) % p
 print "Las kas : ", k1, k2

 
def main():
 p = input("Ingresa el valor de p ")
 g = input("Ingresa el valor de g ")
 Y = input("Ingresa el valor de Y")
 X = input("Ingresa el valor de X")
 y = obt_y(p, g, Y)
 x = obt_x(p, g, X)
 obt_k(p, x, y, X, Y)

main ()

One capture of the script running and calculating my case(when I was Eve):

Other example of the script running:

That’s all…