RSA e Ed25519

Esta página responde a uma pergunta: como duas partes que nunca se encontraram podem confiar uma na outra numa rede pública? A resposta é a criptografia de chave pública, e você a usa sempre que um serviço desta disciplina conversa com outro: o HTTPS no gateway (TLS²⁴), o JWT que o serviço de autenticação assina e todos os outros serviços conferem²³, a chave SSH que abre um servidor ou um repositório Git²⁵, os certificados que um cluster Kubernetes usa por dentro. Vamos montar o RSA com números pequenos, ver por que sua forma de livro-texto é insegura e depois conhecer o Ed25519, a alternativa moderna.

Por que criptografia de chave pública

Na criptografia simétrica (AES, ChaCha20), a mesma chave cifra e decifra. Ela é rápida, mas os dois lados precisam já compartilhar a chave, e mandá-la pela rede é exatamente o que um bisbilhoteiro espera. Ela também não escala: com uma chave por par, N partes precisam de N(N − 1)/2 chaves, então 100 microsserviços precisariam de 4.950 segredos compartilhados.

Em 1976, Diffie e Hellman propuseram uma saída⁹: dar a cada parte duas chaves, uma pública e uma privada, de modo que o que a chave pública faz só a privada consegue desfazer. Em 1978, Rivest, Shamir e Adleman publicaram o primeiro esquema prático, o RSA¹⁸. Cada parte agora publica uma chave e guarda uma em segredo: N partes precisam de N pares de chaves, e nada secreto trafega.

O par de chaves

As duas chaves são usadas em dois sentidos, para dois trabalhos diferentes:

flowchart LR
    subgraph enc ["Cifragem: qualquer um → dono"]
        a([remetente]) -->|"cifra com a chave<br/>PÚBLICA do dono"| c[texto cifrado]:::comp
        c -->|"decifra com a chave<br/>PRIVADA do dono"| o([dono])
    end
    subgraph sig ["Assinatura: dono → qualquer um"]
        o2([dono]) -->|"assina com a chave<br/>PRIVADA do dono"| s[mensagem + assinatura]:::comp
        s -->|"verifica com a chave<br/>PÚBLICA do dono"| v([qualquer um])
    end

A cifragem dá confidencialidade (só o dono lê). A assinatura dá autenticidade e integridade (só o dono poderia tê-la produzido, e a mensagem não foi alterada); ela não esconde a mensagem.

A matemática, com números pequenos

O RSA se apoia na aritmética modular e numa assimetria: multiplicar dois primos grandes é rápido, mas fatorar o produto de volta nesses primos é inviável nos tamanhos reais de chave⁷. A geração das chaves tem cinco passos; a coluna da direita os acompanha com números de brinquedo.

O passo 5 é o algoritmo de Euclides estendido: divida φ(n) por e, depois o divisor pelo resto, e assim por diante, escrevendo cada resto como um múltiplo de e módulo φ(n). Quando o resto chega a 1, o seu coeficiente é d. As mesmas divisões conferem o passo 4: o último resto não nulo é o gcd(e, φ(n)). O simulador mostra cada divisão.

Alguns fatos que o exemplo de brinquedo esconde:

• Tamanhos reais. p e q são primos aleatórios de cerca de 1024 bits cada (um n de 2048 bits) ou mais, e e é quase sempre 65537 (2¹⁶ + 1, um primo com apenas dois bits 1, então a cifragem é rápida).
• λ em vez de φ. O padrão (RFC 8017¹⁸) calcula d módulo λ(n) = lcm(p − 1, q − 1), o que dá um d menor que funciona igual: aqui λ(n) = 780 e d = 413.
• Os primos são guardados, em segredo. O arquivo da chave privada também guarda p, q e alguns valores derivados deles, para que a decifragem use o teorema chinês do resto e rode várias vezes mais rápido. Quem descobre p ou q recalcula d, então eles são tão secretos quanto o próprio d.
• Por que funciona. (mᵉ)ᵈ = m^(ed) = m^(1 + k·φ(n)) ≡ m (mod n), pelo teorema de Euler² quando m não tem fator comum com n (e pelo teorema chinês do resto para todo outro m < n).

Cifrar e decifrar

A mensagem é primeiro transformada num inteiro m com 0 ≤ m < n. Então:

• Cifrar com a chave pública: c = mᵉ mod n
• Decifrar com a chave privada: m = cᵈ mod n

Com a chave acima, 65¹⁷ mod 3233 = 2790 e 2790²⁷⁵³ mod 3233 = 65.

Ninguém calcula 2790²⁷⁵³ multiplicando 2.752 vezes. O square-and-multiply (elevar ao quadrado e multiplicar) lê o expoente em binário: um quadrado por bit, mais uma multiplicação por bit 1. 17 = 10001₂ custa 4 quadrados e 1 multiplicação; um d de 2048 bits custa cerca de 2.048 quadrados, não 2²⁰⁴⁸ multiplicações. Reduzir mod n a cada passo mantém todo número abaixo de n².

Aplicar a fórmula diretamente, como acima, é o chamado RSA de livro-texto (textbook RSA), e ele é inseguro:

• Determinístico. O mesmo m sempre dá o mesmo c. Um atacante que consegue adivinhar as mensagens possíveis ("sim" ou "não", uma nota de A a F) cifra cada palpite com a chave pública e compara: um ataque de dicionário. Letra a letra, é uma simples cifra de substituição.
• Maleável. Multiplicar um texto cifrado por 2ᵉ mod n dobra o texto claro escondido: no exemplo, 2790 × 2¹⁷ mod 3233 decifra para 130 = 2 × 65. Um atacante consegue alterar uma mensagem que não consegue ler.
• Mensagens pequenas vazam. Com e = 3 e uma mensagem curta, m³ pode ser menor que n: aí não há redução, e uma raiz cúbica comum recupera m.

A correção é o padding com aleatoriedade antes da exponenciação, visto mais abaixo.

Assinaturas digitais

A mesma matemática com as chaves trocadas dá assinaturas. Na prática, o que se assina é um hash da mensagem, h = H(m): um hash cabe abaixo de n, e assiná-lo vale tanto quanto assinar a mensagem inteira.

• Assinar com a chave privada: s = hᵈ mod n
• Verificar com a chave pública: conferir que sᵉ mod n = h

Com a chave acima, h = 123 dá s = 123²⁷⁵³ mod 3233 = 2746, e 2746¹⁷ mod 3233 = 123. Mude um bit da mensagem ou de s e a conferência falha; produzir um s válido para outra mensagem exige d.

É assim que funciona um JWT assinado com RS256 ou PS256²³: o serviço de autenticação assina header.payload com a sua chave privada, e qualquer serviço que tenha a chave pública verifica o token sem conseguir emitir novos. As chaves públicas costumam ser publicadas como um JWK Set (RFC 7517²²) na URL que o provedor de identidade anuncia como jwks_uri.

sequenceDiagram
    participant U as Cliente
    participant A as serviço de autenticação
    participant G as API gateway
    U->>A: POST /login (credenciais)
    A->>A: assina header.payload com a chave PRIVADA (RS256 / PS256)
    A-->>U: JWT = header.payload.assinatura
    U->>G: GET /orders, Authorization: Bearer JWT
    G->>A: busca as chaves públicas (jwks_uri) e as guarda em cache
    G->>G: verifica a assinatura com a chave PÚBLICA
    G-->>U: 200 OK, ou 401 se a assinatura não confere

Criptografia híbrida

O RSA não é usado para cifrar grandes volumes de dados. Cada operação é uma exponenciação modular completa sobre números de 2048 bits, ordens de grandeza mais lenta que o AES, que as CPUs modernas executam em hardware. E uma operação carrega muito pouco: com OAEP e SHA-256, uma chave de 2048 bits cifra no máximo 256 − 2 × 32 − 2 = 190 bytes (RFC 8017, §7.1.1¹⁸).

Por isso os sistemas combinam os dois tipos de criptografia, um padrão chamado criptografia híbrida: uma chave simétrica aleatória nova cifra os dados, e o algoritmo de chave pública protege só essa chave pequena.

flowchart LR
    doc([documento]) --> aes["AES-256-GCM<br/>com a chave K"]:::comp
    k([chave aleatória K]) --> aes
    k --> oaep["RSA-OAEP com a chave<br/>pública do destinatário"]:::comp
    aes --> ct([documento cifrado])
    oaep --> wk([K, embrulhada])
    ct --> msg["mensagem = K embrulhada + documento cifrado"]
    wk --> msg

O destinatário desembrulha K com a chave privada e decifra o documento com K. O JWE (alg: RSA-OAEP-256, enc: A256GCM)²³, o OpenPGP²⁷ e a "envelope encryption" dos serviços de gerenciamento de chaves na nuvem funcionam assim.

Como o TLS 1.3 a usa

O TLS 1.2 podia fazer exatamente o que está acima: o cliente cifrava um segredo aleatório com a chave RSA do servidor. Esse modo tem uma falha: quem grava o tráfego hoje e rouba a chave privada do servidor depois decifra todas as sessões gravadas, porque uma só chave protegia todas (sem forward secrecy). O TLS 1.3 o removeu²⁴. O handshake ainda usa os dois tipos de criptografia, mas cada um para um trabalho diferente:

• uma troca Diffie–Hellman efêmera (normalmente X25519) combina um segredo novo por conexão, que nunca passa pela rede;
• a chave do certificado do servidor (RSA-PSS, ECDSA ou Ed25519) só assina o handshake, provando quem está do outro lado;
• cifras simétricas AEAD (AES-GCM ou ChaCha20-Poly1305) cifram os dados.

sequenceDiagram
    participant C as Cliente
    participant S as Servidor
    C->>S: ClientHello + key_share (valor público X25519 efêmero do cliente)
    S->>C: ServerHello + key_share (valor público X25519 efêmero do servidor)
    Note over C,S: os dois derivam o mesmo segredo (ECDHE) e depois as chaves do handshake (HKDF)
    S->>C: Certificate (chave pública do servidor, assinada por uma CA)
    S->>C: CertificateVerify: assinatura sobre o handshake com a chave PRIVADA
    S->>C: Finished (MAC sobre o handshake)
    C->>S: Finished
    C->>S: requisição HTTP, cifrada com AES-GCM
    S-->>C: resposta HTTP, cifrada com AES-GCM

Padding: OAEP e PSS

O padding corrige o RSA de livro-texto misturando aleatoriedade e estrutura ao número antes da exponenciação. Há dois esquemas padrão, ambos no PKCS #1 v2.2 / RFC 8017¹⁸, um para cada uso.

OAEP — para cifragem

O OAEP (Optimal Asymmetric Encryption Padding), proposto por Bellare e Rogaway¹⁰, combina a mensagem com uma semente aleatória por meio de duas máscaras feitas pela MGF1, uma função de geração de máscara construída sobre um hash como o SHA-256 (RFC 8017, §7.1.1):

flowchart TD
    L([rótulo, normalmente vazio]) --> LH["lHash = SHA-256(rótulo)"]
    M([mensagem]) --> DB["DB = lHash ‖ bytes zero ‖ 0x01 ‖ mensagem"]
    LH --> DB
    S([semente aleatória]) --> G1["MGF1(semente)"]
    G1 --> X1["maskedDB = DB ⊕ MGF1(semente)"]
    DB --> X1
    X1 --> G2["MGF1(maskedDB)"]
    G2 --> X2["maskedSeed = semente ⊕ MGF1(maskedDB)"]
    S --> X2
    X1 --> EM["EM = 0x00 ‖ maskedSeed ‖ maskedDB"]
    X2 --> EM
    EM --> E["RSA: c = EMᵉ mod n"]:::comp
    E --> C([texto cifrado])

• Aleatorizado: cifrar a mesma mensagem duas vezes dá textos cifrados diferentes, então o ataque de dicionário falha. A semente tem o tamanho do hash (32 bytes com SHA-256), valores demais para testar.
• Tudo ou nada: mudar qualquer bit do texto cifrado embaralha todo o bloco com padding, e a conferência na decifragem o rejeita; a maleabilidade some.
• Demonstrado: o RSA-OAEP é seguro contra ataques de texto cifrado escolhido (IND-CCA2) no modelo de oráculo aleatório.

PSS — para assinaturas

O PSS (Probabilistic Signature Scheme), também de Bellare e Rogaway¹¹, acrescenta um salt aleatório ao hash da mensagem antes da operação com a chave privada (RFC 8017, §9.1.1):

flowchart TD
    M([mensagem]) --> MH["mHash = SHA-256(mensagem)"]
    SA([salt aleatório]) --> MP["M' = 8 bytes zero ‖ mHash ‖ salt"]
    MH --> MP
    MP --> H["H = SHA-256(M')"]
    SA --> DB["DB = bytes zero ‖ 0x01 ‖ salt"]
    H --> G["MGF1(H)"]
    G --> X["maskedDB = DB ⊕ MGF1(H)"]
    DB --> X
    X --> EM["EM = maskedDB ‖ H ‖ 0xbc"]
    H --> EM
    EM --> RS["RSA: s = EMᵈ mod n"]:::comp
    RS --> SIG([assinatura])

• Aleatorizado: com o salt, assinar a mesma mensagem duas vezes dá assinaturas diferentes, ao contrário das assinaturas determinísticas PKCS#1 v1.5.
• Demonstrado: o PSS foi projetado com uma prova de segurança justa (tight), que reduz forjar uma assinatura a quebrar o próprio RSA.
• Nos protocolos: o TLS 1.3 só aceita assinaturas RSA no handshake com PSS (o v1.5 sobrevive só dentro dos certificados)²⁴; no JWT, PS256 é PSS e RS256 é v1.5. O RS256 não tem ataque prático conhecido e é o mais suportado, mas prefira PS256 (ou Ed25519) em sistemas novos.

Ed25519

O Ed25519⁵¹⁵ é um algoritmo de assinatura de curvas elípticas, padronizado na RFC 8032¹⁹. Ele não é RSA e não cifra, mas para assinaturas faz o mesmo trabalho com chaves muito menores, e hoje é a escolha preferida em muitos protocolos.

Por que curvas elípticas

A segurança do RSA vem da dificuldade de fatorar. A criptografia de curvas elípticas (ECC)⁶ usa outro problema difícil, o logaritmo discreto em curvas elípticas: dados os pontos B e A = a · B numa curva, achar a³⁵. Os melhores ataques conhecidos contra ele são muito mais lentos que os contra a fatoração, então uma chave bem menor dá a mesma segurança. O ECDSA³³, usado pelo Bitcoin e por muitos certificados TLS, é a assinatura de curvas elípticas mais antiga; o Ed25519 é o seu sucessor moderno.

As linhas de RSA e P-256 seguem o NIST SP 800-57²⁹; os níveis de Ed25519 e Ed448 são os declarados na RFC 8032¹⁹. Uma chave Ed25519 de 256 bits equivale a uma chave RSA de 3072 bits.

Como o Ed25519 funciona

O Ed25519 trabalha na curva de Edwards torcida edwards25519, birracionalmente equivalente à curva de Montgomery Curve25519 de Bernstein⁴¹⁴ (a mesma curva em outras coordenadas):

-x² + y² = 1 − (121665/121666)·x²·y²  (mod p),   p = 2²⁵⁵ − 19

Geração de chaves (RFC 8032, §5.1.5):

1. A chave privada k são 32 bytes aleatórios.
2. Aplique o hash: SHA-512(k) dá 64 bytes. Os 32 primeiros são "ajustados" (clamped, alguns bits fixados) e lidos como o escalar secreto a; os 32 últimos são um prefix guardado para assinar.
3. A chave pública é o ponto da curva A = a · B, em que B é o ponto base fixo da curva, codificado em 32 bytes.

Assinando uma mensagem m (§5.1.6):

1. Derive um nonce determinístico r = SHA-512(prefix ‖ m).
2. Calcule R = r · B.
3. Calcule S = (r + SHA-512(R ‖ A ‖ m) · a) mod ℓ, em que ℓ é a ordem do ponto base.
4. A assinatura é (R, S): 64 bytes.

A verificação confere que S · B = R + SHA-512(R ‖ A ‖ m) · A. Para ir mais fundo, veja a palestra do IEEE S&P sobre o Ed25519 na teoria e na prática³⁴.

Ed25519 comparado ao RSA

Determinismo, uma troca

O Ed25519 deriva o seu nonce da chave privada e da mensagem, em vez de pedir a um gerador de números aleatórios. Isso elimina toda uma classe de bugs catastróficos: em 2010, o PlayStation 3 da Sony assinava o seu firmware com ECDSA usando o mesmo nonce toda vez, e duas assinaturas bastaram para calcular a chave privada¹⁶. O preço é que um dispositivo cuja computação pode ser perturbada fisicamente (uma falha injetada enquanto ele assina a mesma mensagem duas vezes) pode vazar a sua chave¹⁷; isso importa para smart cards e hardware embarcado, não para servidores.

Onde o Ed25519 é usado

• SSH: chaves ssh-ed25519 (RFC 8709²⁶); desde o OpenSSH 9.5 (2023), o ssh-keygen gera chaves Ed25519 por padrão²⁸.
• TLS 1.3: ed25519 é um dos esquemas de assinatura do handshake²⁴, embora a maioria dos certificados públicos ainda use RSA ou ECDSA.
• JWT: alg: "EdDSA" com uma chave OKP e crv: "Ed25519" (RFC 8037²⁰); a RFC 9864 deprecia o EdDSA genérico em favor do explícito alg: "Ed25519"²¹.
• Git: commits e tags podem ser assinados com uma chave SSH Ed25519 (git config gpg.format ssh) ou uma chave OpenPGP Ed25519.
• X25519, o irmão do Ed25519 na mesma curva, faz acordo de chaves: o handshake TLS 1.3 acima, WireGuard, Signal e age.

Qual usar

Gerando chaves:

ssh-keygen -t ed25519 -C "you@example.com"                                 # SSH key pair
openssl genpkey -algorithm ED25519 -out ed25519.pem                        # Ed25519 private key
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out rsa.pem  # RSA private key
openssl pkey -in rsa.pem -pubout -out rsa.pub.pem                          # its public key

Vídeos

Eddie Woo resolve o RSA à mão, do mesmo jeito que o simulador acima (em inglês):

Pontos-chave