Sesión 61: Knuth TAOCP Cap. 1 — Fundamentos de Criptografía: Euclides Extendido, Inverso Modular y Diffie-Hellman#

Tiempo estimado: 75-85 minutos. Nivel: De Junior/Trainee a Staff Specialist. Herramientas obligatorias: Hoja cuadriculada, lápiz, regla y calculadora.

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Consulta rápida: Glosario Maestro | Guía de Diagramas

Máximo Común Divisor (MCD / GCD) y Algoritmo de Euclides#

• (a) En palabras simples (intuición): Si tienes dos baldosas de 240 cm y 46 cm y quieres recortar azulejos cuadrados idénticos lo más grandes posible que cubran ambas longitudes sin que sobre nada, el tamaño de ese cuadrado es el MCD. Euclides descubrió hace 2,300 años que en vez de factorizar números gigantes, basta con restar o sacar el residuo repetidamente: el divisor pasa a ser dividendo y el residuo pasa a ser el nuevo divisor.
• (b) Definición técnica paso a paso: Algoritmo numérico que calcula el entero positivo más grande que divide exactamente a dos enteros a y b:

Complejidad de tiempo: O(log(min(a, b))) divisiones por el Teorema de Lamé.

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante un bucle while b != 0 con variables mutables en el Stack o con recursión de cola en una función pura.
• (d) Error típico de Junior: Intentar hallar el MCD descomponiendo ambos números en factores primos mediante divisiones de prueba en O(√(N)), lo cual es intratable para números de 2048 bits en criptografía.

Algoritmo de Euclides Extendido e Identidad de Bézout#

• (a) En palabras simples (intuición): El algoritmo de Euclides común solo te dice cuál es el MCD. El algoritmo extendido te entrega además dos "pesos mágicos" enteros x e y (que pueden ser negativos) tales que a · x + b · y = MCD. Es como equilibrar una balanza de dos platos usando solo pesas de tamaño a y b.
• (b) Definición técnica paso a paso: Teorema de Étienne Bézout (1779): para cualesquiera enteros a y b con g = gcd(a, b), existen enteros x, y ∈ ℤ tales que:

El algoritmo extendido computa g, x, y mediante inducción hacia atrás durante el desenrollado de la recursión euclidiana.

• (c) Cómo funciona en Rust (memoria y tipos): Retorna una tupla en el Stack (i64, i64, i64). El uso de enteros con signo (i64) es obligatorio, ya que uno de los coeficientes de Bézout siempre es negativo.
• (d) Error típico de Junior: Usar tipos sin signo (u64) para los coeficientes de Bézout, provocando un pánico inmediato de Rust por desbordamiento al restar.

Inverso Multiplicativo Modular#

• (a) En palabras simples (intuición): En la aritmética común de la escuela, el inverso de multiplicar por 3 es multiplicar por un tercio (1/3), porque 3 × (1/3) = 1. Pero en la aritmética de reloj (donde los números dan la vuelta y no existen fracciones ni decimales), ¿por qué número entero multiplicas al 3 para que el residuo al dividir entre 11 sea 1? La respuesta es 4, porque 3 × 4 = 12 ≡ 1 ±od{11}. El número 4 es el "inverso modular" de 3 módulo 11.
• (b) Definición técnica paso a paso: Un entero x es el inverso multiplicativo de a módulo m si y solo si:

• Condición de Existencia: Existe si y solo si a y m son coprimos (gcd(a, m) = 1).
• Derivación por Bézout: De a · x + m · y = 1, aplicando módulo m:
  (a · x) + 0 ≡ 1 ±od m ⟹ a · x ≡ 1 ±od m
• (c) Cómo funciona en Rust (memoria y tipos): La función retorna Option<i64>. Si gcd != 1, retorna None. Si existe, normaliza el resultado para que esté en el rango positivo [0, m - 1] con (x % m + m) % m.
• (d) Error típico de Junior: Olvidar normalizar el resultado negativo retornado por Bézout (por ejemplo, retornar -7 en vez de $4$ módulo $11$), rompiendo cálculos criptográficos posteriores.

Exponenciación Modular Rápida (Binary Exponentiation)#

• (a) En palabras simples (intuición): Si necesitas calcular 3¹⁰⁰⁰ ±od{13}, intentar calcular primero 3¹⁰⁰⁰ llenaría toda la memoria de tu computadora con un número de cientos de dígitos antes de poder dividirlo. En su lugar, elevas al cuadrado repetidamente paso a paso y sacas el residuo después de cada multiplicación, manteniendo los números diminutos todo el tiempo.
• (b) Definición técnica paso a paso: Algoritmo para computar (b^e) ±od m en tiempo logarítmico O(log e) descomponiendo el exponente e en su representación binaria:
• Si el bit actual de e es 1, multiplica el acumulador por la base actual módulo m.
• En cada paso, eleva la base al cuadrado módulo m: base = (base²) ±od m.
• Desplaza el exponente a la derecha (e = e gg 1).
• (c) Cómo funciona en Rust (memoria y tipos): Si base y modulus son de 64 bits (u64), su producto puede alcanzar 2¹²⁸ - 1, provocando un desbordamiento catastrófico si se multiplica en u64. En Rust se realiza la multiplicación temporalmente en u128 antes de aplicar el módulo: ((a as u128 * b as u128) % m as u128) as u64.
• (d) Error típico de Junior: Usar base.pow(exp) % modulus directamente de la biblioteca estándar, lo cual desborda instantáneamente para cualquier exponente superior a 64.

Intercambio de Claves Diffie-Hellman#

• (a) En palabras simples (intuición): Alicia y Bob quieren inventar una contraseña secreta por teléfono, pero un espía está escuchando toda la conversación. Mezclan un color público (amarillo) con sus colores secretos privados (rojo y azul) y se intercambian las pinturas mezcladas a la vista de todos. Luego, cada uno le agrega su color privado a la mezcla recibida. ¡Ambos terminan exactamente con la misma tonalidad final marrón, mientras que el espía no puede separar los colores para adivinarla!
• (b) Definición técnica paso a paso: Protocolo criptográfico publicado en 1976 por Whitfield Diffie y Martin Hellman:

1. Alicia y Bob acuerdan públicamente un número primo grande p y una base generadora g.
2. Alicia elige en secreto a, calcula A = g^a ±od p y se lo envía a Bob.
3. Bob elige en secreto b, calcula B = g^b ±od p y se lo envía a Alicia.
4. Alicia computa S = B^a ±od p = (g^b)^a ±od p = g^{ab} ±od p.
5. Bob computa S = A^b ±od p = (g^a)^b ±od p = g^{ab} ±od p.
6. Ambos poseen el mismo secreto compartido S, inmune a espías pasivos.

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa encapsulando la clave privada private_key: u64 como un campo estrictamente privado dentro de una estructura DiffieHellmanParty, exponiendo solo métodos que computan valores públicos.
• (d) Error típico de Junior: Intentar descifrar el secreto resolviendo el logaritmo discreto por fuerza bruta.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

Derivación Paso a Paso de la Inducción de Bézout#

¿Por qué la fórmula de transición en Euclides Extendido es x = y₁ y y = x₁ - ⌊ a / b ⌋ · y₁?

1. Por el algoritmo de división entera:
   a = q · b + r ⟹ r = a - q · b, donde q = ⌊ a / b ⌋
2. Por la llamada recursiva a extended_gcd(b, r), obtenemos por hipótesis inductiva que existen x₁, y₁ tales que:
   b · x₁ + r · y₁ = g
3. Sustituimos la expresión de r en esta ecuación:
   b · x₁ + (a - q · b) · y₁ = g
4. Reordenamos algebraicamente agrupando por los términos originales a y b:
   a · y₁ + b · (x₁ - q · y₁) = g
5. Comparando con la ecuación objetivo a · x + b · y = g:
   x = y₁, y = x₁ - q · y₁ = x₁ - ⌊ a / b ⌋ · y₁
   ¡Queda matemáticamente demostrado! Esta relación garantiza que los coeficientes se propagan con exactitud matemática perfecta en cada paso del desenrollado de la recursión.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Transición de Estados#

Consulta el diagrama vectorial:

flowchart TD
    A["ext_gcd(a, b)"] --> BASE{"¿b == 0?"}
    BASE -->|Sí| RET["Retornar (a, 1, 0)<br/>Caso Base de Bézout"]
    BASE -->|No| REC["(g, x1, y1) = ext_gcd(b, a % b)"]
    REC --> CALC["x = y1<br/>y = x1 - (a / b) * y1"]
    CALC --> OUT["Retornar (g, x, y)"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Traza de ejecución en el Stack para extended_gcd(240, 46):

FASE 1: APILAMIENTO EN EL STACK (Recursión hacia adelante)
Frame 0: ext_gcd(240, 46) -> q = 240 / 46 = 5, r = 240 % 46 = 10
Frame 1: ext_gcd(46, 10)  -> q = 46 / 10 = 4,  r = 46 % 10 = 6
Frame 2: ext_gcd(10, 6)   -> q = 10 / 6 = 1,   r = 10 % 6 = 4
Frame 3: ext_gcd(6, 4)    -> q = 6 / 4 = 1,    r = 6 % 4 = 2
Frame 4: ext_gcd(4, 2)    -> q = 4 / 2 = 2,    r = 4 % 2 = 0
Frame 5: ext_gcd(2, 0)    -> CASO BASE: retorna (g=2, x=1, y=0)

FASE 2: DESENROLLADO EN EL STACK (Cálculo de coeficientes de Bézout)
Frame 4 (4, 2):  q = 2, x1 = 1, y1 = 0
                 x = 0, y = 1 - (2)*0 = 1        -> retorna (2, 0, 1)   [4*(0) + 2*(1) = 2]
Frame 3 (6, 4):  q = 1, x1 = 0, y1 = 1
                 x = 1, y = 0 - (1)*1 = -1       -> retorna (2, 1, -1)  [6*(1) + 4*(-1) = 2]
Frame 2 (10, 6): q = 1, x1 = 1, y1 = -1
                 x = -1, y = 1 - (1)*(-1) = 2    -> retorna (2, -1, 2)  [10*(-1) + 6*(2) = 2]
Frame 1 (46, 10):q = 4, x1 = -1, y1 = 2
                 x = 2, y = -1 - (4)*2 = -9      -> retorna (2, 2, -9)  [46*(2) + 10*(-9) = 2]
Frame 0 (240, 46): q = 5, x1 = 2, y1 = -9
                 x = -9, y = 2 - (5)*(-9) = 47   -> retorna (2, -9, 47) [240*(-9) + 46*(47) = 2]

Comprobación Final en Silicio:
240 * (-9) + 46 * (47) = -2160 + 2162 = +2. ¡Identidad de Bézout exacta!

4. Implementación Canónica en Rust (Compilable con rustc --test)#

Archivo de referencia: practica-rust/dia_61.rs

/// Retorna una tupla (gcd, x, y) que satisface: a * x + b * y = gcd(a, b)
pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        if a < 0 {
            (-a, -1, 0)
        } else {
            (a, 1, 0)
        }
    } else {
        let (g, x1, y1) = extended_gcd(b, a % b);
        let x = y1;
        let y = x1 - (a / b) * y1;
        (g, x, y)
    }
}

/// Inverso multiplicativo modular tal que (a * x) % m == 1
pub fn mod_inverse(a: i64, m: i64) -> Option<i64> {
    if m <= 1 {
        return None;
    }
    let (g, x, _) = extended_gcd(a, m);
    if g != 1 {
        return None; // No son coprimos
    }
    Some((x % m + m) % m)
}

/// Exponenciación binaria modular rápida (base^exp) % modulus en O(log exp)
pub fn mod_pow(base: u64, exp: u64, modulus: u64) -> u64 {
    if modulus == 1 {
        return 0;
    }
    let mut result: u128 = 1;
    let mut base_u128: u128 = (base % modulus) as u128;
    let mut exp_curr = exp;
    let m = modulus as u128;

    while exp_curr > 0 {
        if exp_curr & 1 == 1 {
            result = (result * base_u128) % m;
        }
        base_u128 = (base_u128 * base_u128) % m;
        exp_curr >>= 1;
    }

    result as u64
}

/// Estructura para Intercambio de Claves Diffie-Hellman
pub struct DiffieHellmanParty {
    pub name: String,
    private_key: u64,
    pub prime_p: u64,
    pub generator_g: u64,
}

impl DiffieHellmanParty {
    pub fn new(name: &str, private_key: u64, prime_p: u64, generator_g: u64) -> Self {
        Self {
            name: name.to_string(),
            private_key,
            prime_p,
            generator_g,
        }
    }

    pub fn compute_public_key(&self) -> u64 {
        mod_pow(self.generator_g, self.private_key, self.prime_p)
    }

    pub fn compute_shared_secret(&self, peer_public_key: u64) -> u64 {
        mod_pow(peer_public_key, self.private_key, self.prime_p)
    }
}

Implementación de Referencia en Python Tipado#

from typing import Optional, Tuple


def extended_gcd_py(a: int, b: int) -> Tuple[int, int, int]:
    """Retorna (g, x, y) tal que a*x + b*y = g."""
    if b == 0:
        return (abs(a), 1 if a >= 0 else -1, 0)
    g, x1, y1 = extended_gcd_py(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)


def mod_inverse_py(a: int, m: int) -> Optional[int]:
    """Calcula el inverso modular de a módulo m."""
    if m <= 1:
        return None
    g, x, _ = extended_gcd_py(a, m)
    if g != 1:
        return None
    return (x % m + m) % m


def mod_pow_py(base: int, exp: int, modulus: int) -> int:
    """Exponenciación modular rápida en O(log exp)."""
    return pow(base, exp, modulus)

5. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

6. Navegación#

• ← Sesión 60: Grokking Cap. 11 — LSH y Simhash
• Sesión 62: CTCI Cap. 9 — Consistent Hashing y Token Bucket Rate Limiting →
• Mapa del Curso
• Glosario Maestro
• Guía de Diagramas de Arquitectura