RSA

Introducción

El sistema criptográfico con clave pública RSA es un algoritmo asimétrico de cifrado por bloques, que utiliza una clave pública, la cual se distribuye, y otra privada, la cual es guardada en secreto por su propietario.

Este algoritmo fue desarrollado por Rivest, Shamir y Adleman y provee tanto confidencialidad (propiedad de la información que garantiza que está accesible únicamente a personal autorizado) como autenticación (propiedad asociada a la identificación, se trata de métodos que permiten comprobar de manera segura alguna característica sobre el mensaje). Está basado en el problema de la factorización de números enteros largos: dados dos números primos p y q muy grandes, es sencillo hallar su producto (p*q), pero es un problema muy complejo encontrar, a partir del producto, los números p y q que lo originaron.

Los mensajes enviados usando el algoritmo RSA se representan mediante números y el funcionamiento se basa en el producto de los números primos mencionados anteriormente, lo cuales deben ser grandes (mayores que 10^100) y elegidos al azar para conformar las claves. Para realizar tanto la encripación como la desencriptación, se emplean expresiones exponenciales en aritmética modular.

Pasos del algoritmo

Generación de claves:

1) Generar aleatoriamente dos números primos grandes (típicamente 1024 bits) y distintos, p y q.

2) Calcular n como producto de p y q: n = p*q

3) Calcular phi: phi(n) = (p-1)*(q-1)

4) Calcula un número natural d que sea relativamente primo (coprimo) de phi(n), es decir que mcd(d, phi(n)) = 1. Esto es lo mismo que buscar un numero impar por el que dividir phi(n) que de cero como resto.

5) Mediante el algoritmo extendido de Euclides calcular e, el inverso multiplicativo de d: (e*d) mod fi(n) = 1. Para ello puede calcularse
e=((k*fi(n))+1)/d para k=1,2,3,… hasta encontrar un e entero.

ENTONCES:

• El par de números (e,n) son la clave pública.
• El par de números (d,n) son la clave privada.

Encriptación:

1) Asignar a cada caracter del mensaje plano un número entero entre 0 y (n-1) de acuerdo a alguna codificación elegida, por ejemplo ASCII.

2) Elegir un tamaño de bloque, dividir el mensaje representado numéricamente en bloques de ese tamaño.

3) Por cada bloque resutante (m), realizar la encriptación de acuerdo a c = m^e mod n

M: mensaje plano
m: bloque de mensaje plano
c: bloque de mensaje encriptado
C: mensaje encriptado

Desencriptación:

1) Por cada bloque de mensaje encriptado (c), realizar la desencriptación de acuerdo a m = c^d mod n

2) Asignar a cada número del mensaje desencriptado el caracter correspondiente de acuerdo a la misma codificación utilizada para desencriptar

Ejemplo de pantalla

Armar una primera versión de como podría verse por pantalla este algoritmo (no se compliquen, un dibujito en google draw que más o menos muestre los bontones, campos y etiquetas, junto con la explicación de la operación y ya)