Capítulo 2 — Matemática discreta | 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.

Mapa da aula

Aula 02 publicada. Mapa, exemplo, EX003.

flowchart TD
  N0["2.1 Aritmética modular"]
  N1["2.2 Anéis de polinômios"]
  N2["2.3 Atividade prática — Laboratório R"]
  N3["2.4 Funções de hash"]
  N4["Síntese"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX003"]

Desenho lógico

flowchart LR
  N0["2.1 Aritmética modular"]
  N1["2.2 Anéis de polinômios"]
  N2["2.3 Atividade prática — Laboratório R"]
  N3["2.4 Funções de hash"]
  N4["Síntese"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX003"]

[2.1 Aritmética modular]
    |
    v
[2.2 Anéis de polinômios]
    |
    v
[2.3 Atividade prática — Laboratório R]
    |
    v
[2.4 Funções de hash]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX003]

Objetivos de aprendizagem

Você vai (1) calcular em aritmética modular e em anéis de polinômios; (2) explicar o anel Z_q[x]/(x^n+1) usado pelo ML-KEM e pelo ML-DSA; (3) enunciar as propriedades de segurança de uma função de hash; e (4) ligar a estrutura de grupo ao motivo pelo qual o algoritmo de Shor funciona. O capítulo parte do Capítulo 1 e prepara a probabilidade (Capítulo 7) e os métodos de reticulados do Capítulo 24.

2.1 Aritmética modular

A aritmética módulo q mantém os números em {0, …, q−1}. O RSA usa um módulo composto; a criptografia de curvas elípticas usa grupos de pontos sobre um corpo primo. Ambos dependem da dificuldade de encontrar um período oculto — a ordem de um elemento ou um logaritmo discreto. A percepção de Shor é que um computador quântico consegue encontrar períodos com eficiência usando a transformada quântica de Fourier; é por isso que todos os esquemas cuja segurança se reduz a um período oculto num grupo abeliano caem juntos.

Essa fraqueza comum explica por que a migração não pode ser feita um algoritmo de cada vez, trocando o RSA por curvas elípticas: os dois caem diante da mesma ideia. Os esquemas pós-quânticos são escolhidos justamente porque os seus problemas difíceis, como equações lineares com ruído ou a inversão de hashes, não têm nenhum período oculto conhecido que um computador quântico possa encontrar.

2.2 Anéis de polinômios

O ML-KEM (FIPS 203) calcula com polinômios de grau menor que 256 cujos coeficientes são inteiros módulo q = 3329, reduzidos módulo x^256 + 1. Nesse anel, multiplicar por x desloca os coeficientes uma posição para cima, e o coeficiente que sai pelo topo volta para a base com o sinal trocado, porque x^n = −1. Vetores e matrizes desses polinômios formam um módulo, daí "reticulado modular" (module-lattice). A estrutura dá chaves compactas e multiplicação rápida (pela transformada de teoria dos números, NTT), enquanto a dificuldade vem do acréscimo de um pequeno ruído — o assunto do Capítulo 24.

2.3 Atividade prática — Laboratório R

# Lab R (ch 2): multiplication in R_q = Z_q[x]/(x^n + 1), the ring behind ML-KEM (there n=256, q=3329).
q, n = 17, 4
def mul(a, b):
    c = [0] * n
    for i in range(n):
        for j in range(n):
            k = i + j
            if k < n:
                c[k] = (c[k] + a[i] * b[j]) % q
            else:                       # x^n = -1, so wrap around with a sign flip
                c[k - n] = (c[k - n] - a[i] * b[j]) % q
    return c
a = [1, 2, 0, 3]      # 1 + 2x + 3x^3
b = [0, 1, 0, 0]      # x
print("a*x  =", mul(a, b), " (coefficients shift; x^3 * x = x^4 = -1 -> 17-3 = 14)")
print("a*a  =", mul(a, a))

Saída esperada:

a*x  = [14, 1, 2, 0]  (coefficients shift; x^3 * x = x^4 = -1 -> 17-3 = 14)
a*a  = [6, 4, 12, 6]

Verificação à mão: (1 + 2x + 3x³)·x = x + 2x² + 3x⁴ = x + 2x² − 3 ≡ 14 + x + 2x² (mod 17).

A verificação à mão mostra a regra de volta em ação: o termo x⁴ ultrapassa o limite de grau para n igual a quatro, então vira menos três, e menos três módulo dezessete é quatorze. O ML-KEM usa a mesma regra com n igual a 256 e q igual a 3329. Estudantes que erram o sinal calculam um polinômio diferente, e numa implementação real esse erro quebraria todo desencapsulamento, e é por isso que os testes de resposta conhecida (KAT) o detectam de imediato.

2.4 Funções de hash

Um hash criptográfico mapeia qualquer entrada num resumo de tamanho fixo. As propriedades exigidas são resistência à pré-imagem (dado um resumo, não encontrar nenhuma entrada), resistência à segunda pré-imagem e resistência a colisões. As assinaturas baseadas em hash (SLH-DSA na FIPS 205; LMS e XMSS na SP 800-208) precisam apenas dessas propriedades, e é por isso que são as assinaturas pós-quânticas mais conservadoras: não se sabe de computadores quânticos que façam muito melhor do que acelerações no estilo de Grover contra boas funções de hash.

Grover consegue buscar pré-imagens mais depressa, tirando aproximadamente a raiz quadrada do trabalho, então um hash de 256 bits ainda oferece cerca de 128 bits contra a busca de pré-imagem. A busca de colisões com algoritmos quânticos ganha, na prática, menos do que os limites idealizados sugerem. O preço das assinaturas baseadas em hash é tamanho e velocidade, não pressupostos de segurança.

2.5 Exemplo resolvido

Um desenvolvedor da BPA pergunta por que a biblioteca pós-quântica "multiplica polinômios" quando o RSA "só exponencia". A resposta: a segurança do RSA está no grupo multiplicativo módulo N, onde Shor encontra períodos. A do ML-KEM está na álgebra linear com ruído sobre um anel de polinômios, onde não se conhece atalho de busca de períodos; o anel serve à eficiência, o ruído serve à segurança.

A pergunta seguinte do desenvolvedor costuma ser sobre custo: a multiplicação de polinômios com a transformada de teoria dos números é rápida, e a geração de chaves do ML-KEM costuma ser mais rápida do que a do RSA. O que muda para o sistema é o tamanho: chaves e textos cifrados são maiores que os de curvas elípticas. Isso desloca o problema de engenharia do tempo de CPU para os bytes na rede.

2.6 Erros comuns e limites

Esquecer a troca de sinal ao reduzir por x^n + 1.
Achar que a estrutura de anel sozinha dá segurança (sem ruído, o sistema linear é fácil).
Confundir resistência a colisões com resistência à pré-imagem.

Uma troca de sinal esquecida produz saídas que parecem plausíveis, mas falham nos testes de interoperabilidade contra a norma. Supor que o anel sozinho dá segurança ignora o papel do ruído: sem erros pequenos, a eliminação gaussiana recupera o segredo. Confundir resistência a colisões e à pré-imagem leva a afirmações erradas sobre parâmetros, por exemplo, reduzir à metade o tamanho de um hash para um uso que só precisa de resistência à pré-imagem.

Exercícios

EX003 — Multiplicação no anel. Calcule à mão (2 + x)(3 + x³) em Z_17[x]/(x⁴ + 1) e confira com o Laboratório R. Rubrica: 3 = correto, com os passos de redução.
EX004 — Propriedades do hash. Para o SLH-DSA, um manifesto de integridade de arquivos e o armazenamento de senhas, diga qual propriedade do hash mais importa. Rubrica: 3 = correto e justificado.

Síntese

A criptografia de chave pública tradicional esconde um período que o algoritmo de Shor encontra; os esquemas de reticulados calculam num anel de polinômios e escondem os segredos sob ruído; os esquemas baseados em hash dependem apenas das propriedades do hash.