Descripción del algoritmo

Es realmente muy simple, como puede verse a continuación (¡utiliza solamente aritmética modular!):

1. Encuentre dos números primos muy grandes $P$ y $Q$ (por ejemplo, cuya representación binaria sea de $1024$ bits).¹³
2. Elija un número $E$, tal que:
   1. $E>1$,
   2. $E<P\cdot Q$,
   3. $E$ y $(P-1)\cdot (Q-1)$ sean co-primos (no tengan factores primos distintos de $1$ en común o, lo que es equivalente, su máximo común divisor sea $1$)¹⁴.
3. Calcule $D$ tal que $(D\cdot E-1)$ sea divisible por $(P-1)\cdot (Q-1)$. Para ello basta encontrar un entero $X$ que haga que $\frac{X\cdot (P-1)\cdot (Q-1)+1}{E}$ sea entero, siendo esto último el valor de $D$.
4. La función de cifrado es $C=(M^{E})$ mod $P\cdot Q$, donde $C$ es el mensaje cifrado (un entero positivo) y $M$ es el mensaje original ($M$ debe ser menor que $P\cdot Q$).¹⁵
5. La función de descifrado es $M=(C^{D})$ mod $P\cdot Q$.

La clave pública es el par $(P\cdot Q,E)$. La clave privada es el número $D$.

La clave pública puede difundirse libremente, ya que no se conoce una forma simple de calcular $D$, $P$ o $Q$ dados solamente $P\cdot Q$ y $E$.

Para calcular $D$ es necesario calcular $P$ y $Q$. Dado que sólo conocemos $P\cdot Q$, y gracias al teorema fundamental de la aritmética¹⁶, podemos factorizar este número para descubrir $P$ y $Q$. El inconveniente radica en que la forma más eficiente de factorizar un número $n$ que se conoce en la actualidad¹⁷ es $O(2^{n})$. Esto significa que toma una cantidad de tiempo exponencial respecto del tamaño del número a factorizar. Si $P$ y $Q$ son dos enteros cuya representación binaria ocupa $1024$ bits, factorizar su producto puede llevarle a cualquier computadora varios milenios, como mínimo (esto sin tener en cuenta el espacio necesario para realizar los cálculos).