Capítulo 1 — Raciocínio matemático | Graduação 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 — Raciocínio matemático

Mapa da aula

Aula 01 publicada. Mapa, exemplo, EX001.

flowchart TD
  N0["1.1 Por que estudantes de segurança precisam de demo"]
  N1["1.2 Taxas de crescimento"]
  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 estudantes de segurança precisam de demo"]
  N1["1.2 Taxas de crescimento"]
  N2["1.4 Atividade prática — Laboratório G"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3 --> Q["EX001"]

[1.1 Por que estudantes de segurança precisam de demo]
    |
    v
[1.2 Taxas de crescimento]
    |
    v
[1.4 Atividade prática — Laboratório G]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX001]

Objetivos de aprendizagem

Você vai (1) ler e escrever uma demonstração curta por argumento direto, por contradição e por indução; (2) comparar taxas de crescimento usando logaritmos e a notação O grande; (3) explicar por que "com que rapidez cresce o custo do ataque?" é a pergunta central da criptografia; e (4) distinguir uma afirmação matemática de uma estimativa empírica. O capítulo prepara as estruturas discretas (Capítulo 6) e a probabilidade (Capítulo 12).

1.1 Por que estudantes de segurança precisam de demonstrações

Uma afirmação de segurança é um enunciado sobre todo atacante dentro de um modelo, e não sobre os atacantes que por acaso testamos. Testar uma fechadura com dez gazuas mostra que ela resistiu a dez gazuas; não mostra que resiste à décima primeira. A matemática é a única ferramenta que nos permite fazer afirmações do tipo "para todo", e ela o faz enunciando as hipóteses com precisão. Quando uma norma diz que um esquema é seguro "se o problema Module-LWE for difícil", essa frase é um teorema condicional: a conclusão é tão forte quanto a hipótese, e a hipótese se apoia em décadas de ataques fracassados, e não numa demonstração. Aprender a separar a parte demonstrada da parte suposta é o hábito matemático mais útil deste livro.

Três formas de demonstração se repetem. Uma demonstração direta encadeia afirmações verdadeiras até a conclusão. Uma demonstração por contradição supõe o contrário e deriva algo impossível; a demonstração de Euclides de que existem infinitos primos é o exemplo clássico e sustenta por que os módulos RSA podem ser escolhidos livremente. A indução demonstra um caso base e um passo de n para n+1; é assim que raciocinamos sobre laços, cadeias de hash e os contadores dentro das assinaturas com estado.

1.2 Taxas de crescimento

Os criptógrafos medem a segurança em bits: um problema de "128 bits" exige cerca de 2^128 operações básicas. Os logaritmos convertem entre escalas: log₂(10^30) ≈ 100, então 10^30 operações são cerca de 2^100. A notação O grande mantém apenas o termo dominante: um algoritmo que executa 3n³ + 50n passos é O(n³). A ameaça quântica é, no fundo, uma mudança na taxa de crescimento. Classicamente, o melhor algoritmo de fatoração conhecido cresce de forma subexponencial no comprimento em bits do número; o algoritmo de Shor (Shor, 1997) cresce de forma polinomial, aproximadamente como n³ operações lógicas. Para a busca de chaves por força bruta, o algoritmo de Grover (Grover, 1996) apenas reduz 2^k tentativas a cerca de 2^(k/2) iterações sequenciais. Uma das mudanças é um colapso; a outra é uma raiz quadrada que chaves mais longas absorvem.

1.3 Exemplo resolvido

O gerente de TI da HCU lê uma manchete dizendo que os computadores quânticos vão "quebrar toda a criptografia". Usando as taxas de crescimento, classificamos a criptografia da HCU. O RSA-2048 e as chaves de curvas elípticas protegem os logins e a troca de chaves da VPN: existe um ataque de tempo polinomial num grande computador quântico tolerante a falhas, então eles precisam ser substituídos. O AES-256 cifra o banco de dados: o Grover deixa cerca de 2^128 de trabalho sequencial, ainda muito além do alcance, então ele fica. A manchete erra no seu alcance, e a correção vem de uma comparação de crescimento, e não de uma opinião.

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

Leia a saída como uma tabela de taxas de crescimento, e não como tempos de execução previstos: os números ignoram constantes, correção de erros e velocidade do hardware, que o Capítulo 19 trata como hipóteses explícitas.

Dois contrastes se destacam. Para as chaves simétricas, a busca de Grover reduz o expoente à metade, então uma chave de 256 bits ainda deixa um problema muito grande. Para o RSA, a distância é bem maior: o custo clássico cresce mais rápido que qualquer polinômio no tamanho da chave, enquanto o custo de Shor cresce apenas como o seu cubo. Dobrar a chave de 1024 para 2048 bits acrescenta muito trabalho clássico, mas apenas alguns bits de trabalho quântico. Essa diferença é a razão pela qual o RSA precisa ser substituído, e não alongado.

1.5 Erros comuns e limites

Tratar "seguro se o problema X for difícil" como uma demonstração incondicional.
Comparar contagens de operações entre máquinas como se uma porta quântica e uma instrução clássica custassem o mesmo.
Ler as estimativas heurísticas de fatoração como exatas; elas são guias de ordem de grandeza.

Cada erro vem de esquecer o que o cálculo deixa de fora. As demonstrações de segurança são condicionais, então a condição precisa ser declarada ao lado do resultado. As contagens de operações comparam crescimento, e não tempo de relógio, já que uma única operação quântica com correção de erros pode levar muito mais tempo que uma clássica. As estimativas heurísticas são úteis para decidir quais algoritmos estão em perigo, não para prever uma data. Um estudante cuidadoso escreve a hipótese ao lado de cada número.

Exercícios

EX001 — Bits de trabalho. Expresse 10^24 operações e 10^24 × 2^20 operações em bits de trabalho. Rubrica: 3 = os dois corretos, com o logaritmo mostrado.
EX002 — Forma da demonstração. Demonstre por indução que uma cadeia de hash de comprimento n, construída como h₁ = H(s), h_{k+1} = H(h_k), exige exatamente n avaliações de hash. Rubrica: 3 = caso base, passo e conclusão enunciados.

Síntese

Os argumentos de segurança combinam implicações demonstradas com problemas difíceis supostos. A ameaça quântica é uma mudança na taxa de crescimento: o Shor, de tempo polinomial, derruba a fatoração e os logaritmos discretos, enquanto o Grover apenas reduz à metade o expoente da busca de chaves.

Continue estudando — capítulo 01 de 40

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

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