Bob publica en el periódico la clave para escribirle. ¿Cómo lograr que esa clave cierre una carta pero no la abra?
Bob quiere que cualquiera pueda escribirle en secreto, incluso gente a la que nunca ha visto. Publica una clave en el periódico: «cifrad con esto las cartas para mí». Eva también lee el periódico. ¿Puede ser que Eva tenga en sus manos la misma clave y aun así no lea ni una sola carta para Bob?
Suena absurdo. En cualquier cifrado conocido, desde el de César hasta AES, la misma clave cierra y abre. Quien sabe cifrar sabe descifrar: basta con hacerlo todo al revés. Publicar una clave así es publicar el propio secreto.
En 1976 Diffie y Hellman mostraron cómo dos personas pueden acordar una clave común en público. Pero hay que acordarla de nuevo con cada interlocutor, y los dos tienen que estar conectados a la vez. En el mismo artículo describieron un sueño mejor: un cifrado con dos claves distintas, una pública para cerrar y otra privada para abrir. No sabían cómo construirlo.
RSA es un cifrado de clave pública: Bob tiene dos claves, y son distintas. La pública la reparte a todos, la privada no se la enseña a nadie. La misma idea existe en la vida diaria: el candado.
Bob reparte a todos candados abiertos y guarda su llave. Alicia mete una carta en una caja y cierra en ella el candado de Bob: para eso no hace falta llave. La caja viaja hasta Bob por correo normal. Eva también tiene el candado de Bob, pero un candado solo sabe cerrarse.
Simplificación: un candado de verdad se puede forzar con una ganzúa. El candado numérico de RSA también tiene ganzúa —factorizar n—, pero con números enormes no funciona.
RSA cierra con la misma operación que Diffie–Hellman: eleva un número a una potencia y toma el resto de una división. Lo nuevo está en otra parte: el módulo n lo construye el propio Bob a partir de dos primos secretos, y son ellos los que le permiten calcular la llave. Todos los ejemplos de abajo usan los números del juego, donde n = 33.
Bob elige dos números primos aleatorios p y q, que solo son divisibles entre 1 y entre sí mismos. En las claves reales cada uno tiene 1024 bits o más, unas 309 cifras decimales. Su producto n = p × q lo reparte, y p y q los guarda en secreto. Multiplicar dos números es fácil. Averiguar de qué primos está hecho un producto es difícil si los números son enormes.
Ejemplo: p = 3, q = 11, n = 3 × 11 = 33.
Bob calcula φ = (p − 1)(q − 1) y elige la potencia del candado e, un número sin divisores comunes con φ. En las claves reales casi siempre e = 65537. A partir de e y φ halla la potencia de la llave d: aquella con la que e · d deja resto 1 al dividir entre φ. La clave pública es el par (n, e), la privada es d. Para hallar d hace falta φ, y para hallar φ hacen falta p y q.
Ejemplo: φ = 2 × 10 = 20, e = 3, d = 7, porque 3 · 7 = 21 = 1 · 20 + 1.
La carta es un número m menor que n: primero el texto se convierte en números. Alicia toma la clave pública de Bob y calcula c = me mod n. Eso es «cerrar el candado». La potencia se calcula por etapas: multiplicar, tomar el resto, multiplicar, tomar el resto. El resultado es el mismo que elevando a la potencia completa, pero los números no crecen. Si no, ningún ordenador podría con la potencia 65537 y números de cientos de cifras. El número c se envía a la vista: sin d no sirve de nada.
Ejemplo: m = 4. 4 × 4 = 16; 16 × 4 = 64 = 1 · 33 + 31. Así que c = 31.
Bob eleva c a su potencia secreta d con el mismo módulo y obtiene el m original. No hay ninguna operación nueva: el método es el mismo, solo cambia la potencia.
Ejemplo: 317 mod 33 por etapas: 31 · 31 = 961 → 4; 4 · 31 = 124 → 25; 25 · 31 = 775 → 16; 16 · 31 = 496 → 1; 1 · 31 = 31; 31 · 31 = 961 → 4. Bob obtiene m = 4.
Alicia elevó m a la potencia e, y Bob elevó el resultado a la potencia d. En total es me·d. Y Bob eligió e · d de modo que fuera 1 más que un múltiplo de φ. Los restos módulo n tienen una propiedad (el teorema de Euler): una potencia así devuelve cualquier número a su sitio. Por eso cd = me·d = m mod n. Puede imaginarse así: el candado baraja los números de 0 a n − 1 como cartas, y cada número tiene su propio lugar. La llave vuelve por las mismas líneas.
Ejemplo: 3 · 7 = 21 = 1 · 20 + 1, y 421 mod 33 = 4.
Ronald Rivest, Adi Shamir y Leonard Adleman, del MIT, pasaron un año buscando la función con la que soñaban Diffie y Hellman. Rivest y Shamir proponían esquemas y Adleman los rompía. Un esquema que funcionaba, con dos primos, apareció en abril de 1977; las letras RSA son sus iniciales. En agosto Martin Gardner habló del cifrado en Scientific American y publicó un reto: un número de 129 cifras y una frase cifrada con él, con un premio de 100 dólares. Se resolvió solo en 1994: unos 600 voluntarios pasaron ocho meses factorizando el número por internet. La frase resultó ser «The Magic Words are Squeamish Ossifrage».
El GCHQ británico también se adelantó aquí. En 1973 el joven matemático Clifford Cocks leyó la nota de su colega James Ellis sobre el «cifrado no secreto» y en una sola tarde encontró el mismo esquema con dos primos, casi cuatro años antes que Rivest, Shamir y Adleman. La patente del MIT sobre RSA estuvo vigente en EE. UU. hasta septiembre de 2000; después el algoritmo quedó libre.
RSA sigue funcionando a tu alrededor, aunque hoy firma más a menudo de lo que cifra:
Los certificados de la mayoría de los sitios están firmados con RSA, y el navegador comprueba con esa firma que la clave pertenece justo a ese sitio. En cambio, enviar la clave de la conexión con RSA quedó prohibido en TLS 1.3: ahora eso es tarea del intercambio Diffie–Hellman.
En la primera conexión, un servidor o un router muestra la huella de su clave pública, y a menudo es una clave RSA. Con ella el dispositivo demuestra que hablas con él y no con un impostor.
El correo con PGP, las firmas de programas y actualizaciones, las tarjetas bancarias con chip: en cualquier lugar donde hay que comprobar al autor sin haberlo visto nunca.
Los dos algoritmos son de criptografía de clave pública y los dos calculan potencias módulo un número, así que se confunden a menudo. La diferencia está en lo que hacen. En el intercambio Diffie–Hellman Alicia y Bob se intercambian números públicos y cada uno calcula por su lado la clave común. Ahí no se cifra nada, y los dos tienen que participar a la vez. En RSA Bob ya tiene un candado repartido a todos de antemano: Alicia lo toma y cierra la carta ella sola, aunque Bob no esté conectado en ese momento.
| Pregunta | RSA | Diffie–Hellman |
|---|---|---|
| Para qué sirve | Para cerrar una carta para un solo destinatario o firmar la tuya | Para que dos personas obtengan una clave común con la que luego cifrar sus mensajes |
| ¿Tiene que estar conectado el otro? | No: Alicia ya tiene el candado de Bob | Sí: cada uno debe aportar su número secreto |
| Qué se envía | La propia carta, cerrada con el candado | Solo números públicos; ni la carta ni la clave pasan por el canal |
| Claves | El candado y la llave de Bob sirven durante años | Los números secretos se eligen de nuevo para cada conversación |
| El problema difícil para Eva | Descomponer n en dos primos | Hallar el número secreto a partir del público (logaritmo discreto) |
| Analogía | Un candado abierto | Pinturas que mezclan dos personas |
En los estándares rusos no hay RSA en absoluto. Las firmas se hacen según GOST R 34.10-2012 sobre curvas elípticas, y la clave común se obtiene con VKO (véase el artículo sobre Diffie–Hellman). Aquí la clave pública es un punto de una curva, no un producto de dos primos, así que no hay nada que factorizar. La seguridad se apoya en otro problema difícil: el logaritmo discreto.
Cerrar una carta directamente con la clave pública tampoco es costumbre en GOST: la clave pública solo sirve para firmar y para obtener una clave común, y la carta se cifra luego con un cifrado simétrico. De hecho, en el mundo de RSA se hace casi lo mismo: con RSA no se suele cerrar la carta en sí, sino una clave aleatoria para AES.
Aun así, RSA aparece en Rusia cada día. Los navegadores normales no entienden GOST, así que incluso los certificados para sitios web que emite desde 2022 la autoridad de certificación nacional del Ministerio de Desarrollo Digital están firmados con RSA. Para las conexiones GOST esa autoridad tiene una cadena de certificados aparte, pero esos sitios solo se abren en navegadores compatibles con GOST, como Yandex Browser.
En el juego construirás la clave tú mismo, cerrarás y abrirás una carta, y luego intentarás romperla como Eva. Qué hacer:
Los dos esquemas tienen un par de claves, pública y privada, pero los problemas difíciles en los que se basan son distintos, y también lo que saben hacer:
| Parámetro | RSA | GOST R 34.10-2012 |
|---|---|---|
| De qué está hecha la clave | Dos primos grandes y su producto | Un número secreto y un punto de una curva elíptica |
| Problema difícil | Factorización | Logaritmo discreto en una curva |
| Tamaño de clave para ≈ 128 bits de seguridad | 3072 bits | 256 bits |
| Qué sabe hacer | Cifrado (con OAEP) y firma | Firma; la clave común, con VKO |
| Año | 1977 | 2012 (antes, GOST R 34.10-2001) |
| Norma | PKCS #1 (RFC 8017) | GOST R 34.10-2012 (RFC 7091), TC 26 |
Los números RSA se factorizan con la misma criba del cuerpo de números que amenaza a Diffie–Hellman, así que la seguridad también es la misma: 2048 bits equivalen aproximadamente a una clave simétrica de 112 bits, y para 128 bits hacen falta 3072. Cómo crecieron los récords: RSA-129 (426 bits) se factorizó en 1994, RSA-768 en 2009, RSA-250 (829 bits) en 2020. Los 2048 bits quedan aún muy lejos, pero las claves de menos de 2048 bits hoy se consideran inseguras.
El número 65537 = 216 + 1 es primo, y en binario solo tiene dos unos, así que una carta se puede cerrar con 17 multiplicaciones. Un e muy pequeño, como 3, es peligroso si no se añade azar: cuando m3 es menor que n, la división no cambia nada, y Eva simplemente saca la raíz cúbica de c. En el juego se ve con m = 2 y 3: 23 = 8 es menor que 33, y c = 8.
En 2012 dos grupos de investigadores reunieron millones de claves públicas RSA de internet y las compararon por pares. Decenas de miles de claves resultaron tener factores primos comunes, sobre todo en routers, cámaras de red y otros aparatos que creaban su clave justo tras el primer encendido, cuando todavía no tenían buen azar. Si dos n comparten un p, el algoritmo de Euclides lo encuentra en una fracción de segundo, y las dos claves quedan rotas. Los primos no solo deben ser enormes, sino realmente aleatorios.
El algoritmo de Shor en un ordenador cuántico factorizaría n tan rápido como resolvería el problema de Diffie–Hellman. Para RSA lo más importante son las firmas, y su sustituto ya está preparado: los estándares de firma poscuántica ML-DSA (FIPS 204) y SLH-DSA (FIPS 205). El segundo es interesante porque se apoya solo en funciones hash, sin nada de teoría de números.
Ahora sabes cómo cerrar una carta con una clave que tienen todos, y por qué la dificultad de factorizar no basta por sí sola
En el juego elegirás tus propios primos, construirás la cinta del candado y verás a Eva leer la carta sin factorizar nada