RSA do zero

O RSA junta tudo o que vimos. A segurança vem de uma assimetria: multiplicar dois primos grandes é fácil, fatorar o produto é (até onde se sabe) difícil.

1. Escolha primos p, q grandes;  n = p·q
2. φ(n) = (p−1)(q−1)
3. Escolha e coprimo com φ(n)   (normalmente 65537)
4. d = e⁻¹ mod φ(n)

Chave pública: (n, e)      Chave privada: d
Cifrar:   c = mᵉ mod n
Decifrar: m = cᵈ mod n

Por que funciona? e·d = 1 + k·φ(n), então c^d = m^(ed) = m · (m^φ(n))ᵏ ≡ m · 1ᵏ = m (mod n), pelo teorema de Euler.

import random

def eh_primo(n, k=40):                 # Miller–Rabin
    if n < 4:
        return n in (2, 3)
    d, s = n - 1, 0
    while d % 2 == 0:
        d, s = d // 2, s + 1
    for _ in range(k):
        x = pow(random.randrange(2, n - 1), d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def primo(bits):
    while True:
        c = random.getrandbits(bits) | (1 << bits - 1) | 1
        if eh_primo(c):
            return c

p, q = primo(1024), primo(1024)
n, phi, e = p * q, (p - 1) * (q - 1), 65537
d = pow(e, -1, phi)

m = int.from_bytes("olá, RSA".encode(), "big")
c = pow(m, e, n)
assert pow(c, d, n) == m