Problema RSA

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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.


Ícone de esboço Este artigo sobre Criptografia é um esboço. Você pode ajudar a Wikipédia expandindo-o.


Nota e referências

  1. Breaking RSA may not be equivalent to factoring. Página visitada em 17 de junho de 2011.
  2. Handbook of Applied Cryptography, Ch. 8. Página visitada em 17 de junho de 2011.