RSA explicado

Cada vez que un navegador muestra un candado, se firma un mensaje o un programa comprueba una actualización, la criptografía de clave pública está en acción, y RSA es su forma más conocida. Su idea es que la clave que cierra un mensaje puede publicarse, mientras que la clave que lo abre se mantiene privada. Sorprendentemente, todo el sistema se basa en aritmética que se enseña en la escuela: números primos, multiplicación y restos.

Los primos secretos 61 y 53 dan el módulo público 3233. Las letras de HELLO se convierten en 3000, 28, 2726, 2726 y 1307 con el exponente público 17, y el exponente privado 2753 devuelve 3000 a 72
Los primos secretos 61 y 53 dan el módulo público 3233. Las letras de HELLO se convierten en 3000, 28, 2726, 2726 y 1307 con el exponente público 17, y el exponente privado 2753 devuelve 3000 a 72

El problema que resuelve RSA

Los cifrados tradicionales, desde el cifrado César hasta el moderno AES, usan la misma clave para cerrar y abrir, así que las dos partes deben compartir antes una clave secreta en privado. La criptografía de clave pública elimina ese paso. Cada persona tiene dos claves: una clave pública que cualquiera puede usar para cifrarle un mensaje y una clave privada que solo ella posee y que es la única que puede descifrarlo. Whitfield Diffie y Martin Hellman describieron la idea en 1976, y un año después Ron Rivest, Adi Shamir y Leonard Adleman, del MIT, encontraron una forma de llevarla a la práctica, llamada RSA por sus iniciales.

Martin Hellman (izquierda) y Whitfield Diffie (derecha), 1977
Martin Hellman (izquierda) y Whitfield Diffie (derecha), 1977

Crear las claves

Elige dos primos grandes, p y q, y multiplícalos: n = p × q. Calcula φ(n) = (p − 1)(q − 1), la función φ de Euler, que cuenta los números menores que n que no comparten ningún factor con él. Escoge un exponente público e que no comparta ningún factor con φ(n); 65537 es la elección habitual. Después halla el exponente privado d tal que e × d deje resto 1 al dividirlo entre φ(n). El algoritmo de Euclides extendido lo hace rápidamente. La clave pública es el par (e, n); la clave privada es d. Con p = 61 y q = 53 se obtiene n = 3233, φ(n) = 3120, e = 17 y d = 2753.

Cifrar y descifrar

Primero, el mensaje se convierte en un número m menor que n. Para cifrarlo, se calcula c = mᵉ mod n, el resto de mᵉ al dividirlo entre n. Para descifrar, se calcula cᵈ mod n. El teorema de Euler garantiza que así se recupera m, porque e × d es 1 más que un múltiplo de φ(n). Con las claves anteriores, la letra A, código 65, se convierte en 65¹⁷ mod 3233 = 2790, y 2790²⁷⁵³ mod 3233 vuelve a ser 65. Potencias tan grandes nunca se escriben enteras: los cuadrados sucesivos las calculan con una elevación al cuadrado por cada bit del exponente, tomando el resto en cada paso.

Firmas digitales

RSA también funciona al revés. Elevar un mensaje al exponente privado, s = mᵈ mod n, produce una firma que solo puede crear el propietario de la clave. Cualquiera puede comprobarla con la clave pública: si sᵉ mod n devuelve m, el mensaje procede del titular de d y no se ha modificado por el camino. En la práctica, lo que se firma es un hash corto del mensaje y no el mensaje en sí. Firmas como esta protegen las actualizaciones de software, los sitios web seguros y los documentos electrónicos.

Por qué es seguro

Todo el mundo puede ver n y e. Para hallar d, un atacante necesita φ(n), y para hallar φ(n) necesita p y q, así que romper RSA se reduce a factorizar n. Multiplicar dos primos le lleva a un ordenador una fracción de microsegundo; se cree que descomponer el producto de nuevo en ellos es extremadamente difícil. El mayor número del desafío RSA factorizado hasta ahora, RSA-250 en 2020, tiene 829 bits y requirió unos 2700 años de tiempo de cálculo. Las claves que se usan hoy tienen al menos 2048 bits, unas 617 cifras.

Un secreto descubierto dos veces

En 1973, cuatro años antes que RSA, el matemático británico Clifford Cocks encontró el mismo esquema mientras trabajaba en la agencia de inteligencia GCHQ, a partir de una idea de su colega James Ellis. El trabajo era secreto y no se hizo público hasta 1997. El propio RSA se patentó en Estados Unidos en 1983; la patente expiró en septiembre de 2000, dos semanas después de que el algoritmo se hubiera liberado al dominio público.

Ron Rivest, Adi Shamir y Len Adleman (de izquierda a derecha)
Ron Rivest, Adi Shamir y Len Adleman (de izquierda a derecha)

RSA en la práctica

El RSA real nunca cifra texto directamente. El mensaje se rellena con bytes aleatorios, mediante un esquema como OAEP, para que el mismo mensaje se cifre de forma distinta cada vez y no puedan filtrarse patrones. Como RSA es lento, se usa sobre todo para intercambiar o proteger una clave corta de un cifrado simétrico rápido como AES, o para firmar. Ordenadores cuánticos lo bastante grandes podrían factorizar n rápidamente con el algoritmo de Shor de 1994, y por eso se están introduciendo nuevos métodos poscuánticos junto a RSA.

Explóralo

Abre la demostración del cifrado RSA para crear claves a partir de tus propios primos o de primos aleatorios de 2 a 8 cifras, ver cómo el algoritmo de Euclides extendido halla d fila a fila, cifrar o firmar un mensaje carácter a carácter y seguir los cuadrados sucesivos de cualquier carácter. Después deja que Eve factorice n y observa cómo crece el tiempo que necesita con el tamaño de los primos.

Preguntas frecuentes

¿Por qué RSA necesita números primos?

Porque φ(n) solo es fácil de calcular si se sabe cómo se descompone n en primos. Para n = p × q con p y q primos, φ(n) = (p − 1)(q − 1). Los primos también hacen que n sea lo más difícil posible de factorizar para su tamaño, ya que no tiene ningún factor pequeño.

¿Por qué e suele ser 65537?

65537 = 2¹⁶ + 1 es primo y solo tiene dos unos en binario, así que cifrar con él requiere solo 16 elevaciones al cuadrado y una multiplicación. Además, es lo bastante grande para evitar las debilidades de exponentes muy pequeños como 3.

¿Qué diferencia hay entre RSA y Diffie–Hellman?

Diffie–Hellman permite a dos personas acordar una clave secreta compartida por un canal abierto; por sí solo no cifra ni firma nada. RSA cifra y firma directamente con un par de claves. Ambos se basan en problemas que son fáciles en un sentido y difíciles en el otro: la factorización en el caso de RSA y el logaritmo discreto en el de Diffie–Hellman.

¿Se pueden usar las claves de la demostración para cifrar de verdad?

No. Sus primos tienen como mucho una docena de cifras, así que cualquier clave que genere puede factorizarse en segundos o menos, y cifra cada carácter por separado, sin relleno. Está pensada para ver cómo funciona RSA, no para proteger nada.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir la demostración del cifrado RSA