ML-KEM: Mecanismo de Encapsulamiento de Claves basado en Retículos

🔐

Tema relacionado: Tema 4: Estandarización de Criptografía Post-Cuántica

Introducción

ML-KEM (Module-Lattice Key Encapsulation Mechanism), anteriormente conocido como CRYSTALS-Kyber, es un mecanismo de encapsulamiento de claves basado en problemas de retículos modulares. Ha sido seleccionado por el NIST como el estándar FIPS 203 para el intercambio de claves post-cuántico.

ML-KEM proporciona un método seguro para que dos partes establezcan una clave compartida que puede utilizarse posteriormente para cifrado simétrico. A diferencia de los algoritmos de intercambio de claves tradicionales como Diffie-Hellman o RSA, ML-KEM está diseñado para resistir ataques de ordenadores cuánticos.

En este ejemplo, exploraremos cómo funciona ML-KEM y demostraremos sus operaciones básicas: generación de claves, encapsulamiento y desencapsulamiento.

Fundamento Teórico

Problemas de Retículos

ML-KEM basa su seguridad en la dificultad de resolver ciertos problemas relacionados con retículos, específicamente el problema de Learning With Errors (LWE) en su variante modular:

Module-LWE (MLWE): Una generalización de Ring-LWE que proporciona un mejor equilibrio entre seguridad y eficiencia.
Problema Computacional: Dado un conjunto de muestras (a, b = a·s + e), donde a es aleatorio, s es secreto y e es un pequeño error, encontrar s es computacionalmente difícil.

Estructura de ML-KEM

ML-KEM es un mecanismo de encapsulamiento de claves (KEM) que consta de tres algoritmos principales:

KeyGen: Genera un par de claves pública/privada.
Encaps: Utiliza la clave pública para encapsular (cifrar) una clave simétrica compartida.
Decaps: Utiliza la clave privada para desencapsular (descifrar) la clave simétrica compartida.

Parámetros de ML-KEM

ML-KEM viene en tres variantes que ofrecen diferentes niveles de seguridad:

Variante	Nivel de Seguridad	Tamaño de Clave Pública	Tamaño de Clave Privada	Tamaño de Cifrado
ML-KEM-512	Nivel 1 (AES-128)	800 bytes	1,632 bytes	768 bytes
ML-KEM-768	Nivel 3 (AES-192)	1,184 bytes	2,400 bytes	1,088 bytes
ML-KEM-1024	Nivel 5 (AES-256)	1,568 bytes	3,168 bytes	1,568 bytes

Operaciones Matemáticas

ML-KEM utiliza varias operaciones matemáticas específicas:

Polinomios: Operaciones en el anillo R = Z_q[X]/(X^n + 1), donde n = 256 y q = 3329.
Módulos: Vectores y matrices de polinomios que permiten ajustar el nivel de seguridad.
NTT (Transformada Número-Teórica): Utilizada para multiplicación eficiente de polinomios.
Compresión y Descompresión: Técnicas para reducir el tamaño de las claves y cifrados.
Funciones Hash: SHA3-256, SHA3-512 y SHAKE-128/256 para derivación de claves y aleatorización.

Simulación Interactiva

Nivel de Seguridad:

Resultados

Seleccione un nivel de seguridad y haga clic en "Generar Claves" para comenzar.

Clave Pública

Clave Privada

Clave Compartida

Cifrado

Visualización

Implementación

A continuación se muestra una implementación simplificada de ML-KEM en Python. Esta implementación es para fines educativos y omite muchos detalles técnicos del algoritmo real.

import numpy as np
import hashlib
import secrets

# Parámetros simplificados para ML-KEM
class MLKEMParams:
    def __init__(self, k, eta1, eta2, du, dv):
        self.n = 256  # Grado del polinomio
        self.q = 3329  # Módulo
        self.k = k  # Dimensión del módulo
        self.eta1 = eta1  # Parámetro de distribución de ruido
        self.eta2 = eta2  # Parámetro de distribución de ruido
        self.du = du  # Parámetro de compresión
        self.dv = dv  # Parámetro de compresión

# Definición de parámetros para diferentes niveles de seguridad
def get_params(security_level):
    if security_level == 512:  # Nivel 1
        return MLKEMParams(k=2, eta1=3, eta2=2, du=10, dv=4)
    elif security_level == 768:  # Nivel 3
        return MLKEMParams(k=3, eta1=2, eta2=2, du=10, dv=4)
    elif security_level == 1024:  # Nivel 5
        return MLKEMParams(k=4, eta1=2, eta2=2, du=11, dv=5)
    else:
        raise ValueError("Nivel de seguridad no válido")

# Funciones auxiliares simplificadas
def sample_poly(n, q, eta):
    """Genera un polinomio con coeficientes pequeños."""
    return np.array([secrets.randbelow(2*eta+1) - eta for _ in range(n)]) % q

def sample_matrix(k, n, q):
    """Genera una matriz de polinomios aleatorios."""
    return np.array([[secrets.randbelow(q) for _ in range(n)] for _ in range(k)])

def compress(x, d, q):
    """Comprime un valor x a d bits."""
    return round((2**d / q) * x) % (2**d)

def decompress(x, d, q):
    """Descomprime un valor x de d bits."""
    return round((q / 2**d) * x) % q

def hash_function(data, length):
    """Función hash simplificada basada en SHA3."""
    h = hashlib.sha3_256(data).digest()
    if length > len(h):
        h += hashlib.sha3_256(h).digest()
    return h[:length]

# Implementación simplificada de ML-KEM
class MLKEM:
    def __init__(self, security_level=768):
        self.params = get_params(security_level)
        self.n = self.params.n
        self.q = self.params.q
        self.k = self.params.k
    
    def keygen(self):
        """Genera un par de claves pública/privada."""
        # Generar semilla aleatoria
        d = secrets.token_bytes(32)
        
        # Generar matriz A (en una implementación real, esto se haría de forma determinista)
        A = sample_matrix(self.k, self.n, self.q)
        
        # Generar vector secreto s
        s = np.array([sample_poly(self.n, self.q, self.params.eta1) for _ in range(self.k)])
        
        # Generar vector de error e
        e = np.array([sample_poly(self.n, self.q, self.params.eta1) for _ in range(self.k)])
        
        # Calcular t = A·s + e
        t = np.zeros((self.k, self.n), dtype=int)
        for i in range(self.k):
            for j in range(self.k):
                # En una implementación real, esto sería una multiplicación de polinomios
                t[i] = (t[i] + np.convolve(A[i, j], s[j], mode='same')) % self.q
            t[i] = (t[i] + e[i]) % self.q
        
        # Clave pública: (t, d)
        public_key = (t, d)
        
        # Clave privada: (s, t, d)
        private_key = (s, t, d)
        
        return public_key, private_key
    
    def encaps(self, public_key):
        """Encapsula una clave compartida usando la clave pública."""
        t, d = public_key
        
        # Generar mensaje aleatorio m
        m = secrets.token_bytes(32)
        
        # Derivar ruido y semilla a partir de m y d
        seed = hash_function(m + bytes(d), 32)
        
        # Generar matriz A (en una implementación real, esto se haría de forma determinista)
        A = sample_matrix(self.k, self.n, self.q)
        
        # Generar vector r
        r = np.array([sample_poly(self.n, self.q, self.params.eta1) for _ in range(self.k)])
        
        # Generar vector de error e1
        e1 = np.array([sample_poly(self.n, self.q, self.params.eta2) for _ in range(self.k)])
        
        # Generar error e2
        e2 = sample_poly(self.n, self.q, self.params.eta2)
        
        # Calcular u = A^T·r + e1
        u = np.zeros((self.k, self.n), dtype=int)
        for i in range(self.k):
            for j in range(self.k):
                # En una implementación real, esto sería una multiplicación de polinomios
                u[i] = (u[i] + np.convolve(A[j, i], r[j], mode='same')) % self.q
            u[i] = (u[i] + e1[i]) % self.q
        
        # Calcular v = t^T·r + e2 + ⌈q/2⌋·m
        v = np.zeros(self.n, dtype=int)
        for i in range(self.k):
            # En una implementación real, esto sería una multiplicación de polinomios
            v = (v + np.convolve(t[i], r[i], mode='same')) % self.q
        
        # Añadir error y mensaje
        v = (v + e2) % self.q
        
        # Codificar mensaje en el dominio de la señal
        m_bits = ''.join(format(b, '08b') for b in m)
        for i in range(min(self.n, len(m_bits))):
            if i < len(m_bits) and m_bits[i] == '1':
                v[i] = (v[i] + (self.q // 2)) % self.q
        
        # Comprimir u y v
        u_compressed = np.array([[compress(u[i][j], self.params.du, self.q) 
                                 for j in range(self.n)] for i in range(self.k)])
        v_compressed = np.array([compress(v[j], self.params.dv, self.q) 
                                for j in range(self.n)])
        
        # Cifrado: (u_compressed, v_compressed)
        ciphertext = (u_compressed, v_compressed)
        
        # Derivar clave compartida
        shared_key = hash_function(m + bytes(ciphertext), 32)
        
        return ciphertext, shared_key
    
    def decaps(self, private_key, ciphertext):
        """Desencapsula la clave compartida usando la clave privada y el cifrado."""
        s, t, d = private_key
        u_compressed, v_compressed = ciphertext
        
        # Descomprimir u y v
        u = np.array([[decompress(u_compressed[i][j], self.params.du, self.q) 
                      for j in range(self.n)] for i in range(self.k)])
        v = np.array([decompress(v_compressed[j], self.params.dv, self.q) 
                     for j in range(self.n)])
        
        # Calcular m' = v - s^T·u
        m_prime = np.copy(v)
        for i in range(self.k):
            # En una implementación real, esto sería una multiplicación de polinomios
            m_prime = (m_prime - np.convolve(s[i], u[i], mode='same')[:self.n]) % self.q
        
        # Decodificar mensaje
        m = bytearray(32)
        for i in range(min(self.n, 256)):  # 256 bits = 32 bytes
            bit_pos = i // 8
            bit_offset = i % 8
            # Comprobar si el coeficiente está más cerca de q/2 o 0
            if abs(m_prime[i] - (self.q // 2)) < abs(m_prime[i]):
                m[bit_pos] |= (1 << bit_offset)
        
        # Verificar la validez del mensaje desencapsulado
        seed = hash_function(bytes(m) + bytes(d), 32)
        
        # En una implementación real, se recalcularía el cifrado y se verificaría
        # que coincide con el recibido
        
        # Derivar clave compartida
        shared_key = hash_function(bytes(m) + bytes(ciphertext), 32)
        
        return shared_key

# Ejemplo de uso
def main():
    # Crear instancia de ML-KEM con nivel de seguridad 3
    mlkem = MLKEM(security_level=768)
    
    # Generar par de claves
    public_key, private_key = mlkem.keygen()
    print("Claves generadas")
    
    # Encapsular clave compartida
    ciphertext, shared_key_encaps = mlkem.encaps(public_key)
    print("Clave encapsulada")
    
    # Desencapsular clave compartida
    shared_key_decaps = mlkem.decaps(private_key, ciphertext)
    print("Clave desencapsulada")
    
    # Verificar que las claves compartidas coinciden
    if shared_key_encaps == shared_key_decaps:
        print("Éxito: Las claves compartidas coinciden")
    else:
        print("Error: Las claves compartidas no coinciden")

if __name__ == "__main__":
    main()

Esta implementación es una simplificación significativa del algoritmo ML-KEM real. En la práctica, ML-KEM utiliza:

Transformada Número-Teórica (NTT) para multiplicación eficiente de polinomios
Generación determinista de la matriz A a partir de una semilla
Técnicas de muestreo eficientes para distribuciones binomiales
Codificación y decodificación optimizadas
Medidas adicionales contra ataques de canal lateral

Para implementaciones completas y seguras, se recomienda utilizar bibliotecas criptográficas establecidas como liboqs o pqcrypto.

Ventajas y Consideraciones

Ventajas

Seguridad Post-Cuántica: Resistente a ataques de ordenadores cuánticos, incluido el algoritmo de Shor.
Eficiencia: Operaciones relativamente rápidas y tamaños de clave/cifrado moderados.
Flexibilidad: Diferentes niveles de seguridad para distintas necesidades.
Estandarización: Seleccionado como estándar FIPS 203 por el NIST.
Análisis Extenso: Ha sido sometido a un riguroso análisis criptográfico durante el proceso de selección del NIST.

Consideraciones

Tamaño de Claves: Las claves son más grandes que en criptografía de curva elíptica (aunque más pequeñas que otros esquemas post-cuánticos).
Novedad: Menos probado en el tiempo que algoritmos tradicionales como RSA o ECDH.
Implementación: Requiere cuidado para evitar vulnerabilidades de implementación y ataques de canal lateral.
Integración: La migración a ML-KEM en sistemas existentes puede requerir modificaciones significativas.

Comparación con Otros Mecanismos de Intercambio de Claves

Característica	ML-KEM	RSA	ECDH
Seguridad Post-Cuántica	Sí	No	No
Tamaño de Clave Pública (Nivel 128 bits)	~800-1,568 bytes	~256-384 bytes	~32-64 bytes
Tamaño de Cifrado/Intercambio	~768-1,568 bytes	~256-384 bytes	~32-64 bytes
Velocidad de Operación	Rápida	Lenta	Muy rápida
Base Matemática	Retículos Modulares	Factorización	Logaritmo Discreto

Aplicaciones Prácticas

TLS/SSL

ML-KEM puede integrarse en protocolos TLS para establecer conexiones seguras post-cuánticas. Existen implementaciones experimentales en OpenSSL y BoringSSL que permiten el uso de ML-KEM en el handshake TLS, ya sea en modo híbrido (combinado con ECDHE) o como único mecanismo.

VPN

Las redes privadas virtuales pueden utilizar ML-KEM para el establecimiento de claves, proporcionando seguridad post-cuántica para las comunicaciones empresariales. Proyectos como OpenVPN y WireGuard están explorando la integración de algoritmos post-cuánticos.

Cifrado de Correo Electrónico

Protocolos como S/MIME y OpenPGP pueden beneficiarse de ML-KEM para el intercambio seguro de claves de sesión, permitiendo el cifrado de correos electrónicos resistente a ataques cuánticos.

IoT y Dispositivos Embebidos

ML-KEM es relativamente eficiente en términos de recursos computacionales, lo que lo hace adecuado para dispositivos con restricciones como sensores IoT y sistemas embebidos que necesitan seguridad a largo plazo.

Recursos Adicionales

← Anterior: Algoritmo de Shor Siguiente: ML-DSA →