◇ OpenCyber Academy
Engenharia · Capítulo 2 · Português

Capítulo 2 — Matemática discreta

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 2 — Matemática discreta

Mapa da aula

Aula 02 publicada. Mapa, exemplo, EX004.

flowchart TD
  N0["2.1 Aritmética do relógio"]
  N1["2.2 Inversos e Fermat"]
  N2["Laboratório — Aritmética modular de brinquedo"]
  N3["2.3 Ler o brinquedo"]
  N4["Síntese"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX004"]

Desenho lógico

flowchart LR
  N0["2.1 Aritmética do relógio"]
  N1["2.2 Inversos e Fermat"]
  N2["Laboratório — Aritmética modular de brinquedo"]
  N3["2.3 Ler o brinquedo"]
  N4["Síntese"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX004"]

[2.1 Aritmética do relógio]
    |
    v
[2.2 Inversos e Fermat]
    |
    v
[Laboratório — Aritmética modular de brinquedo]
    |
    v
[2.3 Ler o brinquedo]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX004]

Objetivos de aprendizagem

Você vai (1) calcular com aritmética modular; (2) explicar por que os inversos modulares e o pequeno teorema de Fermat importam para os sistemas de chave pública; (3) reconhecer por que exemplos de brinquedo nunca devem virar chaves reais.

2.1 Aritmética do relógio

A aritmética modular funciona como um relógio: os números dão a volta depois de chegar ao módulo. Dezessete horas depois das 9 horas são 2 horas, porque 26 mod 24 é igual a 2. A criptografia de chave pública vive nesse mundo. Aiyana pratica adição, multiplicação e exponenciação módulo n e aprende que o pow(b, e, n) de três argumentos do Python calcula b^e mod n com eficiência, por quadrados sucessivos, sem jamais construir o enorme número intermediário. O Handbook of Applied Cryptography, no capítulo 2, reúne essas ferramentas da teoria dos números e está disponível gratuitamente na internet, o que o torna sua referência para definições como máximo divisor comum e inverso multiplicativo.

2.2 Inversos e Fermat

Um número e tem inverso módulo m quando mdc(e, m) = 1; o inverso d satisfaz e × d mod m = 1, e o algoritmo de Euclides estendido o encontra. O pequeno teorema de Fermat diz que, para um primo p e um a não divisível por p, a^(p-1) mod p = 1. Junto com a generalização de Euler, esses fatos explicam por que a construção do RSA de livro-texto consegue reverter uma exponenciação com um segundo expoente. Aiyana trata isso como compreensão, e não como engenharia: a RFC 8017 mostra que o RSA real precisa de esquemas de preenchimento (padding) como o OAEP e o PSS, porque a operação crua de livro-texto vaza estrutura e é insegura.

Laboratório — Aritmética modular de brinquedo

"""Modular arithmetic facts behind public-key cryptography, on toy numbers (never a real key)."""
from math import gcd
p, q = 61, 53            # textbook-sized primes, far too small for any real use
n, phi = p * q, (p - 1) * (q - 1)
e = 17

def main():
    d = pow(e, -1, phi)  # modular inverse (Python 3.8+)
    print(f"n={n} phi={phi} gcd(e,phi)={gcd(e, phi)} d={d} (e*d mod phi = {e * d % phi})")
    m = 65
    c = pow(m, e, n)
    print(f"toy m={m} -> c={c} -> back {pow(c, d, n)}")
    print(f"Fermat check: 7^(61-1) mod 61 = {pow(7, 60, 61)}")

if __name__ == "__main__":
    main()

Execute com python3 lab_modular.py. Saída verificada:

n=3233 phi=3120 gcd(e,phi)=1 d=2753 (e*d mod phi = 1)
toy m=65 -> c=2790 -> back 65
Fermat check: 7^(61-1) mod 61 = 1

2.3 Ler o brinquedo

Com os primos 61 e 53, o módulo é 3233 e phi é 3120. O expoente 17 não tem fator em comum com 3120, então seu inverso existe e é igual a 2753, e 17 × 2753 mod 3120 é 1. Elevar 65 à 17ª potência dá 2790, e elevar 2790 a 2753 devolve 65. A verificação de Fermat imprime 1 para 7^60 mod 61. Aiyana escreve em vermelho nas suas anotações que esses números podem ser fatorados à mão instantaneamente, que não há preenchimento nem aleatoriedade e que a Ridgeway vai usar, em vez disso, bibliotecas avaliadas que implementam assinaturas do FIPS 186-5 ou da RFC 8032. Os módulos RSA reais têm hoje pelo menos 2048 bits, e a geração de chaves fica a cargo de bibliotecas auditadas.

Exemplo resolvido

Aiyana calcula o inverso de 17 módulo 3120, verifica o teorema de Fermat para 7 e 61 e explica por que a mesma aritmética com números de tamanho real ainda precisa do preenchimento padronizado.

Caso sintético. Os primos e a mensagem são brinquedos de livro-texto; a RFC 8017 e o FIPS 186-5 são as normas reais.

Erros e limites

O RSA de brinquedo é um recurso didático. Copiá-lo para um software, mesmo com primos grandes, produz um sistema inseguro, sem preenchimento, sem cuidado com canais laterais e sem geração de chaves avaliada.

Exercícios

Síntese

A aritmética modular, os inversos e o teorema de Fermat explicam a matemática da chave pública, mas os sistemas reais dependem de esquemas padronizados e de bibliotecas avaliadas.

Continue estudando — aula 02 (capítulo 02 de 50)

← Capítulo 01 · Índice das aulas · Capítulo 03 →

Continue para a próxima aula já escrita.