El algoritmo RSA para dummies

Descomponer un número en sus factores primos es el dolor de cabeza de todo estudiante de primaria, porque no existe un procedimiento fijo (receta, algoritmo) para hacerlo. Recordemos que los números primos solo son divisibles por 1 o por si mismos, por ejemplo 2, 3, 5, 7, 11, 17. En cambio números como 4 (2x2), 12 (2x3x2) etc. no son primos. Como no hay receta fija para encontrar los factorees primos, solo se pueden usar métodos de aproximación sucesiva o sea prueba y error. Con los años esta dificultad adquirió una enorme importancia al convertirse en la base de casi todos los métodos modernos de cifrado conocidos como "de clave pública".

Encontré en la web del Clay Mathematics Institute esta extraordinaria explicación del algoritmo RSA, el más usado en el mundo para encriptar con clave pública. La explicación es simple, fácil de entender y por eso la traduje y la copio a continuación:

RSA 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 como la que se muestra arriba (tabla ASCII), donde A corresponde a 11, B a 12, etc. Por ejemplo la palabra Attack! Sería transformada en 115656373947.

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 sean:
f(x) = x^e mod N (esto significa "divida N por  x^e y tome el resto") 

g(x) = x^d mod N (idem)

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

e es elmensaje 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 al malvado 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.

Notas de C.M.I.

El hecho que g deshace lo que f  hace, es decir g desencripta mensajes encriptados por f, es consecuencia del pequeño teorema de Fermat: 

"Si a no es divisible por p, donde p es primo, entonces (a^(p-1))-1 es divisible por p." 

Fermat (1605-1661) fue un matematico francés que fundó la teoría de los números. Ver referencias históricas sobre el último teorema de Fermat. Alrededor de 1630 Fermat escribió al margen de su copia de la Aritmethica de Diophantus que el tenía una prueba maravillosa del hecho que la ecuación x^n + y^n = z^n no tenía soluciones en los enteros positivos para n>2. Esto fue probado 360 años después por Andrew Wiles, en 1993.

Nota mía:

La belleza y popularidad del RSA está en que es simple, se basa en un problema matemático que cualquier alumno de secundaria puede entender y por eso hay mucha más gente en condiciones de tratar de quebrarlo. Su rival es la encriptación de curvas elípticas que se basa en matemáticas mucho más complicadas, por lo que tiene el inconveniente del ser "magia negra" para mucha gente, que la hace menos accesible y menos confiable.

Tuve la suerte de escuchar la historia de la competencia entre RSA y curva elíptica contada por el mismísimo inventor de esta última, el doctor Neal Koblitz que fue uno de los expositores del curso Information Security and Risk Management in Context, todo gracias a Coursera.

También gracias al curso de criptografía entiendo por que se usa  x^e mod N para encriptar, el mod permite hacer la operación XOR que tiene ciertas propiedades "magicas" en términos de encriptación, que hacen imposible aplicar análisis estadísticos para romper el código. No estoy seguro que el mod implique una operación XOR, es una idea mía nomás porque todas las encriptaciones modernas incluyen XOR en algún lado.

En fin, alguno de estos días reemprenderé la tarea de escribir de nuevo mi curso de seguridad informática y criptografía, tengo muchísimos conocimientos nuevos gracias a los cursos online que he tomado, solo tengo que vencer mi irresistible flojera y empezar.