Um método, conhecido como criptografia RSA, foi desenvolvido pelos matemáticos Ron Rivest, Adi Shamir, and Leonard Adleman e foi publicado em 1977.
\[
\varphi(n)=|\{a\in\{1,\ldots,n\}\mid \mbox{mdc}(a,n)=1\}|
\]
para todo natural $n$. Demonstra, para primos $p$ e $q$ distintos, que
\[
\varphi(pq)=(p-1)(q-1).
\]
Assuma que Alice quer enviar uma mensagem para Bob. Eles seguem os seguintes passos:
- Bob escolhe um número $n$ tal que $n$ é produto de dois primos $p$ e $q$ e escolhe um número $e\in\{2,\ldots,n-1\}$ tal que $\mbox{mdc}(e,\varphi(n))=1$. Isso implica que $e$ é invertível módulo $\varphi(n)$; ou seja existe $d\in\{1,\ldots,\varphi(n)\}$ tal que
\[
ed\equiv 1\pmod{\varphi(n)}.
\] - Bob publica o par $(n,e)$ dos números. Este é a chave pública do Bob e está disponível publicamente para toda pessoa que quer enviar mensagem sigilosa para o Bob. Em particular esta chave é conhecida por Alice.
- O Bob guarda os números $(\varphi(n),d)$ em sigilo. Esta é a chave privada do Bob.
- A mensagem da Alice é um número $b$ entre $1$ e $n$. A Alice vai calcular
\[
C(b)=\mbox{o resto de $b^e$ por $n$}.
\]
Note que Alice conhece os números $e$ e $n$ e consegue calcular $C(b)$ (usando o algoritmo de exponenciação rápida.) O número $C(b)$ é a mensagem codificada. - Alice envia $C(b)$ para o Bob.
- Ao receber a mensagem $c=C(b)$ da Alice, Bob calcula
\[
D( c)=\mbox{o resto de $c^d$ módulo $n$}.
\]
O número obtido $D(c)$ é a mensagem descodificada. - O número $D(c)$ coincide com a mensagem original $b$ da Alice; ou seja, o Bob conseguiu descodificar a mensagem da Alice.
\[
de+60k=1
\]
com algum $k$ e assim pode ser encontrado usando o Algoritmo de Euclides. De fato, $d=37$. A mensagem que a Alice manda para o Bob é um número entre $1$ e $76$. Assuma que a mensagem da Alice é o número 30. Então Alice calcula o resto de $30^{13}$ módulo $77$ que dá $72$. Então o mensagem da Alice é $C(30)=72$. Ao receber esta mensagem, o Bob calcula o resto de $D(72)=72^{37}\equiv 30\pmod{77}$ que foi a mensagem original da Alice.
Vimos no exemplo como o método funciona, mas queremos entender teoricamente porque ele funciona.
\[
D(C(b))=(b^e)^d=b^{ed}\pmod n.
\]
Para provar que $D(C(b))=b$, precisa-se verificar que $b^{ed}\equiv b\pmod n$; ou seja $n\mid (b^{ed}-b)$. Como $n=pq$ é produto de dois primos, é suficiente (e necessário) verificar que $p\mid (b^{ed}-b)$ e $q\mid (b^{ed}-b)$. Nós fazemos esta verificação para $p$, o primo $q$ pode ser tratado com argumento igual.
Primeiro, se $p\mid b$, então $p\mid (b^{ed}-b)$ e a afirmação é verdadeira. Assuma agora que $p\nmid b$ e lembre que o Pequeno Teorema de Fermat implica neste caso que $b^{p-1}\equiv 1\pmod p$. Como $ed\equiv 1\pmod{\varphi(n)}$, tem-se que
\[
ed=k\varphi(n)+1=k(p-1)(q-1)+1
\]
com algum $k$ inteiro. Então
\[
b^{ed}=b^{k(p-1)(q-1)+1}=(b^{p-1})^{k(q-1)}\cdot b\equiv b\pmod p.
\]
Obtivemos então que $b^{ed}\equiv b\pmod n$ que equivale à afirmação que $D(C(b))=b$ que implica que o método usado por Bob vai descodificar a mensagem da Alice.
A segurança do método está baseado no fato que para aplicar a função $D$ de descodificação, o Bob precisa calcular o valor de $d$ que precisa do valor de $\varphi(n)=(p-1)(q-1)$. Claramente, se alguém sabe $p$ e $q$ então consegue calcular $\varphi(n)$ e também a chave privada $d$. Mas a chave pública contém o apenas o número $n$ e não os seus fatores $p$ e $q$. Neste momento nós não conhecemos nenhum algoritmo que pode ser usado para fatorar números muito grandes.
O seguinte resultado implica que a determinação de $\varphi(n)$ é computacionalmente equivalente à determinação dos fatores $p$ e $q$ de $n$.
\[
\varphi(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1
\]
e assim conhecemos $p+q=n-\varphi(n)+1$. Além disso,
\[
(p+q)^2-4n=p^2+2pq+q^2-4pq=p^2-2pq+q^2=(p-q)^2
\]
e assim
\[
p-q=\sqrt{(p+q)^2-4n}.
\]
Isto implica, que conseguimos determinar o valor de $p-q$. Sabendo $p+q$ e $p-q$, é fácil determinar $p$ e $q$.
Vale mencionar que existe um algoritmo quântico eficiente para determinar a fatoração de um número. Este algoritmo é conhecido como o Algoritmo de Shor e foi publicado em 1994. Este algoritmo neste momento não implica nenhum perigo para a segurança de mensagens criptografadas, mas no futuro os computadores quânticos podem se desenvolver o suficiente para poder quebrar o algoritmo RSA. Neste momento muitos matemáticos trabalham no desenvolvimento e algoritmos que são seguros contra ataques de computadores quânticos (criptografia pós-quântica).