Tarea 4 Algoritmo RSA

Introducción

El algoritmo RSA, es famoso por ser el más usado en el mundo para encriptar con clave pública.

Y se refiere con clave o llave pública a que por lo menos una clave que actúa como codificadora se encuentra visible para todos los participantes de la comunicación y los que intentan descifrarla. 

El meollo de nuestro algoritmo es utilizar una clave privada, sólo conocida por la persona quien escribe el mensaje, para encriptar con clave pública y clave privada y así sea muy difícil encontrar el mensaje original, para personas quienes no sean emisor o receptor.

Planteamiento del problema:

Implementar un algoritmo RSA, entro de una comunicación cliente-servidor, a manera de observar el comportamiento que se tiene de las llaves públicas y privadas sobre el mensaje que viaja en valores enteros.

Procedimiento del Algoritmo:

Éste asume que hay alguna forma de convertir las letras y símbolos en números y viceversa. Esto lo podemos hacer usando una tabla de conversión ASCII, donde A corresponde a 11, B a 12, etc. Por ejemplo la palabra Attack! Sería transformada en 115656373947.

Tabla de conversión ASCII:

	0	1	2	3	4	5	6	7	8	9
0	XX	xx	xx	xx	xx	xx	xx	xx	xx	xx
1	SP	A	B	C	D	E	F	G	H	I
2	J	K	L	M	N	O	P	Q	R	S
3	T	U	V	W	X	Y	Z	a	b	c
4	d	e	f	g	h	i	j	k	l	m
5	n	o	p	q	r	s	t	u	v	w
6	x	y	z	.	,	:	;	´	“
7	!	@	#	$	%	^	&	*	'-	'+
8	(	)	[	]	{	}	?	'/	<	>
9	0	1	2	3	4	5	6	7	8	9

Luego de convertir la palabra en un número entero, encriptar y desencriptar se convierte en un asunto de cálculo simple entre grandes números enteros. 

Sean p y q dos números primos muy grandes, se multiplican obteniendo 

N = pq. 

Sea e un entero positivo que no tenga factores en común con (p-1)(q-1). 

Sea d un entero positivo tal que ed - 1 es divisible por (p-1)(q-1).

Y en definición sea:

f(x) = x^e mod N (esto significa "divida N por x^e y tome el resto") 

g(x) = x^d mod N (i de m)

Use f(x) para encriptar y g(x) para desencriptar.

e es el mensaje encriptado, N es la clave pública que cualquiera puede conocer y puede usarse para encriptar un mensaje, en cambio d es el mensaje desencriptado. p y q son la clave privada que solo conoce el destinatario y le sirve para desencriptar el mensaje.

¿Por que el RSA es tan difícil de romper? Pensemos que hace Alice para recibir mensajes secretos. Primero genera los grandes números primos p y q, luego escoge e. Finalmente resuelve la ecuación para encontrar d: 

ed + (p-1)(q-1)y = 1

Donde todas estas variables son números enteros. Alice publica e y N. Es todo lo que necesita para que cualquiera le envíe mensajes secretos.

Ahora veamos a Bob que conoce N y quiere desencriptar los mensajes de Alice. Para esto necesita conocer los factores de N, p y q de modo de resolver la ecuación. Luego resuelve la ecuación para encontrar d, lo que equivale a desencriptar el mensaje de Alice. El problema es que para factorizar (o sea encontrar p y q que multiplicados hacen N) le tomaría una enorme cantidad de tiempo computacional -para valores de p y q suficientemente grandes- podría tomar millones de años con el conocimiento y tecnologías actuales.

Implementación:

Se tuvo problemas al intentar implementar el algoritmo en un programa, primeramente utilizando los sockets, ya que no se obtenía comunicación ambidireccional.

	#Algunas funciones fueron obtenidas de la siguiente URL: http://blog.hackxcrack.es/2011/11/introduccion-la-criptografia-moderna_09.html
	import hashlib
	import random
	def hacerentero(s): #Se utiliza una funcion para hacer el mensaje a enteros
	n = 0
	for c in s:
	n <<= 8 #evaluando los digitos ingresados por el usuario
	n += ord(c) #se obtiene el orden de c
	return n
	def esPrimo(n): #Funcion que checa si el numero es primo
	raiz=int(sqrt(n)); #Se obtiene su raiz para evaluar en una condicion
	for i in range(2,raiz+1):
	if n%i==0:
	return False;
	return True;
	def cifrado(mensaje, public): #Funcion que cifra el texto
	n = hacerentero(s) #Se guarda el mensaje hecho entero en n
	c = modex(n, public[1], public[0]) #Se guarda en c el mensaje cifrado por la clave publica
	return
	def descifrado(n, private): #Funcion que descifra con clave privada
	p = modex(n, private[1], private[0]) #Se almacena en p el numero coprimo de q
	s = hacerentero(p)
	return
	def entrando(mensaje,private):
	s = int(hashlib.sha1(me).hexdigest(), 16) #Se almacena en un entero la representación de bits
	return modex(s,private[1],private[0])
	def checandoentrada(mensaje,sign,pub): #Funcion que checa las entradas a nuestro sistema
	s = modex(sign,pub[1],pub[0])
	h = int(hashlib.sha1(msg).hexdigest(), 16)
	return s == h
	def Alice(publico, privado): #Funcion que modifica el mensaje original conoce la llave publica y privada
	mensaje= raw_input("Ingrese el mensaje: ")
	smsint=int(hacerentero(mensaje))
	return mensaje
	def main():
	primo= False #Se rellenan los valores necesarios o por default
	primo2= False
	while primo == False || primo2==False: #Sale de la condicion hasta que se ingresa un numero primo
	p= int(raw_input("primo1: "))
	primo=esprimo(p)
	q= int(raw_input("primo2: ")) #Cuando son 2 numeros primos, termina el while
	primo2=esprimo(q)
	N=p*q #Empiezan calculos del algoritmo
	phi = (p - 1) * (q - 1) #Se obtiene el valor de phi
	e=65537
	while (phi%e) == 0:
	e=generadorprimo(17)
	d = inverse_mod(e, phi) #Se señalaa d como el inverso modular tomando a e, phi
	public = (n, e)
	private = (n, d)
	Alice(public, private) #Se calculan las supuestas claves publicas y las mandas a alice para que proceda a encriptar.
	main()

view raw rsa.py hosted with ❤ by GitHub

El programa está incompleto, tiene algo de lógica pero le falta funcionalidad a la hora de la implementación, se necesita comprender más a fondo el algortimo.
Se necesita implementar comunicación cliente servidor donde la información viaje en dos direcciones, para poder simular correctamente el funcionamiento del algoritmo.

Conclusiones:

Se puede concluir que el algoritmo RSA es muy seguro, y no vulnerable, ya que aunque parezca que se da mucha información a las otras partes de la comunicación, la clave privada nunca se comparte, ni se muestra, lo cual no permite la obtención del mensaje original.

Referencias:

Autor: "Javiyu" Título: "Generadores en python" Fecha: 13 de mayo del 2008 URL: http://javiyu.blogspot.mx/2008/05/generadores-en-python.html

Autor: Tomas Bradanovic Título: "El algoritmo RSA para dummies" Fecha: Jueves 22 de noviembre del 2012 URL: http://bradanovic.blogspot.mx/2012/11/el-algoritmo-rsa-para-dummies.html

Autor: "Raúl González Duque" Título: "Sockets en Python" Fecha: URL: http://mundogeek.net/archivos/2008/04/12/sockets-en-python/