O Algoritmo de Grover vs a Sua Palavra-passe: O Que a Matemática Realmente Diz
O algoritmo de Grover é o ataque quântico que as pessoas realmente têm em mente quando se preocupam com palavras-passe “à prova de computação quântica”. Não quebra nada instantaneamente. Oferece uma aceleração quadrática para pesquisa não estruturada: um trabalho de força bruta que classicamente demora N tentativas necessita de cerca de √N iterações quânticas, o que efetivamente reduz para metade a robustez em bits de uma palavra-passe, em vez de a colapsar.
A aceleração quadrática, numa só linha
Se o espaço de chaves da sua palavra-passe tem 2^n possibilidades, um atacante clássico espera pesquisar na ordem de 2^n tentativas. O algoritmo de Grover reduz isso para cerca de 2^(n/2) iterações. Assim, uma pesquisa de 128 bits torna-se uma pesquisa de 64 bits — dramático em teoria, mas é uma raiz quadrada, não o colapso exponencial que o algoritmo de Shor inflige às chaves RSA e de curva elíptica. O algoritmo de Grover não fatoriza; pesquisa.
| Entropia efetiva | Trabalho clássico (~2^n) | Trabalho de Grover (~2^(n/2)) | Veredito prático |
|---|---|---|---|
| 40 bits | ~1,1 × 10^12 | ~1,0 × 10^6 | Fraca mesmo hoje |
| 64 bits | ~1,8 × 10^19 | ~4,3 × 10^9 | Vulnerável à computação quântica a longo prazo |
| 80 bits | ~1,2 × 10^24 | ~1,1 × 10^12 | No limite; acrescente comprimento |
| 128 bits | ~3,4 × 10^38 | ~1,8 × 10^19 | Segura; a √ ainda deixa 64 bits |
Porque é que o algoritmo de Grover é muito menos assustador na prática do que no papel
Três fatores atenuam gravemente o algoritmo de Grover na quebra de palavras-passe:
- É inerentemente sequencial. As iterações de Grover não podem ser paralelizadas da forma como os aglomerados de GPU clássicos dividem uma lista de palavras; executar M máquinas dá apenas uma aceleração de √M, pelo que não se pode simplesmente atirar hardware ao problema.
- A velocidade por operação é glacial. O hardware quântico atual executa portas a taxas muitas ordens de grandeza mais lentas do que uma GPU calcula hashes, e cada iteração de Grover necessita de executar o circuito de hash completo de forma coerente.
- A correção de erros é enorme. Uma execução de Grover criptograficamente útil necessita de milhões de qubits lógicos estáveis, sustentados ao longo de um número astronomicamente elevado de iterações — muito para além das máquinas atuais.
O que significa para a escolha de uma palavra-passe
A defesa é aborrecida e eficaz: acrescente comprimento. Cada caractere aleatório extra restaura aproximadamente os bits que o algoritmo de Grover retirou. Uma palavra-passe verdadeiramente aleatória de 16 caracteres a partir de um conjunto completo de chaves situa-se bem acima da linha dos 128 bits após a penalização de raiz quadrada. É exatamente por isto que o nosso verificador de palavras-passe modela o algoritmo de Grover como √(tentativas), em vez de fingir que os computadores quânticos são mágicos.
Para a outra metade da história quântica — a quebra de chave pública que é exponencial — leia Criptografia Pós-Quântica, Explicada. E para ver o comprimento em ação, consulte Quanto Tempo Demora a Quebrar uma Palavra-passe de 16 Caracteres?.