Esta semana nos toco hablar sobre el algoritmo RSA para encriptar calves públicamente y usarlo para autentificar usuarios en un servidor.
Para esto la tarea fue fabricar una autentificaciónn con cliente servidor Utilizando dicho algoritmo para cifrar los datos sensibles del usuario que en mi caso sera la contraseña.
Mi implementación
La idea del algoritmo es que un sujeto quiere recibir información cifrada de otro para esto el primer sujeto crea una clave publica y una privada. La publica la envia al segundo sujeto para que cifre la información a enviar. De esta forma solo el primero debería poder descifrar la información.
El primer archivo es el siguiente, donde se llevan a cabo los cálculos pertinentes de RSA. Primero se calculé las claves de la siguiente manera:
- Elegí dos números primos "p" y "q"
- El número a usar como modulo "n" lo calcule multiplicando "p*q"
- Calcule Fi de Euler con multiplicando = (p-1)*(q-1)
- Después generando números aleatorios y la función de Euclides calculé un coprimo de el valor calculado en el paso 3, a este valor es "e".
- Por ultimo con la función de Euclides extendida calculé el multiplicador modular inverso de "e" el cual es el valor "d".
Con estos es posible encriptar información elevando el mensaje a cifrar a la "e" y aplicando el modulo "m", después para descifrarlo el mensaje cifrado se eleva a la "d" y se aplica modulo "m".
RSA.py
#! /usr/bin/python
import random
class RSA:
def fi_euclides(self, q, p):
return ((q-1)*(p-1))
def euclides(self, a, b):
while( b != 0):
a, b = b, a%b
return a
def euclides_extendido(self, a, b):
if b == 0:
return (a, 1, 0)
else:
(d, s, t) = self.euclides_extendido(b, a%b)
return (d, t, s-(a/b)*t)
def obtener_coprimo(self, a):
temp = random.randint(0, a)
while( self.euclides(a, temp) != 1):
temp = random.randint(0, a)
return temp
def generar_llaves(self, q, p):
self.p = p
self.q = q
self.n = p*q
fi = self.fi_euclides(p, q)
b = -1
while( b <= 0):
self.e = self.obtener_coprimo(fi)
(a, b, c) = self.euclides_extendido(self.e, fi)
self.d = b
return self.n, self.e, self.d
def exp_bin(self, x, n):
if n == 1:
return x
elif n%2 == 0:
return (self.exp_bin(x, n/2))**2
else:
return (x*self.exp_bin(x, n-1))
def cifrar(self, n, e, m):
return ( self.exp_bin(m, e)%n )
def descifrar(self, n,d, c):
return ( self.exp_bin(c, d)%n )
Una vez implementado el algoritmo, lo implemente para autentificar usuarios usando sockets en python. El servidor lo que hace es esperar una conexión y una vez que alguien conecta con este, genera las claves y le envía las claves publicas, después espera al cliente para que envié su cuenta y su contraseña cifrada y las verifica con su base de datos si estos son correctos.
Servidor.py
import random
import socket
import sys
import time
from rsa import RSA
def verify(usr, passw):
usr = str(usr)
passw = str(passw)
try:
fl = open("acounts.dat", "r")
except:
print "Error verifying acount"
for line in fl:
line = (line.replace("\n", "")).split("->")
if usr.lower() == line[0].lower() and passw == line[1]:
fl.close()
return True
fl.close()
return False
def main():
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
try:
s.bind(("localhost", int(sys.argv[1]) ))
except socket.error , msg:
print str(msg[0]) + ': ' + msg[1]
sys.exit()
print "Waiting for a conection..."
s.listen(10)
conn, addr = s.accept()
print "Conection reached..."
rsa = RSA()
print "Generating keys..."
(n, e, d) = rsa.generar_llaves(479, 487)
print "Sending keys..."
try:
time.sleep(1)
conn.sendall(str(n))
time.sleep(1)
conn.sendall(str(e))
except:
exit(1)
print "Waiting for aswer..."
usuario = conn.recv(1024)
ciphertext = int(conn.recv(1024))
if verify(usuario, rsa.descifrar(n, d, ciphertext)):
print "Authenticated Sesion."
conn.sendall("Authenticated Sesion :)")
else:
print "Unauthenticated Sesion, closing conection..."
conn.sendall("Unauthenticated Sesion :(")
conn.close()
s.close()
main()
El cliente conecta con el servidor para esperar las claves publicas de el. Cuando las recibe pide el nombre de usuario y la contraseña, encripta la contraseña y la envía junto con el nombre de usuario. Después espera para que el servidor verifique que son correctas.
Cliente.py
from rsa import RSA
import getpass
import socket
import sys
import time
def main():
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
try:
s.connect(("localhost", int(sys.argv[1]) ))
except socket.error, msg:
s.close()
print "Error with conection"
exit(1)
print "Conection reached."
rsa = RSA()
print "Reciving keys..."
try:
n = int(s.recv(1024))
e = int(s.recv(1024))
except:
exit(1)
username = raw_input("Username:")
password = raw_input("Password:")
# password = getpass.getpass()
time.sleep(1)
print "Sending username..."
s.sendall(username)
chipertext = str(rsa.cifrar(n, e, int(password) ))
time.sleep(1)
print "Sending password..."
s.sendall(chipertext)
print s.recv(1024)
s.close()
main()
Todas las cuentas usadas se guardan en un archivo el cuál tiene los siguientes datos:
Max->123456 Champy->18283 Cecy->101010
El autentificador corriendo
Se intentan dos conexiones la primera con la contraseña correcta y la segunda con la contraseña incorrecta. Como se puede observar en el primero realiza una conexión exitosa y en el segundo, esto no sucede:
Servidor corriendo:
kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$ python servidor.py 4141 Waiting for a conection... Conection reached... Generating keys... Sending keys... Waiting for aswer... Authenticated Sesion. kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$ python servidor.py 4141 Waiting for a conection... Conection reached... Generating keys... Sending keys... Waiting for aswer... Unauthenticated Sesion, closing conection... kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$
Cliente corriendo:
kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$ python cliente.py 4141 Conection reached. Reciving keys... Username:Max Password:123456 Sending username... Sending password... Authenticated Sesion :) kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$ python cliente.py 4141 Conection reached. Reciving keys... Username:Max Password:010101 Sending username... Sending password... Unauthenticated Sesion :(
Los inconvenientes de mi implementación es que aunque los numeros "e" y "d" para las claves son generados de forma aleatoría, los numeros p y q deberían ser generados aletoriamente de alguna lista de numeros primos fuertes.
Además las contraseñas solo aceptan numeros enteros menores a n, puesto que al intentar convertir cadenas de texto a números, obtuve números demasiado grandes y python no los soportaba.
Adios.
References:
http://www.binarytides.com/python-socket-programming-tutorial/
http://en.wikipedia.org/wiki/RSA_%28algorithm%29
http://es.wikipedia.org/wiki/Exponenciaci%C3%B3n_binaria
http://es.wikipedia.org/wiki/Algoritmo_de_Euclides
http://mundogeek.net/archivos/2008/04/12/sockets-en-python/
Eh, no era por contraseñas. Nada de contraseñas. Era que el servidor manda un "challenge" x y el cliente regresa un f(x) "firmado" con su clave privada. Pero por lo menos tienes exp_bin <3. Van 5 pts.
ResponderBorrarWow. You have explained the complete idea of rsa algorithm with its implementation. I even tested the code you have shared above and its working well. Thank you for this detail.
ResponderBorrardigital signature