O RSA (Rivest-Shamir-Adleman) é um criptosistema assimétrico desenvolvido por Ron Rivest, Adi Shamir e Len Adleman em 1979
É um algoritmo baseado na dificuldade computacional da fatoração de um número inteiro grande em dois primos e do “problema RSA”, que consiste em calcular a mensagem específica que gera um criptotexto interceptado.
Suponha que Alice deseja receber uma mensagem criptografada na forma de um número inteiro de Beto. De acordo com o algoritmo RSA, eles procederão da seguinte maneira:
Beto toma a informação a ser transmitida \(x \in \mathbb{Z}_n\) e calcula \(y = x^p \text{ mod }n\), que é o texto ilegível.
A informação \(y\) é transmitida para Alice.
Alice obtém a mensagem ilegível \(y\) e calcula \[ y^s \text{ mod }n = (x^p)^s \text{ mod }n = x^{ps} \text{ mod }n \stackrel{(*)}= x \text{ mod n} = x \] Onde a igualdade \((*)\) é uma consequência demonstrável da definição de \(p\) e \(\Phi(n)\) e do Pequeno Teorema de Euler.
O resultado \(x\) é a mensagem legível de Beto.
Em protocolos implementados, é comum chamar a quantidade pública \(p\) de “expoente”, normalmente denotada \(e\), a quantidade pública \(n\) de “módulo”, normalmente denotada \(N\) e a quantidade secreta \(n\) de “chave”, normalmente denotada \(d\).
O valor mais comum escolhido para o expoente é \(65537 = 10001_{16}\). Note que o valor do expoente ser o mesmo não implica que o segredo \(s\) é o mesmo, afinal, o valor \(\Phi(n)\) depende de \(n\) e é secreto.[^3]
O algoritmo RSA também pode ser utilizado para assinar mensagens. Neste caso, basta Alice enviar a mensagem \(x\) junto da sua assinatura \(y = x^s \text{ mod }n\). Então, para verificar que de fato foi Alice que enviou a mensagem \(x\), Beto pode decriptografar \(y\) com a chave pública de Alice, fazendo \(y^{p} \text{ mod }n\), e comparar com a mensagem \(x\).
Se ambas forem idênticas, apenas Alice pode ter enviado \(x\), pois apenas ela possui a chave secreta \(s\) cuja criptografia é desfeita pela chave pública \(p\).
Além disso, Beto também pode assinar o mesmo documento com sua chave secreta e enviar a Alice, que usará a chave pública de Beto para decriptografar. Se a mensagem obtida for igual à que ela enviou originalmente, Alice sabe que Beto de fato leu e consentiu com aquela mensagem.
Apesar dessa possibilidade, assinatura RSA direta (i.e. como descrita aqui) é considerada insegura (por que?).
Existem algumas formas de se quebrar o RSA: 1. Buscar diretamente a informação \(x\) tal que \(y = x^p \text{ mod }n\). Esse problema é conhecido como o “problema RSA”, para o qual não é conhecido algoritmo eficiente. 2. Fatorar \(n\) em \(p \cdot q\), de maneira que se possa obter \(\Phi(n)\) e, portanto, \(s = p ^{-1} \text{ mod }\Phi(n)\). Esse é o Problema da Fatoração, para o qual não é conhecido algoritmo eficiente. 3. Determinar \(\Phi(n)\) sem fatorar \(n\). É possível provar que esse problema é pelo menos tão difícil quanto fatorar \(n\).
Suponha que \(\Phi(n)\) foi determinado sem que se conheça \(n\). Dessa maneira, podemos fazer \[ \Phi(n) = (q-1)(r-1) = qr -q -r +1 = n - (q+r) + 1 \] Como \(n\) é conhecido, podemos determinar \(q+r\). Além disso, \[ (q+r)^2 = q^2 + 2qr + r^2 = (q^2 - 2qr + r^2) - 4qr = (q-r)^2 - 4n \] E, como \(n\) é conhecido, podemos calcular \(q-r\).
Finalmente, \(q\) é metade da soma de \(q+r\) com \(q-r\), e \(r\) é \(n/q\). Dessa forma, fatoramos \(n\) em \(q\) e \(r\).
Exige-se que \(p\) e \(q\) sejam da mesma ordem pois existem algoritmos de fatoração cujo tempo de execução depende somente do menor valor entre \(p\) e \(q\). Estes são os chamados algoritmos de uso especial, ou de Primeira Categoria.↩︎
Se esse valor obtido \(p\) for muito pequeno, é aconselhavel que \(s\) seja sorteado novamente, pois isso pode acarretar em \(x^p < n\), o que significa que a mensagem nunca passa pelo módulo \(n\) e, dessa maneira, \(y ^{1/p} = x\).↩︎