Dada a RSA, por que não sabemos se a criptografia de chave pública é possível?

23

Eu estava na wikipedia na lista de problemas não resolvidos de ciência da computação e descobri o seguinte: É possível a criptografia de chave pública?

Eu pensei que a criptografia RSA era uma forma de criptografia de chave pública? Por que isso é um problema?

Namster
fonte
5
Nem sabemos se a criptografia simétrica pode ser segura, e isso é uma conjectura muito mais fraca do que a criptografia de chave pública sendo segura.
CodesInChaos
@CodesInChaos Isso é verdade desde que falemos de segurança com base na complexidade computacional. Mas se você está considerando a segurança teórica da informação, há construções comprovadamente seguras, como o one-time-pad para criptografia e o Wegman-Carter para autenticação de mensagens.
kasperd

Respostas:

31

Não sabemos ao certo se o RSA é seguro. Pode ser que o RSA possa ser quebrado em tempo polinomial, por exemplo, se o fatoramento puder ser feito com eficiência. O que está aberto é a existência de um sistema de criptografia de chave pública comprovadamente seguro . Não sabemos ao certo se esse sistema de criptografia existe; pelo que sabemos, todo sistema de criptografia pode ser quebrado com eficiência.

Um problema diferente e não relacionado com o RSA é que ele pode ser quebrado por computadores quânticos. Esse é um problema não relacionado, pois a definição de um sistema de criptografia de chave pública seguro exige apenas que o sistema de criptografia não possa ser quebrado por computadores clássicos (não quânticos).

Na prática, porém, o RSA parece seguro e é usado o tempo todo. Isto é devido à diferença entre teoria e prática. Embora teoricamente não tenhamos certeza de que o RSA é seguro, na prática, precisamos usar algum sistema de criptografia de chave pública, e o RSA é uma boa opção, pois as pessoas tentaram quebrá-lo e falharam. De um modo geral, um sistema de criptografia conhecido com o qual as pessoas se preocupam é mais seguro do que um sistema obscuro, pois resistiu às tentativas dos criptografadores. Isso não constitui uma prova de que é seguro - pode não ser - mas é o melhor que podemos fazer.

Yuval Filmus
fonte
4
Em poucas palavras: Segura até quebrar.
Ismael Miguel
2
Ótima resposta. Eu também acrescentaria que qualquer criptografia é entregue apenas com um prazo de baixa probabilidade de ser quebrado. Ninguém fornece um sistema de criptografia e afirma que é seguro. Eles sempre dizem que não é provável que seja quebrado nos próximos 5 anos ou mais. Esse é um problema para as vendas, pois, muitas vezes, os clientes não técnicos veem isso como uma fraqueza declarada.
RSinohara
Na verdade, essa é uma falha geral na ciência da computação: o CS é muito bom em provar quanto tempo levará um algoritmo, mas muito fraco em provar que não existem algoritmos mais rápidos .
RBarryYoung
3

Aqui estão alguns outros ângulos / detalhes sobre esta questão, mais específicos e geralmente. Como a YF escreve em um comentário, apesar das aparências, a RSA não é comprovadamente tão difícil quanto a fatoração. A quebra da RSA envolve o problema de log discreto que, obviamente, está intimamente relacionado à fatoração de complexidade, mas não provou ser a mesma complexidade. Mas (como apontado), nem mesmo o fatoração foi comprovado.

YF também menciona computação quântica. Como os especialistas sabem bem, o RSA não é seguro contra a computação quântica, que provou ser capaz de levar em consideração o tempo P usando o algoritmo Shors . O algoritmo Shors foi considerado um avanço na época. E outro avanço a ser mencionado em uma área "próxima" é o algoritmo de primalidade AKS, que provou que o teste de primalidade está em P. Avanços teóricos na teoria da complexidade são raros, mas não são inéditos.

YF não menciona, mas está sempre à espreita no fundo dessas perguntas, a "grande questão" de P =? NP ainda está aberta. Pensa-se geralmente que "a criptografia algorítmica poderia ser impossível" (exceto para blocos únicos) se P = NP, que geralmente é desacreditado pelos especialistas.

Uma excelente maneira de conceituar cientificamente isso é o Impagliazzos 5 worlds , visão geral da Kabanets . notavelmente, os teóricos da complexidade não sabem "em qual dos cinco mundos em que vivemos", embora exista evidência circunstancial que inclua alguns aspectos. O mundo em que vivemos depende das conjecturas da teoria da complexidade aberta. Eles também se relacionam a problemas abertos em existências de funções de alçapão e funções de mão única . (RSA é suposto ser os dois.) Houve uma conferência de pesquisa de 2009 sobre os mundos Impagliazzos, com o pensamento mais recente relatado.

vzn
fonte
1
veja também o status dos mundos Impagliazzos / Ciência da Computação Teórica . em resumo, aproximadamente, a RSA é considerada pelos especialistas como plausível ou provavelmente segura, mas não comprovadamente segura, e essa lacuna elimina muitas das maiores questões em aberto no campo.
vzn
2

Uma coisa que precisa ser definida aqui é a definição de possível. Existem duas maneiras de responder a isso. A primeira é: um sistema de criptografia de chave pública pode ser considerado teoricamente seguro? No sentido mais amplo, isso exige que o algoritmo seja seguro, mesmo quando sujeito a um ataque envolvendo poder computacional infinito. Existe um sistema conhecido que conseguiu isso, o teclado único, mas isso é apenas na teoria, pois não podemos criar os números verdadeiramente aleatórios necessários e é uma chave privada. A segunda maneira pela qual a pergunta pode ser vista é: um sistema de criptografia de chave pública pode ser considerado incondicionalmente seguro? Essa segunda definição é mais flexível. No caso da RSA, se alguém provar que a fatoração inteira é tão difícil quanto atualmente pensamos, e provar que não há outras suposições ou falhas no sistema, então o RSA seria incondicionalmente seguro. A segurança incondicional elimina o requisito de poder computacional infinito e o torna impossível no universo físico. Como todos os nossos algoritmos de chave pública se baseiam em suposições massivas sobre a computabilidade, eles não atendem à segunda definição.

lPlant
fonte
Quebrar a RSA não é equivalente a fatorar; é potencialmente mais fácil.
Yuval Filmus
Esta resposta está confusa. O bloco único não é um sistema de criptografia de chave pública, portanto, não é correto que o bloco único tenha conseguido isso. A resposta para "um sistema de criptografia de chave pública pode ser considerado teoricamente seguro?" é não". Além disso, não há provas conhecidas de que "fatorar é difícil" implica "RSA é seguro"; de fato, há razões para suspeitar que pode não haver redução dessa forma.
DW