Calculadora RSA
Elige dos primos p y q, un exponente público e y un mensaje numérico m menor que n. La calculadora construye el par de claves, halla d como inverso de e módulo φ(n), cifra m en c y lo descifra, para seguir o comprobar a mano el RSA de los libros.
Funciona en tu navegador: nada de lo que escribes se envía a ningún sitio.
Cómo usarla
- Introduce dos primos distintos p y q. Con primos pequeños como 61 y 53 los números se leen bien.
- Introduce el exponente público e: mayor que 1, menor que φ(n) y coprimo con φ(n).
- Si quieres, introduce un mensaje m, un entero menor que n. Verás el exponente privado d, el texto cifrado c y el valor descifrado, que debe coincidir con m.
Cómo funciona RSA
- Claves. n = p × q y φ(n) = (p − 1)(q − 1). Se elige e con mcd(e, φ(n)) = 1 y se calcula d = e⁻¹ mod φ(n). La clave pública es (e, n) y la privada (d, n).
- Cifrado. c = mᵉ mod n.
- Descifrado. m = cᵈ mod n. Funciona porque e × d = 1 + kφ(n) y, por el teorema de Euler, m^φ(n) ≡ 1 (mod n).
Las potencias grandes se calculan elevando al cuadrado repetidamente, así que incluso primos de 64 bits salen al instante. p y q se comprueban con un test de Miller-Rabin determinista.
Ejemplo resuelto
p = 61, q = 53, e = 17, m = 65.
- n = 61 × 53 = 3233, un módulo de 12 bits.
- φ(n) = 60 × 52 = 3120; λ(n) = mcm(60, 52) = 780.
- d = 17⁻¹ mod 3120 = 2753; la línea de comprobación dice 17 × 2753 mod 3120 = 1.
- Clave pública (17; 3233), clave privada (2753; 3233).
- c = 65¹⁷ mod 3233 = 2790, y 2790²⁷⁵³ mod 3233 devuelve 65.
Consejos
- Primero e, luego la comprobación. En la práctica se usa 65537, pero con primos pequeños suele ser mayor que φ(n); usa 3, 7 o 17.
- Los mensajes son números. El texto hay que convertirlo antes en números (por ejemplo, códigos de carácter), y cada uno debe ser menor que n.
- Para hallar d a mano se usa el algoritmo de Euclides extendido; la calculadora de Euclides extendido muestra cada paso de ese inverso.
Preguntas frecuentes
¿Cómo se calcula la clave privada d?
d es el inverso modular de e módulo φ(n): el número con e × d ≡ 1 (mod φ(n)). Se obtiene con el algoritmo de Euclides extendido. Con p = 61, q = 53 y e = 17, φ(n) = 3120 y d = 2753, porque 17 × 2753 = 46.801 = 15 × 3120 + 1.
¿Por qué e tiene que ser coprimo con φ(n)?
Solo así e tiene inverso módulo φ(n). Si e y φ(n) comparten un factor, d no existe y el mensaje no podría descifrarse de forma única. La calculadora indica el factor común cuando ocurre.
¿Qué diferencia hay entre φ(n) y λ(n)?
φ(n) = (p − 1)(q − 1) es la función de Euler; λ(n) = mcm(p − 1, q − 1) es la de Carmichael y divide a φ(n). Las dos sirven para hallar d; con λ sale un d menor (413 en vez de 2753 en el ejemplo), y es la que usan los estándares actuales.
¿Sirve para cifrar datos reales?
No. Los números son diminutos y no hay relleno, así que cualquiera puede factorizar n o ver mensajes repetidos. Úsala para aprender y comprobar ejercicios; para cifrar de verdad usa una biblioteca probada con claves de 2048 bits o más.
¿Por qué el mensaje debe ser menor que n?
El cifrado trabaja módulo n, así que m y m + n dan el mismo texto cifrado. Un mensaje igual o mayor que n no se podría distinguir de uno menor al descifrar.