Fuerza bruta cuántica en criptoanálisis

Ataque de Fuerza Bruta Cuántica sobre Cifrado

Un ataque de búsqueda de clave por fuerza bruta se aplica cuando el espacio de textos planos posibles es significativamente menor que el espacio total de caracteres. Eva intercepta un texto cifrado de Alicia a Bob e implementa dos funciones: DESCIFRAR(clave, texto_cifrado) para descifrar y ESTEXTOPLANO(texto) para verificar si el texto pertenece al conjunto de textos planos válidos. Si el cifrado es por bloques, DESCIFRAR opera en bloques, y ESTEXTOPLANO acumula los resultados.

El pseudocódigo del ataque es simple:

para cada clave
    texto = DESCIFRAR(clave, texto_cifrado)
    si ESTEXTOPLANO(texto) == 0 entonces devolver (clave,texto)
fin para

Los criterios de ESTEXTOPLANO utilizan estadísticas de caracteres, combinaciones o heurísticas sin bases de datos—verifican frecuencia, entropía o patrones lingüísticos.

Teoría de la Información para Evaluar el Éxito

Para un cifrado monoalfabético, estimamos la probabilidad de un falso positivo:

• LONGITUD(texto_plano) — longitud en bits
• LONGITUD(clave) — longitud de la clave en bits
• LONGITUD(texto_cifrado) — longitud del texto cifrado en bits
• ENTROPÍA(texto_plano) — entropía de Shannon del texto plano

Condiciones:

• LONGITUD(texto_plano) ≤ LONGITUD(texto_cifrado)
• Probabilidad de paso falso: 2^-(LONGITUD(texto_plano) - ENTROPÍA(texto_plano))
• Si LONGITUD(texto_plano) - ENTROPÍA(texto_plano) > LONGITUD(clave), la clave se determina de forma única

Para algoritmos que preservan la longitud: cuando LONGITUD(texto_cifrado) - ENTROPÍA(texto_plano) ≥ LONGITUD(clave), el ataque garantiza encontrar la clave.

Enfoque Cuántico a la Fuerza Bruta

La computación cuántica se basa en la superposición y el entrelazamiento de qubits. Un registro de N qubits entrelazados equivale a 2^N estados clásicos. La aritmética (suma, multiplicación, desplazamientos) se implementa con puertas cuánticas—transformaciones de operadores unitarios.

Cualquier función clásica sobre un registro de clave puede transformarse en una unitaria U(K), donde K es una superposición de todas las claves.

Algoritmo de Grover para Búsqueda de Clave

Pasos del ataque cuántico:

• Inicializar un registro K de longitud LONGITUD(clave) en una superposición uniforme de todas las claves: |K⟩ = (1/√2^{LONGITUD(clave)}) Σ |clave⟩
• Aplicar el oráculo U(K) = DESCIFRAR(K, texto_cifrado), luego ESTEXTOPLANO(U(K)): la fase se invierte para estados con ESTEXTOPLANO == 0
• Amplificar la amplitud del estado objetivo usando el algoritmo de Grover: π/4 * √2^{LONGITUD(clave)} iteraciones con operadores de difusión y el oráculo
• Medir el registro K—colapsa a la clave correcta con probabilidad ~1

El oráculo requiere implementar DESCIFRAR y ESTEXTOPLANO como circuitos cuánticos reversibles. Para cifrados por bloques—procesar por bloques con qubits auxiliares.

// Pseudocódigo de circuito cuántico (estilo Q#)
operación FuerzaBruta(keyReg : Qubit[], ciphertext : String) : (Int, String) {
    // Aplicar H a todos los qubits para superposición
    AplicarATodos(H, keyReg);
    // Oráculo: inversión de fase si ESTEXTOPLANO(DESCIFRAR(keyReg, ciphertext)) == 0
    Oráculo(keyReg, ciphertext);
    // Iteraciones de Grover
    para iter en 0 .. IteracionesGrover() - 1 {
        DifusiónGrover(keyReg);
        Oráculo(keyReg, ciphertext);
    }
    // Medir
    let clave = MedirClave(keyReg);
    return (0, DESCIFRAR(clave, ciphertext));
}

Aceleración cuadrática: O(√2^{LONGITUD(clave)}) en lugar de O(2^{LONGITUD(clave)}).

Conclusiones Clave

• Clásico vs. Cuántico: Forzar una clave de 128 bits en una CPU—10^38 operaciones; en una computadora cuántica—10^19.
• Condición de Éxito: Redundancia del texto plano (LONGITUD - ENTROPÍA) > LONGITUD(clave)/2 para un ataque práctico.
• Limitaciones: El ruido en sistemas NISQ requiere corrección de errores; el oráculo DESCIFRAR es complejo para cifrados tipo AES.
• Criptografía Post-Cuántica: La transición a esquemas basados en retículos o hashes es esencial.
• Práctica: Los simuladores Q# / Cirq demuestran en claves de 20 bits.

— Editorial Team