Em criptografia, o problema RSA resume a tarefa de realizar uma operação de chave privada RSA dada somente à chave pública. O algoritmo RSA dar origem a uma mensagem para um expoente módulo um número composto N cujos fatores são desconhecidos. Como tal, a tarefa pode ser perfeitamente descrita como encontrar a eth raízes de um número arbitrário, módulo N. Para chaves RSA de grandes tamanhos (acima de 1024 bits), nenhum método eficiente para resolver este problema é conhecido; se um método eficiente fosse desenvolvido, isso ameaçaria a atual ou eventual segurança dos sistemas criptográficos baseados no RSA – tanto para criptográfica de chave pública quanto para assinaturas digitais.
Mais especificamente, o problema RSA é: dado uma chave pública (N, e) e um cifrotexto C ≡ Pe (mod N), para calcular eficientemente P. A estrutura da chave pública RSA requer que N seja um semiprimo grande (i.e., o produto de dois primos grandes), 2 < e < N é co-primo para φ(N), e 0 ≤ C < N. C é escolhido aleatoriamente dentro desse universo; para especificar o problema com completa precisão é necessário também especificar como N e e são gerados, que dependerá da precisão da geração aleatória do par de chaves RSA em uso.
A partir de 2010, a maneira conhecida mais eficiente de resolver o problema RSA é primeiro fatorar o módulo N, que se acredita ser impraticável se N é suficientemente grande (ver fatoração de inteiros). A configuração de rotina da chave RSA já torna público o expoente e, com este primo fatorado, para o expoente privado d, e então o mesmo algoritmo permite qualquer pessoa que fatore N obter a chave privada. Qualquer C (cifrotexto) pode então ser decriptado com a chave privada.
Assim como não existem provas que fatoração de inteiros é computacionalmente difícil, também não existem provas que o problema RSA é similarmente difícil.h [1] Pelo método acima, o problema RSA é ao menos tão fácil quanto o da fatoração, mas ele pode ser mais fácil. Na verdade, existem fortes pontos evidenciando esta conclusão: que o método para quebrar o RSA não pode ser necessariamente convertido em um método para fatorar semiprimos grandes. Isto é talvez mais fácil ver pelo enorme exagero da abordagem da fatoração: o problema RSA pergunta-nos como decriptar um cifrotexto arbitrário, considerando que o método da fatoração revela a chave privada: assim decriptando todos os cifrotextos arbitrários, e permite também realizar encriptações de chave privada arbitrárias no RSA. Nessa mesma linha, encontrando o expoente de decriptação d é na verdade computacionalmente equivalmente a fatorar N, mesmo embora o problema RSA não perguntar por d. Um algoritmo para isso é, por exemplo, dado em.[2]
Além do problema RSA, a RSA tem uma estrutura matemática particular que pode ser potencialmente explorada sem resolver diretamente o problema RSA. Para alcançar o problema pleno RSA, um criptossistema baseado no RSA deve também usar um cenário de “acochoamento” (Padding scheme) como o OAEP. Para proteger contra este tipo de problemas estruturais na RSA.
Nota e referências
- Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «RSA problem», especificamente desta versão.
