¿Por qué funciona RSA? Explicado paso a paso

Aritmética modular. Escribimos $a \equiv b \pmod n$ si $n$ divide a $a - b$: es decir, $a$ y $b$ dejan el mismo resto al dividir entre $n$. Las sumas y los productos se pueden hacer «a trozos»: se reduce módulo $n$ en cualquier paso. Por eso $1234^7 \bmod 2747$ se calcula sin escribir el número gigante, elevando al cuadrado y reduciendo cada vez.

La función $\varphi$. $\varphi(n)$ es la cantidad de números entre 1 y $n$ sin factores comunes con $n$. Si $p$ es primo, $\varphi(p) = p - 1$. Si $n = pq$ con $p \neq q$ primos, $\varphi(n) = (p-1)(q-1)$: entre los números $1, 2, \dots, pq$ hay $q$ múltiplos de $p$ y $p$ múltiplos de $q$, y solo $pq$ está en las dos listas, así que se excluyen $p + q - 1$ y quedan $pq - p - q + 1 = (p-1)(q-1)$. Con $n = 2747$ se excluyen $41 + 67 - 1 = 107$ números y quedan $2640$.

Euclides extendido para hallar $d$. Como $\operatorname{mcd}(e, \varphi(n)) = 1$, existen enteros $s, t$ con $s\,\varphi(n) + t\,e = 1$, y entonces $t \cdot e \equiv 1 \pmod{\varphi(n)}$. Se calculan con el algoritmo de Euclides, arrastrando los coeficientes. Para $\varphi = 2640$ y $e = 7$:

La penúltima fila dice $1 \cdot 2640 - 377 \cdot 7 = 1$. Luego $e^{-1} \equiv -377 \equiv 2263 \pmod{2640}$, y $d = 2263$.

Teorema de Euler. Si $\operatorname{mcd}(a, n) = 1$, entonces

Para $n = p$ primo es el pequeño teorema de Fermat: $a^{p-1} \equiv 1 \pmod p$. Euler publicó una demostración de ese caso en 1741 (escrita en 1736) y la generalización a módulos compuestos, la que usa $\varphi$, en 1763. Aquí solo necesitamos el caso de Fermat, y damos una demostración corta (no es la de 1741, que va por inducción): si $a$ no es múltiplo de $p$, los números $a, 2a, \dots, (p-1)a$ son distintos módulo $p$ (si $ia \equiv ja$, como $p$ no divide a $a$, $p$ divide a $i - j$, y esto solo pasa si $i = j$) y ninguno es múltiplo de $p$. Son, por tanto, los mismos $p - 1$ restos no nulos en otro orden, y multiplicándolos todos:

Como $p$ no divide a $(p-1)!$, se puede simplificar y queda $a^{p-1} \equiv 1 \pmod p$.

Por qué $(m^e)^d \equiv m \pmod n$. Sea $n = pq$ con $p \neq q$ primos, y sean $e, d$ enteros positivos con $ed \equiv 1 \pmod{\varphi(n)}$, es decir, $ed = k\,\varphi(n) + 1$ para algún entero $k \ge 0$. Queremos ver que

Lo probamos por separado módulo $p$ y módulo $q$.

Módulo $p$. Como $ed - 1 = k(p-1)(q-1)$ es múltiplo de $p - 1$, tenemos $m^{ed} = m \cdot (m^{p-1})^{k(q-1)}$. Hay dos casos. Si $p$ no divide a $m$, Fermat da $m^{p-1} \equiv 1$ y por tanto $m^{ed} \equiv m \pmod p$. Si $p$ divide a $m$, entonces $m \equiv 0$ y también $m^{ed} \equiv 0 \equiv m \pmod p$, porque $ed \ge 1$.

Módulo $q$. Lo mismo, intercambiando los papeles.

Juntarlo. Hemos visto que $p$ divide a $m^{ed} - m$ y que $q$ también. Como $p$ y $q$ son primos distintos, $pq$ divide a $m^{ed} - m$. Esto es el teorema chino del resto en su forma más sencilla: un sistema $x \equiv a \pmod p$, $x \equiv a \pmod q$ tiene como única solución módulo $pq$ la clase de $a$. Así, $m^{ed} \equiv m \pmod n$.

El caso $\operatorname{mcd}(m, n) \neq 1$ no se pierde: es justo cuando $p$ o $q$ divide a $m$ y se resuelve con la rama «$m \equiv 0$» de arriba. Con $n = 2747$, por ejemplo, $m = 82 = 2 \cdot 41$ da $c = 1804$ y $1804^{2263} \equiv 82 \pmod{2747}$. Hay $n - \varphi(n) = 107$ valores así entre 0 y 2746, y hemos comprobado con un programa que los 2747 posibles mensajes se descifran bien. La hipótesis $p \neq q$ sí hace falta: con $n = 25$, $e = 3$ y $d = 7$ se cumple $ed = 21 \equiv 1 \pmod{\varphi(25)}$, porque $\varphi(25) = 20$, y sin embargo $5^{21} \equiv 0 \not\equiv 5 \pmod{25}$.

Esta es la demostración que recogen Rivest, Shamir y Adleman en su artículo (sección VI), aunque ellos escogen primero $d$ y calculan $e$ (el papel de los dos exponentes es simétrico) y despachan el caso en que $p$ divide a $m$ en una línea.

Lo que esto no demuestra. La demostración garantiza que descifrar funciona, no que romper RSA sea difícil. Sabemos que encontrar $d$ (o $\varphi(n)$) es tan difícil como factorizar $n$: quien tiene uno de los dos saca los primos enseguida. Pero no está demostrado que cualquier forma de descifrar sin $d$ obligue a factorizar; es un problema abierto, y hay indicios de que para exponentes $e$ pequeños podría no ser así (lo resume Boneh, 1999). La seguridad descansa en que nadie sabe factorizar deprisa ni romper RSA de otra manera, no en un teorema.

Dos avisos honestos

• El RSA «de libro» no es seguro. Si cifras $m^e \bmod n$ sin más, el mismo mensaje da siempre el mismo cifrado, el cifrado deja ver información parcial del mensaje y hay ataques que aprovechan que el producto de dos cifrados es el cifrado del producto. Boneh lo resume así: para que RSA sea seguro hay que añadir azar al cifrar. Por eso el estándar PKCS #1 (RFC 8017) usa RSA solo dentro de esquemas con relleno y, en las aplicaciones nuevas, pide OAEP para cifrar y PSS para firmar.
• Las claves de juguete no protegen nada. Con $n = 2747$ basta probar divisores hasta 41. El NIST (Estados Unidos) exige claves de 2048 bits o más para el uso de su Gobierno federal, es decir, $n$ de unas 617 cifras decimales.

Un dato histórico

Clifford Cocks, matemático del GCHQ británico, escribió el 20 de noviembre de 1973 una nota con un sistema del mismo tipo: el receptor publica $N = PQ$ y recupera el mensaje con el algoritmo de Euclides y aritmética módulo $P$ y $Q$. El propio GCHQ atribuye a Cocks el sistema hoy conocido como RSA. El artículo técnico de Rivest, Shamir y Adleman se publicó en 1978, aunque el sistema ya se había dado a conocer en agosto de 1977 en la revista Scientific American (lo cuenta Boneh).