¿Dónde radica la seguridad del criptosistema RSA?

Conocer la aplicación de descifrado $D$ equivale a conocer la clave privada $d$, que sólo posee Bob. Y esta clave secreta $d$ no puede conocerse a partir de $(n, e)$ sin el conocimiento de $r=\varphi(n)=(p-1)(p-1)$ (recuérdese que $d$ es un representante del inverso de la clase de $e$ módulo $r=(p-1)(q-1))$. Puede razonarse que conocer $r$ es igual de difícil que saber factorizar $n$ como producto de los primos $p$ y $q$. Si estos primos se han elegido suficientemente grandes (y satisfaciendo ciertas condiciones buenas), $n$ tendrá un valor tan grande que será imposible factorizarlo con los recursos computacionales existentes en este momento. Aquí radica la seguridad del criptosistema RSA. Si una supuesta espía Eve interceptara el mensaje que Alice le envía a Bob, le resultaría imposible averiguar la clave secreta $d$ (y, por tanto, descifrar el mensaje) aún sabiendo la clave pública $(n,e)$.

Para probar que el proceso de descifrado anteriormente descrito es correcto, hay que demostrar que las aplicaciones de cifrado, C, y descifrado, D, son inversas una de la otra, es decir, $C\circ D=D\circ C=Id$, donde $Id: \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ es la aplicación identidad. Como, para todo $\overline{x}\in \mathbb{Z}_n$, $C(D(\overline{x}))=D(C(\overline{x}))=\overline{x}^{ed}$, es suficiente demostrar que $$x^{ed}\equiv x\; ({\rm mod}\; n)\;\mbox{para todo $x\in \mathbb{Z}$}.$$

Sea $x$ un entero arbitrario. Si $x$ es divisible por $n$ entonces la congruencia anterior es obvia. Por tanto, podemos asumir que $x$ no es divisible por $n$. Como $ed\equiv 1\; ({\rm mod}\; r)$, existe un entero $\lambda$ tal que $ed=1+\lambda r$. Luego $x^{ed}=x (x^r)^{\lambda}$.

Vamos a distinguir dos casos:

Caso 1: $x$ y $n$ son coprimos. En este caso, la clase $\overline{x}\in \mathbb{Z}_n$ tiene inverso multiplicativo en $\mathbb{Z}$ (por la Proposición 1.9 de los apuntes, que veremos). Además, en la Sección 1.10 del Capítulo 1, veremos también que el conjunto $U_n$ formado por los elementos de $\mathbb{Z}_n$ que tienen inverso multiplicativo es un grupo (con el producto) cuyo orden es $\varphi(n)=r$ (la función de Euler de $n$). Como $\overline{x}\in U_n$, por un corolario del Teorema de Lagrange (que veremos, previsiblemente, en la clase del jueves) el orden de $\overline{x}$ en $U_n$ es un divisor de $r=\varphi(n)$ y, por tanto: $\overline{x}^{r}=\overline{1}$, es decir, $x^{r}\equiv 1\; ({\rm mod}\; n)$. Así pues, $$x^{ed}=x (x^r)^{\lambda}\equiv x\; ({\rm mod}\; n).$$

Caso 2: $x$ y $n$ no son coprimos. En este caso, como $n=p q$, $x$ ha de ser divisible por uno de los dos primos $p$ y $q$, pero no por ambos (al no ser $n$ divisor de $x$). Supongamos, sin pérdida de generalidad, que $p$ divide a $x$ (se razonaría igual si $q$ divide a $x$) y, por tanto, $q$ es coprimo con $x$. Como consecuencia de esto último, la clase de $x$ en $\mathbb{Z}_q$ (que vamos a denotar también por $\overline{x}$; ¡que el abuso notacional no te confunda, por favor!) tiene inverso multiplicativo, luego pertenece a $U_{q}$. Como el grupo $U_q$ tiene orden $\varphi(q)=q-1$, razonando igual que antes se tiene que el orden de $\overline{x}$ en $U_q$ es un divisor de $q-1$ y, por tanto, $\overline{x}^{q-1}=\overline{1}$ en $\mathbb{Z_q}$. Luego $\overline{x}^r=(\overline{x}^{q-1})^{p-1}=\overline{1}$ en $\mathbb{Z}_q$. Por tanto, $x^{ed}=x (x^r)^{\lambda}\equiv x\; ({\rm mod}\; q)$, es decir, $x^{ed}-x$ es un múltiplo de $q$.

Por otro lado (continuando dentro del Caso 2), como $p$ divide a $x$ se cumple, obviamente, que $x^{ed}\equiv 0 \equiv x\; ({\rm mod}\; p)$, es decir, $x^{ed}-x$ es un múltiplo de $p$.

Así, hemos demostrado que $x^{ed}-x$ es, a la vez, múltiplo de $p$ y de $q$. Luego es múltiplo de $n=p q$, es decir, $$x^{ed}\equiv x\; ({\rm mod}\; n).$$

Con esto, acabamos de demostrar que las aplicaciones $C$ y $D$ son inversas una de la otra.

Vamos a diseñar ahora una «función de cifrado», es decir, una función $$C:\mathbb{Z}_n\rightarrow \mathbb{Z}_n$$ tal que, si $\overline{m}$ es el mensaje que Alice quiere cifrar (recordad que Alice ha «preparado» el mensaje para transformarlo en una clase de congruencia módulo $n$), el resultado del cifrado será la imagen de $\overline{m}$ por esta función, es decir, $C(\overline{m})$. Este será el valor que Alice enviará a Bob.

La función de cifrado se define de la siguiente manera: $$C(\overline{x}):=\overline{x}^e$$ para todo $\overline{x}\in \mathbb{Z}_n$ (¡OJO! Aquí la «barrita» superior significa «clase módulo $n$»). Dicho de otro modo, para cifrar el mensaje $\overline{m}$, Alice calculará la clase de $\mathbb{Z}_n$ consistente en multiplicar la clase $\overline{m}$ consigo misma $e$ veces (con el producto en $\mathbb{Z}_n$, claro está).

Por ejemplo, consideremos las claves del anterior ejemplo e imaginemos que el mensaje que quiere cifrar Alice es $\overline{m}=\overline{12423}\in \mathbb{Z}_{25877}$. Entonces se tiene que $$C(\overline{m})=\overline{12423}^{e}=\overline{12423}^{1321}=\overline{14946}\in \mathbb{Z}_{25877}.$$ Este es el mensaje que Alice envía a Bob.

Vamos a diseñar ahora una «función de descifrado», es decir, una función $$D:\mathbb{Z}_n\rightarrow \mathbb{Z}_n$$ tal que, si Bob aplica esta función al mensaje $C(\overline{m})$ que le ha enviado Alice, obtiene el mensaje original $\overline{m}$. Dicho de otro modo, tal que $D(C(\overline{m}))=\overline{m}$. Un poco de reflexión nos hará concluir que, lo que queremos es que $C$ sea una función biyectiva y $D$ sea su inversa.

Esta función de descifrado $D$ se define de la siguiente manera: $$D(\overline{x}):=\overline{x}^d$$ para todo $\overline{x}\in \mathbb{Z}_n$.

En el caso de nuestro ejemplo, si aplicáis esta función de descifrado $D$ a $C(\overline{m})=\overline{14946}$ obtendréis $$D(C(\overline{m}))=D(\overline{14946})=\overline{14946}^{d}=\overline{14946}^{17881}=\overline{m}.$$

¿Por qué esto funciona? ¿Cómo se justifica? Lo veremos en el siguiente post.

Ya hemos visto que la clave pública del criptosistema RSA consiste en un par $(n,e)$, donde $n$ es el producto de dos primos muy grandes, $p$ y $q$, y $e$ es un entero entre $1$ y $r-1$ coprimo con $r$, donde $r=\varphi(n)=\varphi(p q)=(p-1)(q-1)$. Veamos ahora cómo Bob determina una clave privada (que sólo conocerá él).

Consideramos la clase de $e$ en el conjunto de clases de congruencia módulo $r$, $\mathbb{Z}_r$ (recuérdese que $e$ es un entero entre $1$ y $r-1$; por tanto, se trata de una clase distinta de la del cero). Como es habitual, denotemos por $\overline{e}$ a esta clase. Consderamos ahora la operación producto en $\mathbb{Z}_r$. Como ya sabéis, no todo elemento de $\mathbb{Z}_r\setminus \{\overline{0}\}$ tiene inverso multiplicativo (es decir, no para toda clase $\overline{x}\neq \overline{0}$ existe otra clase $\overline{x}^{-1}$ tal que $\overline{x}\cdot \overline{x}=\overline{1}$). Pero, ¿cuáles son las clases de $\mathbb{Z}_r\setminus \{\overline{0}\}$ que tienen inverso multiplicativo? La respuesta la tenéis en la Proposición 1.9 de los apuntes (que veremos más adelante): tienen inverso exactamente aquellas clases $\overline{k}$, con $1\leq k\leq r-1$, tales que $k$ y $r$ son coprimos. Revisad ahora las condiciones que satisface $e$: ¡son exactamente estas! Por tanto, la clase de $e$ en $\mathbb{Z}_n$, $\overline{e}$, tiene inverso multiplicativo. Luego existe un entero $d$ tal que $1<d<r-1$ y $\overline{d}=\overline{e}^{-1}$ en $\mathbb{Z}_r$. Dicho de otro modo, $$ed\equiv 1\;({\rm mod}\; r).$$

Este entero $d$ es la clave privada de Bob.

Ahora repasemos:

• Para generar una clave pública, Bob elige dos primos muy grandes $p$ y $q$ y considera su producto $n=p q$. Después calcula $r:=\varphi(n)=(p-1)(q-1)$ y elige un entero $e$ tal que $1\leq e\leq r-1$ y ${\rm mcd}(e,r)=1$. La clave pública es el par $(n,e)$.
• Para generar una clave privada, Bob calcula el entero $d$ tal que $1\leq d\leq r-1$ y tal que su clase en $\mathbb{Z}_r$ sea el inverso multiplicativo de la clase de $e$, es decir, tal que $ed\equiv 1\;({\rm mod}\;r)$. La clave privada es este entero $d$.

En nuestro ejemplo «de juguete» anterior (recordad: $n=113\cdot 229=25877$ y $e=1321$), Bob podría tomar como clave privada $d:=17881$ (podéis verificar que la clase de $d$ es el inverso multiplicativo de la clase de $e$ módulo $r$).

La siguiente pregunta es: ¿cómo usará Alice la clave pública $(n,e)$ para cifrar mensajes, y cómo usará Bob su clave privada $d$ para descifrarlos?

Recordemos que tenemos a Alice y a Bob, y que Alice quiere enviar un mensaje encriptado a Bob (usando una clave pública) para que Bob lo descifre (usando SU clave privada). Para ello, Bob considera dos números primos muy grandes $p$ y $q$ y los multiplica, formando un entero muy grande $n:=pq$. Este valor $n$ es conocido por Alice y por cualquier persona que quiera y/o pueda conocerlo (¡Ojo! el valor $n$ es público, pero NO lo son los factores $p$ y $q$), y forma parte de la clave pública necesaria para cifrar mensajes para enviar a Bob. Como más adelante recordaremos, la seguridad del sistema radica en que es computacionalmente muy difícil averiguar los factores primos $p$ y $q$ a partir de $n$ si éstos son muy grandes.

Veamos ahora cómo calcular la segunda parte de la clave pública. Para esto Bob (que es el único conocedor de los primos $p$ y $q$) calcula el siguiente valor: $$r:=\varphi(n)=(p-1)(q-1),$$ es decir, la función de Euler de $n$. Para él es muy fácil de calcular pues, como $n$ es el producto de dos primos $p$ y $q$, y ÉL CONOCE ESTOS PRIMOS, por una propiedad de la función de Euler sabe que $\varphi(n)=(p-1)(q-1)$ (véase https://es.wikipedia.org/wiki/Función_φ_de_Euler). Puede razonarse que la dificultad de calcular $r$ a partir únicamente de $n$ (que es muy grande) es similar a la dificultad de obtener los primos $p$ y $q$ sólo a partir de $n$. Una vez calculado este valor $r$, Bob elige arbitrariamente un número entero $e$ tal que $0<e<r$ y tal que ${\rm mcd}(e,r)=1$. El par formado por $(n,e)$ constituye la clave pública completa, y es la información que Bob da a conocer a Alice (y a quien quiera saberla) para que ésta pueda encriptar el mensaje que quiere transmitir a Bob.

Vamos a ver un ejemplo nada realista (con números primos «de risa») para que se entienda bien. Bob podría elegir los primos $p=113$ y $q=229$. El valor $n$ es igual a $113\cdot 229=25877$, y el valor $r$ es igual a $\varphi(113\cdot 229)=112\cdot 228=25536$. Bob elige como $e$ el valor $1321$ (que está entre $1$ y $r-1$ y es coprimo con $r$).

La clave pública sería el par $$(n=25877, e=1321).$$

El sistema criptográfico RSA debe su nombre a sus inventores, Ronald Rivest, Adi Shamir y Leonard Adleman, que publicaron por primera vez el método en 1977. Se trata uno de los criptosistemas más utilizados hoy en día, presente como método de seguridad en transacciones bancarias, firma digital, etc. Permite intercambiar información de forma segura entre varios participantes. Cada participante tiene dos claves: una clave privada, que utiliza para descifrar los mensajes que recibe, y una clave pública, que utilizan los demás participantes cuando desean cifrar un mensaje dirigido a él. Estas dos claves son inversas entre sí, pero debe ser computacionalmente imposible deducir la clave privada a partir de la pública (y en eso radica la seguridad del sistema).

Vamos a considerar dos personajes, Alice y Bob. Alice quiere enviar un mensaje encriptado a Bob. Para ello, Bob debe generar una clave pública para comunicársela a Alice (y a cualquiera que quiera conocerla, pues no es secreta). Esta clave la utilizará Alice para encriptar el mensaje que quiere enviar a Bob. Para generar una clave pública, deben considerarse dos números primos $p$ y $q$ muy grandes (y con ciertas condiciones) y multiplicarlos. Su producto, $n:=pq$, constituye una parte de la clave pública del criptosistema (que todo el mundo conoce, o puede conocer).

Para poder aplicar toda la “maquinaria algebraica” que necesitamos, Alice transforma su mensaje en un elemento del conjunto de las clases de congruencia módulo $n$, $\mathbb{Z}_n$ (o lo divide en varios “submensajes” y transforma cada uno de ellos de esta manera); hay varias maneras de hacer esto, pero no vamos a entrar aquí en semejante disquisición. Por lo que a nosotros respecta, el mensaje se “prepara” de manera que se transforma en un elemento de $\mathbb{Z}_n$ (o en varios de ellos, si se parte en varios submensajes).

¿Cómo se genera la parte que falta de la clave pública? ¿Cómo genera Bob una clave privada? ¿Cómo se encripta un mensaje? ¿Cómo se descifra? ¿Por qué el método es seguro? Aquí entran en juego conceptos algebraicos que veremos en este curso. En próximos posts revelaremos el modo :).