Aritmética modular y criptografía

La idea

Trabajar módulo n es contar como un reloj: después de n − 1 se vuelve al 0. Decimos que a ≡ b (mod n) cuando n divide a a − b, y esta relación de congruencia respeta la suma, la resta y el producto, de modo que se puede calcular con restos sin perder información. La división, en cambio, es delicada: el inverso modular de a, un número a⁻¹ con a·a⁻¹ ≡ 1 (mod n), existe únicamente cuando mcd(a, n) = 1, y se obtiene con el algoritmo de Euclides extendido, que encuentra x e y tales que a x + n y = mcd(a, n).

Elevar a potencias módulo n se hace con exponenciación rápida: se escribe el exponente en binario y se eleva al cuadrado repetidamente reduciendo en cada paso, lo que cuesta O(log e) multiplicaciones en lugar de e. Dos resultados clásicos gobiernan estas potencias: el pequeño teorema de Fermat, a^(p−1) ≡ 1 (mod p) si p es primo y no divide a a, y su generalización, el teorema de Euler, a^φ(n) ≡ 1 (mod n) cuando mcd(a, n) = 1, donde φ es la función indicatriz que cuenta los enteros menores que n coprimos con n.

Sobre esas piezas se construye RSA. Se eligen dos primos p y q, se calcula n = p·q y φ(n) = (p − 1)(q − 1), se toma un exponente público e coprimo con φ(n) y se despeja el privado d ≡ e⁻¹ (mod φ(n)). Cifrar es c = mᵉ mod n y descifrar m = c^d mod n; funciona porque m^(ed) = m^(1 + kφ(n)) ≡ m (mod n). La seguridad no viene de las matemáticas del cifrado, que son públicas, sino de que factorizar n para recuperar p y q es computacionalmente inabordable cuando los primos tienen cientos de dígitos. El mismo lenguaje modular está detrás de los códigos de control (IBAN, ISBN, dígitos verificadores) y de las funciones hash.

Fórmulas clave

• Congruenciaa ≡ b (mod n) ⇔ n | (a − b)
• Euclides extendidoa x + n y = mcd(a, n); si mcd = 1 → a⁻¹ ≡ x (mod n)
• Exponenciación rápidaa^e mod n en O(log e) multiplicaciones
• Pequeño teorema de Fermata^(p−1) ≡ 1 (mod p), p primo, p ∤ a
• Teorema de Eulera^φ(n) ≡ 1 (mod n), mcd(a, n) = 1
• RSAn = p q, φ = (p−1)(q−1), e d ≡ 1 (mod φ), c = mᵉ mod n, m = c^d mod n

Dónde se aplica

Cada conexión HTTPS negocia claves con aritmética modular: RSA o Diffie-Hellman sobre enteros grandes, y las curvas elípticas modernas trabajan módulo un primo de 256 bits. Los dígitos de control del IBAN se calculan como un resto módulo 97, y los del ISBN y de la CURP con pesos y módulos parecidos, lo que permite detectar errores de tecleo al instante. Las tablas hash reparten claves con la operación h(k) = k mod m, y los generadores de números pseudoaleatorios congruenciales lineales, presentes en simuladores y videojuegos, se definen con xₙ₊₁ = (a xₙ + c) mod m.

Con programación (Python)

def euclides_ext(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = euclides_ext(b, a % b)
    return g, y, x - (a // b) * y

def inverso(a, n):
    g, x, _ = euclides_ext(a % n, n)
    if g != 1:
        return None
    return x % n

def potmod(a, e, n):
    r, a = 1, a % n
    while e > 0:
        if e & 1:
            r = r * a % n
        a = a * a % n
        e >>= 1
    return r

p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)
e = 17
d = inverso(e, phi)
print("n =", n, " phi =", phi, " e =", e, " d =", d, " e*d mod phi =", e * d % phi)

m = 65
c = potmod(m, e, n)
print("mensaje", m, "-> cifrado", c, "-> descifrado", potmod(c, d, n))

print("Fermat: 3^(97-1) mod 97 =", potmod(3, 96, 97))
print("inverso de 7 mod 26 =", inverso(7, 26), " comprobacion:", 7 * inverso(7, 26) % 26)
print("reloj modulo 12, saltos de 5:", [5 * k % 12 for k in range(12)])

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Recursión y memoización · Combinatoria y triángulo de Pascal · Complejidad y notación O grande