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).$$