Algoritmos de Shor y Grover explicados

Las computadoras cuánticas no solo ejecutan algoritmos clásicos más rápido: aprovechan la superposición y la interferencia cuánticas para resolver ciertos problemas de forma exponencialmente más rápida. Dos algoritmos amenazan la mayor parte de la criptografía implementada: el de Shor (rompe RSA/ECC) y el de Grover (debilita la criptografía simétrica y los hashes).

El algoritmo de Shor (1994) resuelve la factorización de enteros y el logaritmo discreto en tiempo polinómico en una computadora cuántica. Esto rompe directamente RSA (basado en la factorización), Diffie-Hellman (logaritmo discreto mod p) y ECDH/ECDSA (logaritmo discreto en curvas elípticas).

El ingrediente clave del algoritmo de Shor es la transformada cuántica de Fourier (QFT), una versión cuántica exponencialmente más rápida de la DFT. Para encontrar el período, la QFT identifica el período de f(x) = a^x mod N, a partir del cual se obtienen los factores de N mediante GCD.

Para factorizar N: (1) Elija un valor aleatorio a < N y compruebe gcd(a,N)=1. (2) Encuentre el período r de f(x)=a^x mod N mediante la QFT. (3) Con alta probabilidad, gcd(a^{r/2}±1, N) produce un factor no trivial. El paso clásico es O(log N); la búsqueda cuántica del período es O((log N)^3), es decir, polinómica.

La mejor factorización clásica utiliza GNFS, con complejidad subexponencial O(exp((64/9 log N)^{1/3} log log N)^{2/3})). El algoritmo de Shor en una computadora cuántica tolerante a fallos tiene complejidad polinómica O((log N)^3). RSA-2048 requiere aproximadamente 4000 qubits lógicos y ~10^9 operaciones de compuerta. Las computadoras NISQ actuales tienen unos 1000 qubits ruidosos, por lo que todavía no representan una amenaza.

El algoritmo de Grover (1996) proporciona una aceleración cuadrática para búsquedas no estructuradas. Para un espacio de búsqueda de N elementos, los algoritmos clásicos necesitan O(N) consultas; Grover necesita O(√N). Aplicado a la criptografía, rompe claves simétricas de n bits en O(2^{n/2}) en lugar de O(2^n).

AES-128: seguridad clásica de 2^128; Grover la reduce a 2^64, lo que resulta inseguro frente a una computadora cuántica grande. AES-256: 2^256 → 2^128, por lo que sigue siendo seguro. Solución: duplicar el tamaño de las claves simétricas. Resistencia a colisiones de SHA-256: 2^128 → 2^85 (birthday+Grover). Preimagen de SHA-256: 2^256 → 2^128; correcto.

Las computadoras cuánticas NISQ actuales (IBM Heron: 133 qubits; Google Sycamore: 70 qubits) son demasiado pequeñas y ruidosas para realizar cálculos criptográficamente relevantes. Las estimaciones para romper RSA-2048 sitúan el momento entre 2035 y 2050 con computadoras cuánticas tolerantes a fallos. Los ataques de recopilar ahora y descifrar después ya representan una amenaza.

Los adversarios recopilan hoy tráfico cifrado y lo almacenan. Cuando haya una computadora cuántica disponible, lo descifrarán de forma retroactiva. Esto hace que los secretos de larga duración, como datos gubernamentales clasificados y historiales médicos, sean vulnerables desde hoy. La migración a PQC debe comenzar ahora para proteger esos datos.

Los problemas de retículas (LWE, SIS), los problemas basados en códigos (McEliece), las firmas basadas en hashes (SPHINCS+) y los problemas multivariantes no cuentan con ningún algoritmo cuántico conocido de tiempo polinómico. Estos problemas son la base de los estándares poscuánticos de NIST.

Los estándares PQC de NIST (ML-KEM, ML-DSA, SLH-DSA) se finalizaron en 2024. Las organizaciones deben hacer lo siguiente: inventariar el uso actual de la criptografía, identificar los datos de larga duración y priorizar la implementación de PQC para el intercambio de claves, que es lo más urgente debido a los ataques de recopilar ahora y descifrar después. Las firmas disponen de más tiempo.

¿Cuál es el impacto del algoritmo de Grover en AES-128?

El algoritmo de Shor (tiempo polinómico) rompe RSA, DH y ECC. El algoritmo de Grover (aceleración cuadrática) reduce a la mitad la seguridad efectiva de las claves simétricas. Solución: migrar a los estándares PQC de NIST, basados en retículas. Siguiente tema: el KEM CRYSTALS-Kyber.