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.

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/