Estou a começar uma série de publicações diárias fáceis de ler sobre segurança pós-quântica. Mas não tenho ideia de quantos dias vai durar :). Então, vamos ver. DIA 1: O Algoritmo de Shor e o Apocalipse Quântico(?) A maior parte da nossa pilha de segurança—RSA, ECC, Diffie-Hellman—baseia-se numa única suposição: A fatoração de inteiros e os logs discretos são "difíceis." No silício clássico, são. Para quebrar o RSA-2048, 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 podem ser resolvidos de forma eficiente num computador quântico. O Algoritmo de Shor não apenas força as chaves; utiliza a Transformada de Fourier Quântica (QFT [Não teoria de campos quânticos lol]) para encontrar o período de uma função f(x) = a^x mod N. Uma vez que tem o período, tem os fatores. E uma vez que 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 de tempo sub-exponencial para tempo polinomial O((log N)^3). Não estamos a falar de um aumento de 10x; estamos a falar de passar de trilhões de anos para algumas horas num CRQC. Semelhante ao RSA, o ECC (criptografia de curva elíptica) também NÃO é seguro. Devido à sua estrutura de grupo algébrico eficiente, quebrar uma chave ECC de 256 bits na verdade requer menos qubits lógicos do que o RSA-2048. --- Obrigado pela leitura! Amanhã, vamos discutir por que a ameaça HNDL (colher-agora-decriptar-depois) significa que a transição pós-quântica tem que acontecer agora. (Visual: Peter Shor)