Capítulo 1 — Cálculo I | Engenharia Segurança quântica e pós-quântica

Ensino gratuito e aberto para quem deseja proteger pessoas e tecnologias. Não é preciso criar uma conta para estudar ou consultar as respostas.

Capítulo 1 — Cálculo I

Mapa da aula

Aula 01 publicada. Mapa, exemplo, EX001.

flowchart TD
  N0["1.1 Por que um engenheiro precisa de taxas de cresci"]
  N1["1.2 Logaritmos e bits de segurança"]
  N2["1.4 Atividade prática — Laboratório G"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3
  N3 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX001"]

Desenho lógico

flowchart LR
  N0["1.1 Por que um engenheiro precisa de taxas de cresci"]
  N1["1.2 Logaritmos e bits de segurança"]
  N2["1.4 Atividade prática — Laboratório G"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3 --> Q["EX001"]

[1.1 Por que um engenheiro precisa de taxas de cresci]
    |
    v
[1.2 Logaritmos e bits de segurança]
    |
    v
[1.4 Atividade prática — Laboratório G]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX001]

Objetivos de aprendizagem

Você vai (1) comparar taxas de crescimento — polinomial, subexponencial e exponencial — e explicar por que elas decidem o que um computador quântico ameaça; (2) usar logaritmos para converter fatores de trabalho em "bits de segurança"; e (3) ler criticamente uma afirmação assintótica. Este capítulo abre a etapa de fundamentos e prepara a matemática discreta do Capítulo 2.

1.1 Por que um engenheiro precisa de taxas de crescimento

Toda afirmação de segurança deste livro é uma afirmação sobre a velocidade com que algum custo cresce. Encontrar por força bruta uma chave de k bits exige cerca de 2^k tentativas: o custo dobra a cada bit extra, o que é crescimento exponencial. O melhor algoritmo clássico de fatoração, o crivo geral de corpo de números (GNFS), roda em tempo subexponencial, aproximadamente exp(c·(ln N)^(1/3)·(ln ln N)^(2/3)) para um módulo N. O algoritmo de Shor fatora em tempo polinomial no número de bits — da ordem de n³ portas quânticas elementares para um módulo de n bits, ignorando o custo adicional da correção de erros (Shor 1997). A busca de Grover encontra uma chave entre 2^k candidatas em cerca de 2^(k/2) iterações sequenciais (Grover 1996). Toda a história da PQC decorre dessas quatro funções: Shor transforma um problema subexponencial num polinomial, o que é catastrófico para o RSA e as curvas elípticas; Grover apenas reduz o expoente pela metade, e é por isso que o AES-256 continua aceitável.

1.2 Logaritmos e bits de segurança

Aplicar log₂ a um fator de trabalho dá os "bits de segurança". Um custo de 2^128 operações é "segurança de 128 bits". Os logaritmos transformam produtos em somas, de modo que dobrar o trabalho acrescenta um bit, e multiplicá-lo por um milhão (≈2^20) acrescenta cerca de vinte bits. É por isso que os engenheiros dizem que uma aceleração de 2^20 trazida por hardware melhor "custa" vinte bits. A derivada ajuda a intuição: a curva de custo do GNFS, medida em bits, se achata à medida que as chaves crescem, de modo que cada bit extra de RSA compra menos segurança do que cada bit extra de AES — um dos motivos de as chaves RSA terem milhares de bits.

1.3 Limites e notação assintótica

As afirmações "O grande" descrevem o comportamento quando o tamanho da entrada tende ao infinito e escondem constantes. O n³ de Shor esconde uma constante grande e, mais importante, o custo adicional da correção quântica de erros, que pode multiplicar por mil ou mais o número de qubits físicos. Estimativas de recursos como a de Gidney (2025) — menos de um milhão de qubits ruidosos para o RSA-2048, sob pressupostos de hardware declarados — preenchem essas constantes. Um engenheiro nunca deve ler um limite assintótico como um tempo.

Dois algoritmos com o mesmo O grande podem diferir por fatores que decidem se um ataque leva uma hora ou uma década. A queda de vinte milhões de qubits ruidosos para menos de um milhão veio de constantes e códigos melhores, não de uma mudança no n³ de Shor. Quando um fornecedor cita um limite assintótico, o engenheiro pede os pressupostos de hardware por trás da constante.

1.4 Atividade prática — Laboratório G

# Lab G (ch 1): growth rates that decide what quantum computers threaten.
import math
print("Symmetric key search: classical 2^k trials vs Grover ~2^(k/2) sequential iterations")
for k in (128, 192, 256):
    print(f"  k={k}: classical 2^{k}, Grover ~2^{k//2}")
def gnfs_bits(n_bits):            # heuristic L_N[1/3, (64/9)^(1/3)] work, expressed in bits
    ln_n = n_bits * math.log(2)
    work = (64/9) ** (1/3) * ln_n ** (1/3) * math.log(ln_n) ** (2/3)
    return work / math.log(2)
print("Factoring an n-bit RSA modulus: classical GNFS (heuristic) vs Shor gate count ~n^3")
for n in (1024, 2048, 3072):
    print(f"  n={n}: GNFS ~2^{gnfs_bits(n):.0f} operations; Shor ~n^3 = 2^{math.log2(n**3):.0f} logical gates")

Saída esperada:

Symmetric key search: classical 2^k trials vs Grover ~2^(k/2) sequential iterations
  k=128: classical 2^128, Grover ~2^64
  k=192: classical 2^192, Grover ~2^96
  k=256: classical 2^256, Grover ~2^128
Factoring an n-bit RSA modulus: classical GNFS (heuristic) vs Shor gate count ~n^3
  n=1024: GNFS ~2^87 operations; Shor ~n^3 = 2^30 logical gates
  n=2048: GNFS ~2^117 operations; Shor ~n^3 = 2^33 logical gates
  n=3072: GNFS ~2^139 operations; Shor ~n^3 = 2^35 logical gates

A fórmula do GNFS é heurística (o seu termo o(1) é descartado), então os valores em bits se aproximam da força de 112 bits comumente citada para o RSA-2048, sem coincidir com ela. As "contagens de portas" de Shor são portas lógicas antes da correção de erros.

A comparação do laboratório existe para tornar as formas visíveis lado a lado: a força bruta dobra a cada bit, o GNFS se curva mais devagar e a contagem de portas lógicas de Shor cresce apenas polinomialmente. Executá-lo para módulos de 1024, 2048 e 3072 bits mostra por que chaves RSA mais longas compram pouco contra um adversário quântico. Os estudantes devem anotar na tabela o aviso de que a coluna de Shor omite o custo da correção de erros, de modo que nenhuma linha deve ser lida como tempo para quebrar.

1.5 Exemplo resolvido: a primeira pergunta da BPA

O conselho da BPA pergunta se deve dobrar o tamanho das chaves AES "por causa da computação quântica". Usando a seção 1.1: sob Grover, o AES-128 cai para cerca de 2^64 iterações sequenciais no modelo idealizado, mas Grover se paraleliza mal, então muitos documentos de orientação ainda aceitam o AES-128; migrar a cifragem em massa para o AES-256 é barato e encerra o debate. O item urgente não é o AES, e sim toda troca de chaves RSA e de curva elíptica, que Shor quebra por completo.

O memorando ao conselho da BPA separa, portanto, duas decisões. As chaves simétricas passam para o AES-256 durante a renovação normal, quase sem custo. A troca de chaves e as assinaturas precisam de uma migração planejada para o ML-KEM e o ML-DSA, porque nenhum tamanho de chave salva o RSA ou as curvas elípticas de Shor. Misturar as duas perguntas é a forma como conselhos gastam dinheiro na correção barata e adiam a importante.

1.6 Erros comuns e limites

Tratar Grover como fatal para a criptografia simétrica.
Ler O(n³) como "rápido" sem o custo da correção de erros.
Comparar bits entre curvas exponenciais e subexponenciais como se crescessem da mesma forma.

Cada erro leva a uma decisão errada. Tratar Grover como fatal manda orçamento para atualizações simétricas que já eram adequadas. Ler n³ como rápido ignora os qubits físicos necessários para cada qubit lógico. Comparar números de bits entre curvas de crescimento diferentes faz o RSA-3072 parecer mais forte contra ataques quânticos do que é. Os modelos deste capítulo comparam opções; não são cronogramas.

Exercícios

EX001 — Bits a partir do trabalho. Converta 10^30 e 2^100 × 10^6 operações em bits de segurança. Rubrica: 3 = os dois corretos, com o método.
EX002 — Explicar a assimetria. Em 150 palavras, explique ao conselho da BPA por que o RSA precisa ser substituído, mas o AES-256 não. Rubrica: 3 = argumento de taxa de crescimento correto e não técnico.

Síntese

As taxas de crescimento decidem tudo: Shor torna polinomiais a fatoração e os logaritmos discretos; Grover apenas tira a raiz quadrada da busca. Bits de segurança são logaritmos do trabalho, e os limites assintóticos precisam de estimativas de recursos antes de significarem tempo.

Continue estudando — capítulo 01 de 50

← Página do curso · Índice de capítulos do curso · Capítulo 02 →

Siga para a próxima lição escrita.