Capítulo 6 — Estruturas discretas

Capítulo 6 — Estruturas discretas

Mapa da aula

Aula 06 publicada. Mapa, exemplo, EX016.

flowchart TD
  N0["6.1 Aritmética modular e grupos"]
  N1["6.2 O logaritmo discreto"]
  N2["6.3 Diffie-Hellman à mão"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3
  N3 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX016"]

Desenho lógico

flowchart LR
  N0["6.1 Aritmética modular e grupos"]
  N1["6.2 O logaritmo discreto"]
  N2["6.3 Diffie-Hellman à mão"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3 --> Q["EX016"]

[6.1 Aritmética modular e grupos]
    |
    v
[6.2 O logaritmo discreto]
    |
    v
[6.3 Diffie-Hellman à mão]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX016]

Objetivos de aprendizagem

Você vai (1) usar aritmética modular e grupos; (2) explicar o problema do logaritmo discreto; (3) relacioná-lo ao acordo de chaves Diffie-Hellman.

6.1 Aritmética modular e grupos

Priya estuda os inteiros módulo um primo p. A multiplicação módulo p, excluído o zero, forma um grupo: é fechada, associativa, tem um elemento neutro, e todo elemento tem um inverso. Alguns elementos, chamados geradores, produzem todos os elementos não nulos quando elevados a potências sucessivas. Para p = 23 e gerador 5, as potências de 5 módulo 23 percorrem todos os 22 valores não nulos. Essas estruturas, tratadas no capítulo 2 do Handbook of Applied Cryptography, estão na base de muitos sistemas de chave pública e dão um significado preciso a operações que de outra forma pareceriam aritmética arbitrária.

6.2 O logaritmo discreto

Calcular 5^x mod 23 é fácil para qualquer x, usando a exponenciação rápida. Ir para trás, encontrar x a partir do resultado, é o problema do logaritmo discreto. Para primos minúsculos, Priya consegue testar todos os valores, mas, para primos de milhares de bits, não se conhece nenhum algoritmo clássico eficiente. Essa assimetria, fácil para a frente e difícil para trás, é o que a criptografia de chave pública precisa. Priya destaca a palavra "conhece": a segurança se apoia na crença de que o problema é difícil, e o algoritmo de Shor o resolveria num computador quântico grande, o que motiva normas pós-quânticas como o FIPS 203.

6.3 Diffie-Hellman à mão

Priya resolve uma troca Diffie-Hellman de brinquedo: Alice escolhe o segredo a = 6 e envia 5^6 mod 23 = 8; Bob escolhe b = 15 e envia 5^15 mod 23 = 19. Alice calcula 19^6 mod 23 = 2 e Bob calcula 8^15 mod 23 = 2, um segredo compartilhado que nenhum dos dois enviou. Quem escuta vê 8 e 19, mas precisa resolver um logaritmo discreto. Ela enfatiza que os sistemas reais usam grupos grandes ou curvas elípticas, como o X25519 da RFC 7748, autenticam a troca para deter atacantes ativos e rodam dentro do TLS 1.3, e não como código escrito à mão. Priya repete o cálculo com uma colega para confirmar que os dois lados chegam de fato ao mesmo valor.

Exemplo resolvido

Priya verifica que 5 gera o grupo módulo 23, calcula um segredo compartilhado de brinquedo igual a 2 num Diffie-Hellman e explica por que as trocas reais usam o X25519 dentro do TLS, com autenticação.

Caso sintético. Apenas números de brinquedo; a RFC 7748 e o FIPS 203 são reais.

Erros e limites

O Diffie-Hellman não autenticado está aberto a ataques de intermediário (man-in-the-middle). Grupos de brinquedo são trivialmente quebráveis.

Exercícios

• EX016 — Propriedades de grupo. Liste as quatro propriedades de grupo. Rubrica: 3 = fechamento, associatividade, elemento neutro, inversos;; 2 = três;; 1 = uma;; 0 = nenhuma.

• EX017 — Segredo compartilhado de brinquedo. Que segredo compartilhado a troca de brinquedo produziu, e a partir de quais valores públicos? Rubrica: 3 = 2, a partir dos valores públicos 8 e 19;; 2 = só o segredo;; 1 = errado;; 0 = nenhuma.

• EX018 — Ameaça quântica. Por que o algoritmo de Shor importa aqui? Rubrica: 3 = resolveria logaritmos discretos num computador quântico grande, motivando o FIPS 203;; 2 = quântico;; 1 = nenhum motivo;; 0 = nenhuma.

Síntese

Os grupos e o problema do logaritmo discreto explicam o acordo de chaves; os sistemas reais usam curvas padronizadas dentro de protocolos autenticados.

Continue estudando — aula 06 (capítulo 06 de 40)

← Capítulo 05 · Índice das aulas · Capítulo 07 →

Continue para a próxima aula já escrita.