Computadores quânticos estão prontos para enterrar a criptografia RSA, dizem cientistas chineses

No final de dezembro, apareceu o trabalho de um grupo de cientistas chineses, que demonstrou a possibilidade de quebrar chaves RSA suficientemente longas usando computadores quânticos modernos. O artigo fala sobre a primeira quebra de uma chave de 48 bits por um sistema de apenas 10 qubits supercondutores. Para quebrar uma chave RSA-2048, não são necessários mais de 400 qubits, o que já está na faixa dos recursos modernos. RSA é tudo?

Fonte da imagem: Pixabay

Como se sabe, com a ajuda de um computador quântico e do algoritmo quântico de Shor, pode-se facilmente e simplesmente decompor (fatorar) grandes números em fatores primos e, assim, descriptografar uma chave ou mensagem muito mais rápido do que em um computador clássico. O único problema com a execução do algoritmo de Shor é que são necessários sistemas quânticos de centenas de milhares, senão milhões, de qubits para fatorar chaves longas criptograficamente significativas.

Desde que o algoritmo de Peter Shor se tornou conhecido, os cientistas têm tentado ampliá-lo para que o hacking RSA não seja tão intensivo em recursos para sistemas quânticos. Uma das ideias sobre como fazer isso foi apresentada pelo físico russo Alexei Kitaev. Em 2016, um grupo de físicos do Instituto de Tecnologia de Massachusetts e da Universidade de Innsbruck criou um computador quântico que confirmou o dimensionamento ao executar o algoritmo de Shor. Mas isso não foi suficiente para um avanço sério.

Os cientistas chineses tinham um sistema quântico bastante modesto e queriam mais. Eles seguiram o conselho de outro criptógrafo, Klaus-Peter Schnorr, que propôs uma técnica na primavera passada que acelera significativamente a fatoração.

O trabalho de Schnorr foi criticado por especialistas como incapaz de resistir ao aumento de escala para quebrar chaves longas, cuja “morte” poderia realmente encerrar a história com a criptografia RSA. Mas os pesquisadores chineses afirmam que encontraram uma maneira de contornar essa limitação e a provaram na prática, quebrando uma chave de 48 bits com um sistema quântico de 10 qubits, e também afirmam que o método funciona para quebrar chaves de comprimento criptograficamente significativo.

Na verdade, os chineses combinaram métodos clássicos de fatoração de redução de rede com um algoritmo de otimização quântica aproximada (QAOA). De acordo com seus cálculos, seriam necessários apenas 372 qubits para quebrar uma chave RSA-2048. Um sistema semelhante, por exemplo, estará em breve na IBM. O processador IBM Osprey fornece acesso a 433 qubits. Se há algo por trás das palavras dos cientistas chineses, não faltam mais do que alguns anos para que o RSA-2048 seja hackeado por computadores quânticos.