Algoritmo RSA

Algoritmo RSA

O RSA (Rivest–Shamir–Adleman)¹⁸ é um dos algoritmos de criptografia assimétrica mais antigos e mais usados. Diferentemente dos algoritmos simétricos, que usam a mesma chave para cifrar e decifrar, o RSA usa um par de chaves: uma chave pública, que qualquer pessoa pode conhecer, e uma chave privada, que deve permanecer secreta. A própria ideia de criptografia de chave pública foi apresentada por Diffie e Hellman em 1976⁹.

Sua segurança se apoia em uma assimetria matemática simples: multiplicar dois números primos grandes é rápido, mas fatorar o resultado de volta nesses primos é computacionalmente inviável com chaves de tamanho suficiente (2048 bits ou mais).

O RSA é a base de muitos protocolos que você já usa, incluindo TLS/HTTPS²⁰, SSH²¹, PGP²² e a assinatura de JWT com RS256¹⁹.

Conceitos principais

Par de chaves

As duas chaves estão ligadas matematicamente: uma mensagem cifrada com a chave pública só pode ser decifrada com a chave privada correspondente, e vice-versa.

Fundamento matemático

O RSA é construído sobre a aritmética modular e o teorema de Euler². Os passos principais são:

1. Escolha dois números primos grandes p e q.
2. Calcule n = p × q (o módulo, público).
3. Calcule a função totiente de Euler: φ(n) = (p − 1)(q − 1).
4. Escolha e tal que 1 < e < φ(n) e gcd(e, φ(n)) = 1 (comumente e = 65537).
5. Calcule d como o inverso modular de e módulo φ(n), isto é, d × e ≡ 1 (mod φ(n)).

A chave pública é (e, n). A chave privada é (d, n). Os primos p e q são descartados após a geração das chaves.

Cifragem e decifragem

Dada uma mensagem m (como um inteiro, com m < n):

• Cifrar: c = m^e mod n
• Decifrar: m = c^d mod n

A correção decorre do teorema de Euler: (m^e)^d ≡ m (mod n).

Assinaturas digitais

O RSA também pode ser usado para assinar dados, invertendo o papel das chaves:

• Assinar (com a chave privada): s = m^d mod n
• Verificar (com a chave pública): conferir que s^e mod n = m

É assim que funcionam os tokens JWT assinados com RS256: o servidor assina o token com a sua chave privada; qualquer cliente que tenha a chave pública consegue verificá-lo, sem conseguir forjar um novo.

Por que não usar RSA para tudo?

O RSA é lento em comparação com algoritmos simétricos como o AES. Na prática, o RSA é usado apenas para trocar ou proteger uma chave simétrica (um padrão chamado criptografia híbrida). A chave simétrica então cuida da maior parte da cifragem dos dados. É exatamente isso que o TLS faz.

Além disso, o RSA "puro", sem padding, é inseguro. O uso moderno exige esquemas de padding como o OAEP (para cifragem) ou o PSS (para assinaturas).

Esquemas de padding

O RSA puro — aplicar a fórmula matemática diretamente a uma mensagem — é o RSA de livro-texto (textbook RSA), e ele é quebrado na prática. Sem padding, ele vaza estrutura: cifrar a mesma mensagem sempre produz o mesmo texto cifrado, e um atacante pode manipular textos cifrados algebricamente. Dois esquemas de padding padronizados resolvem isso, um para cada caso de uso.

OAEP — Optimal Asymmetric Encryption Padding

O OAEP (definido no PKCS#1 v2 / RFC 8017¹⁶, proposto originalmente por Bellare e Rogaway¹⁰) é o padding correto a usar ao cifrar dados com RSA. Antes da exponenciação modular, o texto claro é combinado com uma semente aleatória por meio de um par de funções de geração de máscara (MGF1, tipicamente construídas sobre o SHA-256):

flowchart TD
    M([mensagem])
    L([rótulo])
    S([semente aleatória])
    H1["hash(rótulo)"]
    MGF["máscaras MGF1"]
    P["bloco com padding"]
    E["cifragem RSA\nc = m^e mod n"]
    C([texto cifrado])

    M --> P
    L --> H1 --> P
    S --> MGF --> P
    P --> E --> C

    style M fill:#ddf,stroke:#99b
    style C fill:#dfd,stroke:#9b9
    style S fill:#ffd,stroke:#bb9

Propriedades principais:

• Aleatorizado — cifrar o mesmo texto claro duas vezes produz textos cifrados diferentes, impedindo a análise de padrões.
• Tudo ou nada — um único bit invertido no texto cifrado faz a decifragem falhar por completo, em vez de produzir silenciosamente uma saída corrompida.
• Seguro IND-CCA2 — resistente a ataques de texto cifrado escolhido no modelo de oráculo aleatório.

PSS — Probabilistic Signature Scheme

O PSS (também definido no PKCS#1 v2 / RFC 8017¹⁶, apresentado por Bellare e Rogaway¹¹) é o padding correto a usar ao assinar dados com RSA. Ele funciona de forma parecida — um salt aleatório passa pelo hash junto com o digest da mensagem antes da operação com a chave privada —, o que torna cada assinatura única, mesmo para a mesma mensagem.

flowchart TD
    M([mensagem])
    SH["digest\nSHA-256"]
    SA([salt aleatório])
    MGF["máscaras MGF1\n+ saída do hash"]
    EM["mensagem codificada"]
    RS["assinatura RSA\ns = m^d mod n"]
    SIG([assinatura])

    M --> SH
    SH --> MGF
    SA --> MGF
    MGF --> EM --> RS --> SIG

    style M fill:#ddf,stroke:#99b
    style SIG fill:#dfd,stroke:#9b9
    style SA fill:#ffd,stroke:#bb9

Propriedades principais:

• Aleatorizado — o salt faz com que assinar a mesma mensagem duas vezes gere assinaturas diferentes, ao contrário do esquema de assinatura determinístico PKCS1v15.
• Prova de segurança justa (tight) — o PSS tem uma redução demonstrável à dificuldade do RSA, enquanto as assinaturas PKCS#1 v1.5 não têm.
• Identificadores padrão — RS256 (PKCS#1 v1.5) vs. PS256 (PSS com SHA-256) no JWT; prefira PS256 em sistemas novos.

Ed25519 — uma alternativa moderna

O Ed25519⁵¹⁴ é um algoritmo de assinatura de curvas elípticas baseado na curva de Edwards Curve25519⁴¹³, padronizado na RFC 8032¹⁷. Ele não é RSA, mas cumpre o mesmo papel — assinaturas digitais assimétricas — e é cada vez mais a escolha preferida em protocolos modernos.

Por que curvas elípticas?

A segurança do RSA vem da dificuldade da fatoração de inteiros⁷. A criptografia de curvas elípticas (ECC)⁶ usa outro problema difícil: o problema do logaritmo discreto em curvas elípticas (ECDLP). O ECDLP é mais difícil por bit, o que significa que chaves muito menores alcançam o mesmo nível de segurança:

Uma chave Ed25519 de 256 bits tem segurança aproximadamente equivalente à de uma chave RSA de 3072 bits, sendo muito menor e mais rápida.

Como o Ed25519 funciona

O Ed25519 é definido sobre a curva de Edwards torcida (twisted Edwards curve):

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

Geração de chaves:

1. Escolha uma chave privada aleatória k de 32 bytes.
2. Aplique o SHA-512 a k para produzir uma semente de 64 bytes; os 32 bytes inferiores são ajustados (clamped) e usados como o escalar a.
3. A chave pública é o ponto da curva A = a · B, em que B é o ponto base da curva.

Assinando uma mensagem m:

1. Derive um nonce determinístico r = hash(second_half_of_seed || m).
2. Calcule R = r · B.
3. Calcule S = (r + hash(R || A || m) · a) mod ℓ, em que ℓ é a ordem da curva.
4. A assinatura é (R, S) — 64 bytes no total.

A verificação confere que S · B == R + hash(R || A || m) · A.

Principais vantagens sobre o RSA

Determinismo — uma faca de dois gumes

As assinaturas Ed25519 são determinísticas: o nonce r é derivado da chave privada e da mensagem, e não de uma fonte aleatória externa. Isso elimina toda uma classe de bugs catastróficos — com destaque para a falha de ECDSA do Sony PlayStation 3¹⁵, em que um nonce constante expôs a chave privada. A desvantagem é que, se a função de hash for quebrada, o determinismo poderia, em teoria, ajudar um atacante; na prática, isso não é uma preocupação para o SHA-512.

Onde o Ed25519 é usado

• SSH — ssh-keygen -t ed25519 é hoje o tipo de chave recomendado²¹.
• TLS 1.3 — suportado como algoritmo de assinatura²⁰.
• JWT — identificador de algoritmo EdDSA (alg: "EdDSA" com crv: "Ed25519")¹⁹¹⁸.
• Git — assinatura de commits com GPG por meio de uma subchave Ed25519.
• Signal, WireGuard, age — todos usam chaves da família Curve25519.

Gerando as chaves RSA