Contexto historico
El criptosistema RSA fue concebido en 1977 por Ronald Rivest, Adi Shamir y Leonard Adleman en el Laboratorio de Ciencias de la Computacion del MIT, y constituye el primer sistema de cifrado de clave publica practico cuya seguridad no depende del secreto del algoritmo, sino de la dificultad intrinseca de factorizar numeros compuestos grandes. Su publicacion se produjo apenas un año despues del trabajo seminal de Whitfield Diffie y Martin Hellman sobre intercambio de claves, que introdujo la nocion revolucionaria de asimetria criptografica.
Aunque su difusion publica data de 1977, investigaciones desclasificadas del GCHQ britanico revelaron que el matematico Clifford Cocks habia descrito un sistema equivalente en 1973 en un informe interno clasificado, sin que pudiera ser explotado por razones de secreto. La adopcion masiva de RSA a partir de los anos noventa, integrado en protocolos como SSL/TLS, PGP y mas tarde en firmas digitales y certificados X.509, transformo la seguridad en internet y establecio el paradigma de la infraestructura de clave publica.
La robustez de RSA no reside en la obscuridad, sino en la asimetria computacional entre la operacion de multiplicar dos primos, trivial incluso para numeros de cientos de digitos, y la operacion inversa de factorizar su producto, intratable para modulos de 2048 bits con los algoritmos conocidos. Con primos de dos a tres digitos, como los empleados en este modulo didactico, la factorizacion es abordable mediante prueba y error, lo que permite visualizar el proceso que, a escala real, requeriria miles de anos de computo.
Fundamento matematico
El procedimiento se inicia con la eleccion de dos numeros primos distintos p y q, de los cuales se deriva el modulo N = p por q y la funcion totiente de Euler phi(N) = (p-1)(q-1), que cuantifica el numero de enteros menores que N y coprimos con el. Se selecciona a continuacion un exponente publico e tal que sea coprimo con phi(N), es decir, gcd(e, phi(N)) = 1, garantizando la existencia de inverso modular.
La clave privada se obtiene calculando dicho inverso, d congruente con e^-1 modulo phi(N), de forma que e por d es congruente con 1 modulo phi(N). Esta relacion es el corazon del sistema, pues permite que las operaciones de exponenciacion modular sean inversas entre si. El cifrado de un mensaje M, con 0 menor o igual que M menor que N, se realiza como C congruente con M^e modulo N, mientras que el descifrado recupera M congruente con C^d modulo N, gracias al teorema de Euler-Fermat que establece que M^phi(N) es congruente con 1 modulo N para todo M coprimo con N.
Interceptar el paquete C conociendo unicamente la clave publica (e, N) obliga al analista a factorizar N para obtener p y q, calcular phi(N) y finalmente derivar d. En este interceptador, el jugador reproduce exactamente ese flujo de trabajo criptoanalitico: ajusta selectores de primos para que N_calc = p por q coincida con el N objetivo, verifica que gcd(e, phi) = 1 para asegurar invertibilidad, calcula d en tiempo real mediante el algoritmo extendido de Euclides y aplica la clave privada para transformar C en texto plano legible.