Capítulo 6 — Estruturas discretas | 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.

Mapa da aula

Aula 06 publicada. Mapa, exemplo, EX011.

flowchart TD
  N0["6.1 Aritmética modular e grupos"]
  N1["6.2 Anéis de polinômios"]
  N2["6.3 Atividade prática — Laboratório R"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3
  N3 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX011"]

Desenho lógico

flowchart LR
  N0["6.1 Aritmética modular e grupos"]
  N1["6.2 Anéis de polinômios"]
  N2["6.3 Atividade prática — Laboratório R"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3 --> Q["EX011"]

[6.1 Aritmética modular e grupos]
    |
    v
[6.2 Anéis de polinômios]
    |
    v
[6.3 Atividade prática — Laboratório R]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX011]

Objetivos de aprendizagem

Você vai (1) calcular com aritmética modular; (2) explicar os grupos e por que os períodos ocultos importam; (3) multiplicar polinômios no anel Z_q[x]/(x^n+1); e (4) ligar essas estruturas ao RSA, às curvas elípticas e ao ML-KEM.

6.1 Aritmética modular e grupos

Trabalhar módulo q mantém os números em {0, …, q−1}: 15 mod 7 = 1. Um grupo é um conjunto com uma operação associativa, que tem elemento neutro e inversos. Os números não nulos módulo um primo p formam um grupo sob a multiplicação; os pontos de uma curva elíptica formam um grupo sob a adição de pontos. Repetir a operação a partir de um elemento inicial g acaba gerando um ciclo: g, g², g³, … volta a 1 depois de r passos, em que r é a ordem de g. Encontrar r — um período oculto — é difícil classicamente para grupos grandes, e o RSA, o Diffie–Hellman e a criptografia de curvas elípticas se apoiam todos em problemas equivalentes ou redutíveis a encontrar esses períodos ou logaritmos discretos. O algoritmo de Shor encontra períodos de forma eficiente num computador quântico, e é por isso que todos eles caem juntos.

6.2 Anéis de polinômios

Um anel de polinômios Z_q[x]/(x^n+1) contém os polinômios de grau menor que n com coeficientes módulo q. Para multiplicar, multiplique normalmente e depois substitua x^n por −1. O ML-KEM (FIPS 203) usa n = 256 e q = 3329; o ML-DSA (FIPS 204) usa n = 256 e q = 8380417. Vetores desses polinômios formam módulos, daí "reticulado de módulos". O anel é escolhido pela compacidade e pela multiplicação rápida; a segurança vem do acréscimo de um pequeno ruído aleatório, tema do Capítulo 23. Não se conhece nenhum ataque quântico eficiente por busca de períodos contra esses problemas com ruído.

6.3 Atividade prática — Laboratório R

# Lab R (ch 6): 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]

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

O laboratório multiplica dois polinômios pequenos num anel com parâmetros de brinquedo e imprime o resultado. Fazer um produto à mão, como mostrado, é a melhor forma de ver onde acontece a troca de sinal. Os parâmetros reais são muito maiores, mas a regra é a mesma, e as bibliotecas que você vai usar a aplicam com algoritmos muito mais rápidos. O anel de brinquedo não é seguro; ele existe apenas para tornar a aritmética visível.

6.4 Exemplo resolvido

Um desenvolvedor da HCU pergunta por que a sua biblioteca pós-quântica "multiplica polinômios" quando o RSA "eleva números a potências". O RSA trabalha no grupo multiplicativo módulo N, onde existe um período oculto e o Shor consegue encontrá-lo. O ML-KEM trabalha com álgebra linear com ruído sobre anéis de polinômios, onde não se conhece nenhuma estrutura de períodos assim que ajude. A aritmética parece diferente porque o problema difícil é diferente.

Vale a pena responder à pergunta do desenvolvedor antes de qualquer trabalho de migração, porque ela explica por que os novos algoritmos exigem novas habilidades de revisão. O código que lida com polinômios e ruído tem modos de falha diferentes do código que lida com inteiros grandes, como erros na redução ou na amostragem do ruído.

6.5 Erros comuns e limites

Esquecer a troca de sinal ao reduzir x^n a −1.
Acreditar que a estrutura do anel sozinha dá segurança; sem ruído, as equações são fáceis de resolver.
Supor que "nenhum ataque conhecido" significa "demonstradamente seguro".

A troca de sinal é o erro mais comum no cálculo à mão, e os testes com respostas conhecidas o detectam. O segundo erro importa mais: o anel torna a aritmética conveniente, mas a segurança vem do ruído acrescentado. Sem ele, as equações são álgebra linear comum e fáceis de resolver. "Nenhum ataque conhecido" é uma afirmação sobre o conhecimento atual, então as normas incluem margens de segurança e são revistas à medida que a pesquisa continua.

Exercícios

EX011 — Ordem de um elemento. Encontre a ordem de 3 módulo 7 listando as potências. Rubrica: 3 = ordem correta, com a lista.
EX012 — Produto no anel. Calcule (2 + x)(3 + x³) em Z_17[x]/(x⁴+1) e confira com o Laboratório R. Rubrica: 3 = coeficientes corretos, com a redução mostrada.

Síntese

A criptografia de chave pública clássica esconde períodos em grupos, que o algoritmo de Shor encontra. A PQC baseada em reticulados calcula em anéis de polinômios e esconde os segredos sob ruído, uma estrutura sem atalho quântico conhecido.