Algoritmo de Shor
O que é Algoritmo de Shor?
Algoritmo de ShorAlgoritmo quântico que fatora inteiros grandes e calcula logaritmos discretos em tempo polinomial, quebrando RSA, Diffie-Hellman e a criptografia de curvas elípticas num computador quântico suficientemente grande.
O Algoritmo de Shor, publicado por Peter Shor em 1994, resolve a fatoração de inteiros e o logaritmo discreto em tempo polinomial num computador quântico tolerante a falhas. Estes dois problemas sustentam praticamente todos os sistemas de chave pública em produção: RSA, Diffie-Hellman, DSA e ECDSA. Nenhum hardware quântico atual consegue fatorar tamanhos de chave criptograficamente relevantes, mas estimativas credíveis indicam que alguns milhares de qubits lógicos estáveis bastariam para quebrar RSA-2048. Esta perspetiva é a razão de ser do processo de padronização PQC do NIST e da preocupação com ataques "colher agora, decifrar depois".
● Exemplos
- 01
Usado como base teórica para estimar prazos da ameaça quântica contra RSA-2048 e ECC P-256.
- 02
Motiva a migração das primitivas assimétricas clássicas para KEMs baseados em reticulados, como o CRYSTALS-Kyber.
● Perguntas frequentes
O que é Algoritmo de Shor?
Algoritmo quântico que fatora inteiros grandes e calcula logaritmos discretos em tempo polinomial, quebrando RSA, Diffie-Hellman e a criptografia de curvas elípticas num computador quântico suficientemente grande. Pertence à categoria Criptografia da cibersegurança.
O que significa Algoritmo de Shor?
Algoritmo quântico que fatora inteiros grandes e calcula logaritmos discretos em tempo polinomial, quebrando RSA, Diffie-Hellman e a criptografia de curvas elípticas num computador quântico suficientemente grande.
Como funciona Algoritmo de Shor?
O Algoritmo de Shor, publicado por Peter Shor em 1994, resolve a fatoração de inteiros e o logaritmo discreto em tempo polinomial num computador quântico tolerante a falhas. Estes dois problemas sustentam praticamente todos os sistemas de chave pública em produção: RSA, Diffie-Hellman, DSA e ECDSA. Nenhum hardware quântico atual consegue fatorar tamanhos de chave criptograficamente relevantes, mas estimativas credíveis indicam que alguns milhares de qubits lógicos estáveis bastariam para quebrar RSA-2048. Esta perspetiva é a razão de ser do processo de padronização PQC do NIST e da preocupação com ataques "colher agora, decifrar depois".
Como se defender contra Algoritmo de Shor?
As defesas contra Algoritmo de Shor costumam combinar controles técnicos e práticas operacionais, conforme detalhado na definição acima.
Quais são outros nomes para Algoritmo de Shor?
Nomes alternativos comuns: Algoritmo de fatoração de Shor.
● Termos relacionados
- cryptography№ 846
Criptografia pós-quântica
Algoritmos criptográficos clássicos concebidos para se manterem seguros contra ataques de computadores clássicos e computadores quânticos de grande escala.
- cryptography№ 890
Criptografia quântica
Criptografia que utiliza propriedades quânticas, tipicamente de fotões, para obter garantias de segurança impossíveis apenas com comunicação clássica.
- cryptography№ 951
Algoritmo RSA
Algoritmo de chave pública de Rivest, Shamir e Adleman (1977) cuja segurança assenta na dificuldade de factorizar o produto de dois números primos grandes.
- cryptography№ 454
Algoritmo de Grover
Algoritmo quântico de pesquisa que encontra um elemento marcado numa base não estruturada de N entradas em cerca de sqrt(N) passos, oferecendo um ganho quadrático contra cifras simétricas e funções de hash.
- cryptography№ 732
Padronização PQC do NIST
Processo plurianual do NIST que seleciona e padroniza algoritmos criptográficos pós-quânticos; as três primeiras normas, FIPS 203, 204 e 205, foram publicadas em agosto de 2024.
- cryptography№ 253
CRYSTALS-Kyber
Mecanismo de encapsulação de chave baseado em reticulados, padronizado pelo NIST como FIPS 203 (ML-KEM) em agosto de 2024 e concebido para substituir as trocas de chave RSA e Diffie-Hellman num mundo pós-quântico.