Novo Algoritmo Quântico Permite Computador de 20 Milhões de Qubits Quebrar RSA de 2048 Bits em 8 Horas

É certo que computadores quânticos serão capazes de quebrar códigos de criptografia existentes usados para enviar mensagens secretas. Estas técnicas de criptografia nunca foram completamente confiáveis. Em vez disso, dependem de funções matemáticas complexas que funcionam em apenas uma direção, facilitando a criptografia de informações.

A segurança de tais técnicas baseia-se no tempo que um computador clássico leva para descriptografar a informação. Técnicas modernas de criptografia são praticamente inquebráveis, pois levaria milhares de anos para os computadores atuais decifrarem seu código.

No entanto, computadores quânticos conseguiriam quebrar esses códigos com facilidade, e estas máquinas estão bem mais próximas da realidade do que se esperava.

Recentemente, pesquisadores do Google e do Instituto Real de Tecnologia KTH na Suécia desenvolveram uma técnica mais eficiente que computadores quânticos poderiam usar para descriptografar mensagens secretas. Permitiria que computadores quânticos usassem menos recursos para realizar cálculos de quebra de código.

Computadores Quânticos Estão Se Tornando Mais Poderosos

Em 1994, o matemático americano Peter Shor desenvolveu um algoritmo quântico para fatorar números grandes exponencialmente mais rápido que os melhores algoritmos existentes rodando em um computador clássico. Ele sugeriu que uma máquina quântica suficientemente poderosa poderia quebrar técnicas modernas de criptografia com facilidade.

Na última década, muitos avanços foram feitos em computação quântica. Em 2012, cientistas conseguiram usar um computador quântico de 4 qubits para fatorar '143'. Dois anos depois, usaram uma máquina similar para fatorar '56153'.

Considerando a taxa de progresso, computadores quânticos logo seriam capazes de superar os computadores atuais. Pelo menos é o que cientistas esperavam alguns anos atrás.

Descobriu-se que fatorar números grandes em máquinas quânticas é muito mais difícil do que o previsto. Isso se deve ao ruído significativo em computadores quânticos grandes. O problema poderia ser resolvido usando códigos de correção de erro, que por sua vez exigem qubits extras.

Levando este fator de ruído em conta, um computador quântico precisaria de um bilhão de qubits para fatorar números de 2048 bits (ou descriptografar criptografia RSA de 2048 bits). No entanto, os computadores quânticos universais atuais possuem apenas 70 qubits.

Exponenciação Modular

O novo algoritmo permite que computadores quânticos façam esses cálculos com apenas 20 milhões de qubits. Na verdade, os pesquisadores mostraram que um dispositivo quântico rodando neste novo algoritmo levaria apenas 8 horas para quebrar criptografia RSA de 2.048 bits.

Seu método realiza exponenciação modular — um tipo de exponenciação realizada sobre um módulo — de maneira eficiente. Esta operação matemática é computacionalmente cara no algoritmo de Shor.

Os pesquisadores encontraram diferentes maneiras de otimizar esta operação, diminuindo drasticamente os recursos necessários para executar o algoritmo.

Embora um computador quântico com 20 milhões de qubits não seja viável no futuro próximo, especialistas em segurança precisam pensar em uma nova forma de criptografia que mesmo um poderoso computador quântico não consiga quebrar.