Cifrado por medio de RSA
El sistema RSA
El primer algoritmo de cifrado de clave pública (cifrado asimétrico) fue desarrollado por R. Merckle y M. Hellman en 1977. Gracias al trabajo de los famosos analistas criptográficos Shamir, Zippel y Herlestman, se quedó obsoleto rápidamente.
En 1978 apareció el algoritmo de clave pública creado por Rivest, Shamir y Adelman (de aquí el nombre RSA). Este algoritmo todavía se usaba en 2002 para proteger los códigos de las armas nucleares de Estados Unidos y Rusia.
Cómo funciona RSA
El funcionamiento del criptosistema RSA se basa en la dificultad para factorizar grandes números enteros.
Digamos que p y q son dos números primos, y d un número entero tal que d se factoriza en (p-1)*(q-1)). De esta manera, el terceto (p,q,d) representa la clave privada.
Así, la clave pública es un doblete (n, e) creado con la clave privada a través de las siguientes transformaciones:
n = p * q e = 1/d mod((p-1)(q-1))
Digamos que M es el mensaje a enviar. El mensaje M necesita factorizarse en la clave n. El descifrado se basa en el teorema de Euler, que estipula que si M y n se factorizan, entonces:
Mphi(n) = 1 mod(n)
Phi(n) será la función totient y, en este ejemplo, tendría un valor de (p-1)*(q-1).
Por lo tanto, es necesario que M no sea un múltiplo de p, q o n. Una solución sería dividir el mensaje M en bits Mi de manera que la cantidad de números en cada Mi sea estrictamente inferior a la de p y q. Esto supone entonces que p y q son grandes, que es lo que sucede en la práctica ya que el principio de RSA yace en la dificultad de encontrar p y q en un período de tiempo razonable cuando se conoce n; esto asume que p y q son grandes.
En la práctica...
Supongamos que un usuario (llamado Bob) quiere enviar un mensaje M a una persona (llamémosla Alice). Simplemente necesita obtener la clave pública de Alice (n,e) y luego calcular el mensaje cifrado c:
c = Me mod(n)
Luego, Bob envía el mensaje c a Alice, quien es capaz de descifrarlo con su clave privada (p,q,d):
M = Me*d mod(n) = cd mod(n)
