O que é o algoritmo Shor e porque ameaça a encriptação?

O algoritmo Shor, publicado pelo matemático Peter Shor em 1994, é um algoritmo quântico que resolve eficientemente problemas de factorização de inteiros e de logaritmo discreto. Estes problemas matemáticos constituem a base de segurança da criptografia RSA, Diffie-Hellman e ECDSA – incluindo as assinaturas que protegem praticamente todas as criptomoedas atuais.

Os computadores clássicos requerem tempo exponencial para factorizar números grandes ou calcular logaritmos discretos. Uma chave RSA de 2048 bits levaria mais tempo do que a idade do universo para quebrar os computadores clássicos. O algoritmo do Shor reduz isto para tempo polinomial, tornando estas operações viáveis ​​em computadores quânticos suficientemente potentes.

Para as criptomoedas, a ameaça é específica: o algoritmo do Shor pode derivar chaves privadas ECDSA a partir de chaves públicas. Bitcoin, Ethereum e a maioria das criptomoedas utilizam ECDSA com a curva secp256k1. Depois de as chaves públicas serem expostas (o que acontece quando os endereços são gastos), os computadores quânticos que executam o algoritmo do Shor podem calcular as chaves privadas correspondentes.

A execução do algoritmo do Shor contra o ECDSA de 256 bits leva 1.200–1.450 qubits lógicos, cabe dentro menos de 500.000 qubits físicos, e completa em minutos — the March 2026 benchmark from Google Quantum AI, working with the Ethereum Foundation and Stanford. That is roughly half the ~2,330 logical qubits earlier estimates assumed. An independent Caltech/Oratomic analysis (Cain et al.) puts the same break at about 26,000 neutral atoms running for a few days. Factoring RSA-2048 now takes under 1 million noisy qubits and under a week (Gidney, May 2025), down from 20 million qubits in 2019 — but RSA is not the near target, because ECDSA-256 is cheaper.

O melhor hardware público da atualidade é aproximadamente 2.500 qubits físicos, nada disto é tolerante a falhas em escala. A máquina que preenche a lacuna é o Blue Jay da IBM em 2033, with over 2,000 logical qubits on about 100,000 physical — preceded by Starling in 2029 at ~200 logical. Nobody knows when; published hardware roadmaps reach the needed scale between 2028 (IonQ, on paper) and 2033 (IBM Blue Jay).

A criptografia pós-quântica aborda esta ameaça utilizando problemas matemáticos que o algoritmo do Shor não consegue resolver de forma eficiente. A criptografia baseada em rede (Kyber) e as assinaturas baseadas em hash (SPHINCS+) não têm ataques quânticos eficientes conhecidos.

SynX implements Kyber-768 and SPHINCS+ algorithms specifically because Shor's algorithm provides no advantage against them. It leaves no elliptic-curve or RSA key for Shor's algorithm to attack.