Algoritmos de Shor e Grover explicados

Os computadores quânticos não apenas executam algoritmos clássicos mais rapidamente — eles exploram a superposição e a interferência quânticas para resolver certos problemas de forma exponencialmente mais rápida. Dois algoritmos ameaçam a maior parte da criptografia atualmente implantada: o de Shor (quebra RSA/ECC) e o de Grover (enfraquece a criptografia simétrica e as funções de resumo).

O algoritmo de Shor (1994) resolve a fatoração de inteiros e o logaritmo discreto em tempo polinomial em um computador quântico. Isso quebra diretamente RSA (baseado em fatoração), Diffie-Hellman (logaritmo discreto módulo p) e ECDH/ECDSA (logaritmo discreto de curvas elípticas).

O ingrediente fundamental do algoritmo de Shor é a Transformada de Fourier quântica (QFT) — uma versão quântica exponencialmente mais rápida da DFT. Para encontrar períodos, a QFT identifica o período de f(x) = a^x mod N, a partir do qual os fatores de N são derivados usando GCD.

Para fatorar N: (1) escolha um a aleatório tal que a < N e verifique gcd(a,N)=1. (2) encontre o período r de f(x)=a^x mod N usando a QFT. (3) Com alta probabilidade, gcd(a^{r/2}±1, N) produz um fator não trivial. A etapa clássica é O(log N); a busca quântica do período é O((log N)^3) — polinomial.

Melhor fatoração clássica: GNFS — O(exp((64/9 log N)^{1/3} log log N)^{2/3})), subexponencial. O algoritmo de Shor em um computador quântico tolerante a falhas: O((log N)^3), polinomial. RSA-2048 exige aproximadamente 4000 qubits lógicos e cerca de 10^9 operações de portas. Os computadores NISQ atuais têm cerca de 1000 qubits ruidosos — ainda não representam uma ameaça.

O algoritmo de Grover (1996) oferece uma aceleração quadrática para buscas não estruturadas. Para um espaço de busca com N itens, os algoritmos clássicos precisam de O(N) consultas; o algoritmo de Grover precisa de O(√N). Aplicado à criptografia, ele quebra chaves simétricas de n bits em O(2^{n/2}), em vez de O(2^n).

AES-128: segurança clássica de 2^128; Grover reduz isso para 2^64 — inseguro contra um computador quântico de grande porte. AES-256: 2^256 → 2^128 — continua seguro. Solução: dobrar os tamanhos das chaves simétricas. Resistência a colisões do SHA-256: 2^128 → 2^85 (aniversário+Grover). Pré-imagem do SHA-256: 2^256 → 2^128 — OK.

Os computadores quânticos NISQ atuais (IBM Heron: 133 qubits; Google Sycamore: 70 qubits) são pequenos demais e ruidosos demais para cálculos relevantes à criptografia. As estimativas para quebrar RSA-2048 variam de 2035 a 2050 com computadores quânticos tolerantes a falhas. Os ataques de coletar agora e decifrar depois já são uma ameaça atual.

Adversários coletam tráfego criptografado hoje e o armazenam. Quando um computador quântico estiver disponível, eles o decifrarão retroativamente. Isso torna segredos de longa duração, como dados governamentais classificados e prontuários médicos, vulneráveis já hoje. A migração para PQC deve começar agora para esse tipo de dado.

Problemas de reticulados (LWE, SIS), problemas baseados em códigos (McEliece), assinaturas baseadas em funções de resumo (SPHINCS+), problemas multivariados — não há nenhum algoritmo quântico de tempo polinomial conhecido. Eles são a base dos padrões pós-quânticos do NIST.

Os padrões de PQC do NIST (ML-KEM, ML-DSA, SLH-DSA) foram finalizados em 2024. As organizações devem: fazer um inventário do uso atual de criptografia, identificar dados de longa duração e priorizar a implantação de PQC para a troca de chaves, que é a mais urgente devido aos ataques de coletar agora e decifrar depois. As assinaturas têm mais tempo.

Qual é o impacto do algoritmo de Grover sobre o AES-128?

O algoritmo de Shor, de tempo polinomial, quebra RSA, DH e ECC. O algoritmo de Grover, com aceleração quadrática, reduz pela metade a força das chaves simétricas. Solução: migrar para os padrões de PQC do NIST, baseados em reticulados. A seguir: o KEM CRYSTALS-Kyber.