RSA
Números pequeños (p, q < 10000) para que cada paso se pueda verificar a mano.
¿Por qué funciona esto matemáticamente?
RSA se apoya en el teorema de Euler: si gcd(m,n)=1, entonces m^φ(n) ≡ 1 (mod n). La llave se construye eligiendo e y d tales que e·d ≡ 1 (mod φ(n)), es decir, e·d = 1 + k·φ(n) para algún entero k. Entonces:
(m^e)^d = m^(ed) = m^(1 + k·φ(n)) = m · (m^φ(n))^k ≡ m · 1^k = m (mod n)
Por eso cifrar con e y descifrar con d siempre recupera el mensaje original, sin importar qué mensaje sea (mientras 0 ≤ m < n). La seguridad no depende de que esta identidad sea secreta — es pública — sino de que, sin conocer p y q, calcular φ(n) = (p-1)(q-1) (y por lo tanto d) requiere factorizar n, algo computacionalmente inviable para n grande.
En el mundo real: RSA real usa primos de 1024 bits o más (n de más de 2048 bits);
factorizar n para romper la llave privada es computacionalmente inviable a ese tamaño. Con primos
pequeños como los de esta demo, n se factoriza en microsegundos.