Computadores quânticos quebrarão a criptografia RSA em 2023?

Nos últimos dias de 2022, a comunidade de TI ficou bastante agitada devido a um estudo apresentado por um grupo de cientistas chineses. O documento afirma que, em breve, será possível quebrar o algoritmo de criptografia RSA com um comprimento de chave de 2.048 bits – que é fundamental para a operação de protocolos de internet – combinando habilmente a computação clássica e quântica. Bom, quão real é essa ameaça? Vamos descobrir.

Noções quânticas básicas

A capacidade teórica de um computador quântico de realizar fatoração ultrarrápida de números inteiros gigantes e, assim, combinar chaves para vários algoritmos criptográficos assimétricos – incluindo criptografia RSA – é conhecida há muito tempo. Já fizemos uma publicação na qual explicamos em detalhes o que é um computador quântico, como ele funciona e por que é tão difícil construir um. Até agora, todos os especialistas concordaram que um computador quântico grande o suficiente para quebrar o RSA provavelmente não seria construído antes de algumas dezenas de décadas. Para fatorar um inteiro de 2048 bits, que geralmente é usado como uma chave RSA, o algoritmo Shor precisa ser executado em um computador quântico com milhões de qubits (bits quânticos). Ou seja, não se trata de um futuro próximo, já que os melhores computadores quânticos hoje trabalham em 300-400 qubits — e isso depois de décadas de pesquisa.

Mas o problema futuro já foi pensado ativamente e os especialistas em segurança já estão pedindo a adoção da criptografia pós-quântica; ou seja, algoritmos resistentes a hackers com um computador quântico. A expectativa era existência de uma década ou mais para uma transição suave, então a notícia de que o RSA-2048 poderia cair já em 2023 veio como um raio inesperado.

Novidades da China

Pesquisadores chineses conseguiram fatorar uma chave de 48 bits em um computador quântico de 10 qubits. E eles calcularam que é possível dimensionar seu algoritmo para uso com chaves de 2.048 bits usando um computador quântico com apenas 372 qubits. Mas tal computador já existe hoje, na IBM por exemplo, então a necessidade de um dia substituir criptosistemas pela internet de repente deixou de ser algo tão distante que não foi realmente pensado seriamente ainda. Um avanço foi prometido pela combinação do algoritmo Schnorr (não confundir com o algoritmo Shor mencionado acima) com uma etapa adicional do algoritmo de otimização aproximada quântica (QAOA, na sigla em inglês).

O esquema proposto do algoritmo de fatoração híbrida

O algoritmo de Schnorr é usado para fatoração supostamente mais eficiente de números inteiros usando computação clássica. O grupo chinês se propõe a aplicar a otimização quântica na etapa mais intensiva computacionalmente de seu trabalho.

Questões em aberto

O algoritmo de Schnorr foi recebido pela comunidade matemática com certo ceticismo. A alegação do autor de que “isso destruirá o criptosistema RSA” na descrição do estudo foi submetida a escrutínio e não se sustentou. Por exemplo, o famoso criptógrafo Bruce Schneier disse que “funciona bem com módulos menores – aproximadamente da mesma ordem daqueles que o grupo chinês testou – mas falhou em tamanhos maiores”. E ninguém conseguiu provar que esse algoritmo é escalável na prática.

Aplicar a otimização quântica à parte “mais pesada” do algoritmo parece uma boa ideia, mas os especialistas em computação quântica duvidam que a otimização QAOA seja eficaz na solução desse problema computacional. É possível usar um computador quântico, mas dificilmente levará a economia de tempo esperada. Os próprios autores da obra mencionam cuidadosamente esse momento duvidoso bem no final de seu relato, na conclusão:

Deve-se ressaltar que a aceleração quântica do algoritmo não é clara devido à convergência ambígua do QAOA.
…
Além disso, o aumento de velocidade quântica é desconhecido, ainda é um longo caminho para quebrar a RSA quântica.

Portanto, parece que, mesmo que você implemente esse algoritmo híbrido em um sistema clássico + quântico, levará tanto tempo para adivinhar as chaves RSA quanto em um computador comum.

A cereja do bolo é que, além do número de qubits, existem outros parâmetros importantes de um computador quântico, como níveis de interferência e erros e o número de portas. A julgar pela combinação dos parâmetros necessários, mesmo os computadores mais promissores de 2023-2024 provavelmente não são adequados para executar o algoritmo chinês na escala necessária.

Lições práticas

Embora a revolução criptográfica esteja mais uma vez atrasada, o burburinho em torno deste estudo destaca dois desafios relacionados à segurança. Primeiro, ao escolher um algoritmo quântico-resistente entre inúmeras propostas para um “padrão pós-quântico”, novas abordagens algébricas – como o já mencionado algoritmo de Schnorr – devem ser estudadas escrupulosamente. Em segundo lugar, definitivamente precisamos aumentar a prioridade dos projetos de transição para a criptografia pós-quântica. Esse assunto pode parecer sem urgência, mas não será caso se torne realmente um problema.