Teoría de Números es la rama de las matemáticas que estudia las propiedades de los números enteros y es fundamental para la criptografía moderna.

¿Qué es la Teoría de Números?

La teoría de números proporciona los fundamentos matemáticos para la criptografía, especialmente en el estudio de números primos, congruencias y estructuras algebraicas.

Conceptos Fundamentales

Números Primos

  • Definición: Número natural mayor que 1 divisible solo por 1 y sí mismo
  • Ejemplos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29…
  • Importancia: Base de la criptografía RSA
  • Distribución: Teorema de los números primos

Congruencias

  • Definición: a ≡ b (mod n) si n divide a (a - b)
  • Propiedades: Reflexiva, simétrica, transitiva
  • Operaciones: Suma, resta, multiplicación
  • Aplicación: Criptografía modular

Máximo Común Divisor (MCD)

  • Definición: Mayor entero que divide a ambos números
  • Algoritmo de Euclides: Cálculo eficiente
  • Identidad de Bézout: ax + by = mcd(a,b)
  • Aplicación: Generación de claves

Algoritmos Importantes

Algoritmo de Euclides

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def euclidean_gcd(a, b):
    """Calcular MCD usando algoritmo de Euclides"""
    while b != 0:
        a, b = b, a % b
    return a

def extended_euclidean(a, b):
    """Algoritmo de Euclides extendido"""
    if a == 0:
        return b, 0, 1
    
    gcd, x1, y1 = extended_euclidean(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    
    return gcd, x, y

# Ejemplo
gcd, x, y = extended_euclidean(48, 18)
print(f"MCD(48, 18) = {gcd}")
print(f"48*{x} + 18*{y} = {gcd}")

Exponenciación Modular

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def modular_exponentiation(base, exponent, modulus):
    """Exponenciación modular eficiente"""
    result = 1
    base = base % modulus
    
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    
    return result

# Ejemplo
result = modular_exponentiation(2, 10, 13)
print(f"2^10 mod 13 = {result}")

Test de Primalidad

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

def is_prime(n):
    """Test de primalidad simple"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def miller_rabin(n, k=40):
    """Test de primalidad Miller-Rabin"""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # Escribir n-1 como d * 2^r
    r = 0
    d = n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # Test k veces
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

Teoremas Importantes

Teorema de Fermat

  • Enunciado: Si p es primo y a no es divisible por p, entonces a^(p-1) ≡ 1 (mod p)
  • Aplicación: Test de primalidad
  • Ejemplo: 2^6 ≡ 1 (mod 7)

Teorema de Euler

  • Enunciado: Si mcd(a, n) = 1, entonces a^φ(n) ≡ 1 (mod n)
  • Función φ: Función de Euler
  • Aplicación: Criptografía RSA
  • Ejemplo: 2^6 ≡ 1 (mod 9) porque φ(9) = 6

Teorema Chino del Resto

  • Enunciado: Sistema de congruencias con módulos coprimos
  • Aplicación: Optimización de cálculos
  • Ejemplo: Resolver x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

Funciones Importantes

Función de Euler φ(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def euler_phi(n):
    """Calcular función de Euler φ(n)"""
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

# Ejemplo
phi_12 = euler_phi(12)
print(f"φ(12) = {phi_12}")

Función de Möbius

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def mobius_function(n):
    """Calcular función de Möbius μ(n)"""
    if n == 1:
        return 1
    
    count = 0
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            if n % (i * i) == 0:
                return 0
            count += 1
            n //= i
    
    if n > 1:
        count += 1
    
    return 1 if count % 2 == 0 else -1

Aplicaciones en Criptografía

RSA

  • Factorización: Dificultad de factorizar números grandes
  • Función de Euler: φ(n) = (p-1)(q-1)
  • Exponenciación: c = m^e mod n
  • Descifrado: m = c^d mod n

Diffie-Hellman

  • Logaritmo Discreto: Dificultad del problema
  • Generadores: Elementos primitivos
  • Exponenciación: g^a mod p
  • Intercambio: Claves compartidas

Curvas Elípticas

  • Grupos: Estructura de grupo
  • Puntos: Puntos sobre curvas
  • Operaciones: Suma de puntos
  • Logaritmo Discreto: Problema ECDLP

Algoritmos de Factorización

Fuerza Bruta

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def brute_force_factorization(n):
    """Factorización por fuerza bruta"""
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

Pollard’s Rho

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def pollard_rho(n):
    """Algoritmo de Pollard's Rho"""
    if n % 2 == 0:
        return 2
    
    x = random.randint(1, n-1)
    y = x
    c = random.randint(1, n-1)
    d = 1
    
    while d == 1:
        x = (x*x + c) % n
        y = (y*y + c) % n
        y = (y*y + c) % n
        d = euclidean_gcd(abs(x - y), n)
    
    return d if d != n else None

Generación de Números Primos

Generación Aleatoria

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def generate_prime(bits):
    """Generar número primo aleatorio de 'bits' bits"""
    while True:
        # Generar número impar aleatorio
        n = random.getrandbits(bits)
        n |= (1 << bits - 1) | 1  # Asegurar bit más significativo
        
        if miller_rabin(n):
            return n

# Ejemplo
prime_1024 = generate_prime(1024)
print(f"Primo de 1024 bits: {prime_1024}")

Criba de Eratóstenes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def sieve_of_eratosthenes(limit):
    """Criba de Eratóstenes para encontrar primos hasta 'limit'"""
    primes = []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = False
    
    for i in range(2, limit + 1):
        if is_prime[i]:
            primes.append(i)
    
    return primes

Herramientas Computacionales

SageMath

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# Ejemplo con SageMath
# Generar primo
p = random_prime(2^1024)

# Calcular MCD
gcd(48, 18)

# Exponenciación modular
power_mod(2, 10, 13)

# Test de primalidad
is_prime(97)

# Función de Euler
euler_phi(12)

SymPy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from sympy import isprime, gcd, powermod, totient

# Test de primalidad
isprime(97)

# MCD
gcd(48, 18)

# Exponenciación modular
powermod(2, 10, 13)

# Función de Euler
totient(12)

Conceptos Relacionados

  • RSA - Algoritmo que usa teoría de números
  • ECC - Algoritmo que usa teoría de números
  • AES - Algoritmo que complementa teoría de números
  • Funciones Hash - Algoritmos que usan teoría de números
  • Criptoanálisis - Análisis de algoritmos de teoría de números
  • Post-Quantum Cryptography - Criptografía que usa teoría de números
  • CISO - Rol que supervisa teoría de números
  • Ciberseguridad General - Disciplina que incluye teoría de números
  • Brechas de seguridad - Incidentes que afectan teoría de números
  • Vectores de ataque - Ataques contra teoría de números
  • Incident Response - Proceso que incluye teoría de números
  • SIEM - Sistema que monitorea teoría de números
  • SOAR - Automatización que gestiona teoría de números
  • EDR - Herramienta que protege teoría de números
  • Firewall - Dispositivo que complementa teoría de números
  • VPN - Conexión que usa teoría de números
  • Dashboards - Visualización de métricas teoría de números
  • Registros - Logs de operaciones teoría de números

Referencias