Um dos algoritmos assimétricos de chave pública mais amplamente utilizado baseia-se na teoria dos números primos. Seu funcionamento é descrito a seguir:

- Parte de uma premissa associado a um conceito denominado fatoração, em que é fácil multiplicar dois números primos para obter um terceiro número, mas é muito difícil recuperar os dois primos a partir daquele terceiro número. Por exemplo, os fatores primos de 3.337 são 47 e 71.

- Gerar a chave pública envolve multiplicar dois primos grandes. Derivar a chave privada a partir da chave pública envolve fatorar um grande número. Se o número for grande o suficiente e bem escolhido, então ninguém pode fazer isso em uma quantidade de tempo razoável.

Esse algoritmo é conhecido por