Force brute quantique en cryptanalyse

Attaque par force brute quantique sur le chiffrement

Une attaque par recherche exhaustive de clé est appliquée lorsque l'espace des textes clairs possibles est nettement plus petit que l'espace complet des caractères. Ève intercepte un texte chiffré d'Alice à Bob et implémente deux fonctions : DÉCHIFFRER(clé, texte_chiffré) pour le déchiffrement et ESTTEXTE_CLAIR(texte) pour vérifier si le texte appartient à l'ensemble des textes clairs valides. Si le chiffrement est basé sur des blocs, DÉCHIFFRER fonctionne sur des blocs, et ESTTEXTE_CLAIR accumule les résultats.

Le pseudocode de l'attaque est simple :

pour chaque clé
    texte = DÉCHIFFRER(clé, texte_chiffré)
    si ESTTEXTE_CLAIR(texte) == 0 alors retourner (clé,texte)
fin pour

Les critères d'ESTTEXTE_CLAIR utilisent des statistiques de caractères, des combinaisons ou des heuristiques sans bases de données — vérifications de fréquence, d'entropie ou de modèles linguistiques.

Théorie de l'information pour l'évaluation du succès

Pour un chiffrement monoalphabétique, nous estimons la probabilité d'un faux positif :

• LONGUEUR(texte_clair) — longueur en bits
• LONGUEUR(clé) — longueur de la clé en bits
• LONGUEUR(texte_chiffré) — longueur du texte chiffré en bits
• ENTROPIE(texte_clair) — entropie de Shannon du texte clair

Conditions :

• LONGUEUR(texte_clair) ≤ LONGUEUR(texte_chiffré)
• Probabilité de passage faux : 2^-(LONGUEUR(texte_clair) - ENTROPIE(texte_clair))
• Si LONGUEUR(texte_clair) - ENTROPIE(texte_clair) > LONGUEUR(clé), la clé est déterminée de manière unique

Pour les algorithmes préservant la longueur : lorsque LONGUEUR(texte_chiffré) - ENTROPIE(texte_clair) ≥ LONGUEUR(clé), l'attaque est garantie de trouver la clé.

Approche quantique de la force brute

L'informatique quantique repose sur la superposition et l'intrication des qubits. Un registre de N qubits intriqués équivaut à 2^N états classiques. L'arithmétique (addition, multiplication, décalages) est implémentée avec des portes quantiques — transformations d'opérateurs unitaires.

Toute fonction classique sur un registre de clés peut être transformée en un opérateur unitaire U(K), où K est une superposition de toutes les clés.

Algorithme de Grover pour la recherche de clé

Étapes de l'attaque quantique :

• Initialiser un registre K de longueur LONGUEUR(clé) dans une superposition uniforme de toutes les clés : |K⟩ = (1/√2^{LONGUEUR(clé)}) Σ |clé⟩
• Appliquer l'oracle U(K) = DÉCHIFFRER(K, texte_chiffré), puis ESTTEXTE_CLAIR(U(K)) : la phase est inversée pour les états avec ESTTEXTE_CLAIR == 0
• Amplifier l'amplitude de l'état cible en utilisant l'algorithme de Grover : π/4 * √2^{LONGUEUR(clé)} itérations avec des opérateurs de diffusion et l'oracle
• Mesurer le registre K — il s'effondre sur la clé correcte avec une probabilité ~1

L'oracle nécessite d'implémenter DÉCHIFFRER et ESTTEXTE_CLAIR comme des circuits quantiques réversibles. Pour les chiffrements par blocs — traiter par blocs avec des qubits auxiliaires.

// Pseudocode de circuit quantique (style Q#)
opération ForceBrute(keyReg : Qubit[], texte_chiffré : String) : (Int, String) {
    // Appliquer H à tous les qubits pour la superposition
    AppliquerÀChacun(H, keyReg);
    // Oracle : inversion de phase si ESTTEXTE_CLAIR(DÉCHIFFRER(keyReg, texte_chiffré)) == 0
    Oracle(keyReg, texte_chiffré);
    // Itérations de Grover
    pour itération dans 0 .. ItérationsGrover() - 1 {
        DiffusionGrover(keyReg);
        Oracle(keyReg, texte_chiffré);
    }
    // Mesure
    soit clé = MesurerClé(keyReg);
    retourner (0, DÉCHIFFRER(clé, texte_chiffré));
}

Accélération quadratique : O(√2^{LONGUEUR(clé)}) au lieu de O(2^{LONGUEUR(clé)}).

Points clés à retenir

• Classique vs Quantique : Forcer une clé de 128 bits sur un CPU — 10^38 opérations ; sur un ordinateur quantique — 10^19.
• Condition de succès : Redondance du texte clair (LONGUEUR - ENTROPIE) > LONGUEUR(clé)/2 pour une attaque pratique.
• Limitations : Le bruit dans les systèmes NISQ nécessite une correction d'erreur ; l'oracle DÉCHIFFRER est complexe pour les chiffrements de type AES.
• Cryptographie post-quantique : La transition vers des schémas basés sur les réseaux ou les fonctions de hachage est essentielle.
• Pratique : Les simulateurs Q# / Cirq démontrent sur des clés de 20 bits.

— Editorial Team