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?