Algoritmo RSA

El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Leonard Adleman, del Instituto Tecnológico de Massachusetts (MIT); las letras RSA son las iniciales de sus apellidos.

RSA se basa en la dificultad o coste computacional para factorizar grandes números. Las claves públicas y privadas se calculan a partir  de dos primos grandes.  En este sistema se usa una clave para encriptar y otra para desencriptar. La seguridad se basa casi en la imposibilidad de deducir la clave de desencriptar a partir de la clave utilizada para encriptar.

Idea del algoritmo

• Supongamos que Bob quiere enviar a Alicia un mensaje secreto que solo ella pueda leer.
• Alicia envía a Bob una caja con una cerradura abierta, de la que solo Alicia tiene la llave. Bob recibe la caja, escribe el mensaje, lo pone en la caja y la cierra con su cerradura (ahora Bob no puede leer el mensaje). 
• Bob envía la caja a Alicia y ella la abre con su llave. En este ejemplo, la caja con la cerradura es la «clave pública» de Alicia, y la llave de la cerradura es su «clave privada».
• Técnicamente, Bob envía a Alicia un «mensaje llano» M en forma de un número m menor que otro número n, mediante un protocolo reversible conocido como padding scheme («patrón de relleno»). A continuación genera el «mensaje cifrado» c mediante la siguiente operación: 

c = m^e mod n

donde e es la clave pública de Alicia.

• Ahora Alicia descifra el mensaje en clave c mediante la operación inversa dada por

m = c ^ d mod n

donde d es la clave privada que solo Alicia conoce.

Generación de llaves.

1. Alicia y Bob seleccionan dos números primos suficientemente grandes, p y q.
2. Halla N = p × q 
3. Calcula la función indicador de Euler: Φ(N) = (p – 1)·(q – 1)
4. Selecciona un número e menor que Φ(N) y tal que mcd(e, Φ(N)) = 1.
5. Calcula el inverso de e en un reloj con Φ(N) horas.
6. La clave pública está constituida por (N, e) y la secreta por (N, d).

Cifrado del mensaje.

1. Alicia localiza la clave pública de Bob para conocer los valores de N y e
2. Utiliza la función: C ≡ Me(mod N) siendo M del mensaje original y C del cifrado
3. Alicia envía a Bob el criptograma C.

Descifrado del criptograma.

1. Si Bob quiere recuperar el mensaje que ha recibido usa su clave privada d para calcular: M ≡ C d (mod N)

Implementación

A continuación se muestra el código del algoritmo implementado de RSA.

También se realizo la implementación de un cliente-servidor para probar el arlgoritmo RSA.
Servidor

Cliente

Corrida en terminal

Errores.
En el momento que el servidor quiere descifrar el mensaje que recibió del cliente este no logra descifrarlo correctamente.
El error sucede específicamente cuando la función descifrar del archivo rsa.py esta almacenando caracteres erroneos a la hora de crear el mensaje cifrado.

Referencias.

http://www.slideshare.net/amadapa/el-algoritmo-rsa
http://venxmas.fespm.es/IMG/pdf/para_saber_mas_cifrado_rsa_criptografia.pdf
http://mundogeek.net/archivos/2008/04/12/sockets-en-python/

Descargar RSA
Descargar Servidor
Descargar Cliente