Estou começando uma série de posts diários de fácil leitura sobre segurança pós-quântica. Mas não faço ideia de quantos dias isso vai durar :). Então, vamos ver. DIA 1: Algoritmo de Shor e Apocalipse Quântico(?) A maior parte da nossa pilha de segurança — RSA, ECC, Diffie-Hellman — depende de uma única suposição: a fatoração de inteiros e os logs discretos são "difíceis". No silício clássico, eles são. Para decifrar o RSA-2048, você precisaria simplesmente de mais tempo do que a idade do universo. Mas isso não é uma lei física. É uma limitação da computação clássica. Em 1994, Peter Shor mostrou que eles podem ser resolvidos de forma eficiente em um computador quântico. O Algoritmo de Shor não usa apenas chaves de força bruta; ela usa a Transformada Quântica de Fourier (QFT [Não teoria quântica de campos, rs]) para encontrar o período de uma função f(x) = a^x mod N. Depois que você tem o período, você tem os fatores. E uma vez que você tem os fatores, a chave privada está morta. Porque a chave privada pode ser reconstruída a partir da chave pública. A mudança de complexidade é o verdadeiro "apocalipse". Passamos do tempo subexponencial para o tempo polinomial O((log N)^3). Não estamos falando de um aumento de velocidade 10x; estamos falando de passar de trilhões de anos para algumas horas em um CRQC. Semelhante à RSA, a ECC (criptografia de curvas elípticas) também NÃO é segura. Devido à sua eficiente estrutura de grupo algébrica, quebrar uma chave ECC de 256 bits na verdade requer menos qubits lógicos do que o RSA-2048. --- Obrigado por ler! Amanhã, discutiremos por que a ameaça HNDL (colheita agora-decriptação-depois) significa que a transição pós-quântica precisa acontecer agora. (Visual: Peter Shor)