RSA

O RSA é uma cifra de chave pública. Cada pessoa tem um par de chaves: a chave pública, que pode ser entregue a qualquer um e serve para cifrar, e a chave privada, que fica só com o dono e serve para decifrar. Ninguém precisa combinar um segredo antes, que é justamente o problema das cifras de chave única, como o AES.

Tudo no RSA é conta com inteiros (a mensagem vira número como no conceito Texto como número), sempre módulo n: só interessa o resto da divisão por n, o % do Python. Com números pequenos, dá para fazer na mão.

Gerar as chaves.

1. Escolha dois números primos: p = 5 e q = 11.
2. Multiplique: n = p × q = 55. É o módulo, e é público.
3. Calcule phi = (p - 1) × (q - 1) = 4 × 10 = 40. Só quem conhece p e q chega nesse número.
4. Escolha o expoente público e, sem fator em comum com phi: e = 3 serve.
5. Calcule d, o inverso de e módulo phi: o número que faz e × d deixar resto 1 na divisão por phi. Aqui d = 27, porque 3 × 27 = 81 = 2 × 40 + 1.

A chave pública é o par (n, e) = (55, 3). A chave privada é d = 27, e p, q e phi também ficam em segredo, porque quem tem qualquer um deles calcula d.

Cifrar e decifrar. Para cifrar a mensagem m = 9, eleve-a a e e fique com o resto da divisão por n: c = m^e mod n = 9^3 mod 55. Como 9^3 = 729 = 13 × 55 + 14, o cifrado é c = 14. Para decifrar, o dono eleva o cifrado a d: m = c^d mod n = 14^27 mod 55 = 9, e a mensagem volta.

Em Python, com uma pegadinha: lá o ^ é XOR, não potência. Potência é **, e o pow com três argumentos faz a potência já reduzindo módulo n, sem calcular o número gigante 14 ** 27. pow(e, -1, phi) calcula o inverso (Python 3.8 ou mais novo):

p, q, e = 5, 11, 3
n = p * q                 # 55, público
phi = (p - 1) * (q - 1)   # 40, secreto
d = pow(e, -1, phi)       # 27, a chave privada
c = pow(9, e, n)          # cifrar: 14
print(pow(c, d, n))       # decifrar: 9

Por que funciona. d foi escolhido para desfazer e: elevar a e e depois a d, sempre módulo n, devolve o número original, para qualquer m menor que n. É um resultado de Euler sobre restos de potências.

Por que é seguro, e por que números enormes. Quem só tem a chave pública (55, 3) precisa de phi para calcular d, e para phi precisa de p e q. Com n = 55, qualquer um fatora de cabeça: 5 × 11. Com um n de 2048 bits (617 algarismos), produto de dois primos de mais de 300 algarismos cada, nenhum computador conhecido consegue em tempo útil. Esse é o tamanho mínimo aceito hoje; para dados que precisam continuar protegidos depois de 2030, recomendam-se 3072 bits.

Por que o preenchimento. O RSA "de livro", como o de cima, tem dois defeitos:

• É determinístico: a mesma mensagem dá sempre o mesmo cifrado. Se o segredo é "sim" ou "não", o atacante cifra as duas respostas com a chave pública e compara com o que interceptou.
• Mensagem pequena nem chega a dar a volta no módulo. Com e = 3, m = 2 cifra para c = 8, que é só 2^3: basta tirar a raiz cúbica, sem chave nenhuma.

Por isso, na prática, a mensagem recebe um preenchimento (padding) aleatório antes de ser cifrada, o OAEP, que deixa o número do tamanho de n e diferente a cada vez. O expoente público costuma ser e = 65537. E nada disso se implementa à mão: usa-se uma biblioteca, como a pycryptodome:

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Hash import SHA256

chave = RSA.generate(3072)            # e = 65537 por padrão
c = PKCS1_OAEP.new(chave.publickey(), hashAlgo=SHA256).encrypt(b'lote 9 vendido')
print(PKCS1_OAEP.new(chave, hashAlgo=SHA256).decrypt(c))

Cifrar duas vezes a mesma mensagem assim dá dois c diferentes, e os dois decifram certo. Como o RSA é lento e só cifra mensagens menores que n, ele não cifra arquivos inteiros: cifra uma chave de AES sorteada, e o AES cifra o arquivo (é a cifra híbrida, usada por exemplo no e-mail cifrado com PGP). A mesma matemática, com os papéis trocados (o dono usa d e qualquer um confere com e) e outro preenchimento, o PSS, dá a assinatura digital, que é como o RSA aparece nos certificados dos sites.