Introduction

Même si vous n’êtes pas cryptologues, il est fortement probable qui vous ayez entendu parlé de chiffrement post-quantique et de problèmes de confidentialité/intégrité liés à l’informatique quantique. Toutefois, il n’est peut-être pas encore clair de savoir dans quel context nous sommes actuellement et est-ce qu’il y a un ou des dangers immédiats, et de quel(s) danger(s) on parle ?

Dans cet article, nous allons essayer de répondre à ces questions en traitant de :

  • Ce qu’est l’informatique quantique, et l’histoire de la liée à la cryptographie quantique
  • Quels sont les algorithmes qui seraient touchés ?
  • Comment pallier le problème et les types d’algorithmes considérés post-quantiques par le NIST
  • Les avancées jusqu’à présent

Histoire & Desription

Dès les années 1980, l’idée que les ordinateurs utilisant la mécanique quantique pourraient dépasser les performances des ordinateurs classiques a émergé. Cette avancée permettrait de résoudre en heures des problèmes prenant des siècles aux ordinateurs classiques.

La décennie suivante, dans les années 90, après que Peter Shor ait montré qu’un ordinateur quantique pourrait briser certains chiffrement à clé publique, la recherche s’est orientée vers la création d’une cryptographie résistante aux ordinateurs quantiques : la cryptographie post-quantique.

Les deux principes clés de la mécanique quantique qui sont exploités pour l’informatique quantique sont la superposition et l’entrelacement (ou intrication quantique) :

  1. Superposition : Un qubit, l’unité de base de l’information quantique, peut exister simultanément dans un état de 0 et de 1, contrairement à un bit classique qui est soit 0 soit 1. Plus précisément une particule est représentée par un vecteur dans un espace vectoriel, et ce vecteur admet une décomposition en une combinaison linéaire de vecteurs générateurs selon une base donnée. En terme plus simple, la representation des états d’une particule est loin d’être simplement binaire (ce qui permet de faire passer bien plus d’informations avec une seule unité d’information).

  2. Entrelacement : Des qubits peuvent être entrelacés de manière que l’état de l’un dépend de l’état de l’autre, même s’ils sont séparés par de grandes distances. Cela permet une coordination et une communication à une échelle que les ordinateurs classiques ne peuvent pas atteindre, augmentant l’efficacité du traitement des informations.

Ces propriétés uniques permettent aux ordinateurs quantiques de parcourir et de traiter un vaste espace de solutions possibles beaucoup plus rapidement que les ordinateurs classiques, rendant possible la résolution de problèmes jusqu’alors considérés comme extrêmement difficiles ou impossibles à résoudre en temps raisonnable, comme la factorisation de grands nombres ou le logarithme discret (des exemples d’algorithmes seront spécifiés dans la suite de l’article).

Les conséquences de l’informatique quantique au niveau de la cryptographie

Avec l’avènement potentiel d’ordinateurs quantiques stables et dotés d’un nombre suffisant de qubits, les algorithmes principalement affectés seront ceux de la cryptographie à clé publique, c’est-à-dire les chiffrements asymétriques, (présent par exemple dans TLS qui permet de naviguer sur internet sans que nos informations privées ne soit divulguées à qui le veut). En revanche, les chiffrements symétriques, tels que AES, subiront moins les conséquences. En effet, même si l’algorithme de Grover pourrait théoriquement optimiser une attaque par bruteforce grâce aux propriétés quantiques, le simple fait de doubler la longueur de la clé de chiffrement permet à AES de conserver une robustesse significative. (à noter que cette attaque concerne principalement le mode ECB, déjà déconseillé).

Du côté des chiffrements asymétriques, la situation est tout autre. Des systèmes tels que RSA, la cryptographie sur courbes elliptiques (ECC), et les protocoles d’échange de clés basés sur Diffie-Hellman deviendront obsolètes. Les fondements mathématiques assurant leur sécurité peuvent être compromis aisément en exploitant les capacités des ordinateurs quantiques.

Typiquement, la cryptographie sur les courbes elliptiques serait vulnérable face à des ordinateurs quantiques assez puissants pour exécuter l’algorithme de Shor.

Spoiler alerte, ici il y aura un tout petit peu de technique mais non nécéssaire pour comprendre l’essence du texte

Toute la cryptographie basée sur les courbes elliptiques, (celle basée sur le problème du logarithme discret sur courbes elliptique : ECDLP), repose sur la difficulté de trouver un entier secret n étant donné le point 𝑄 = [n]𝑃 = 𝑃 + ... + 𝑃 avec 𝑃 le point générateur d’une courbe elliptique.

Sur un ordinateur quantique capable, (ie. un ordinateur quantique qui possède assez de qubit et qui soit suffisament stable), l’algorithme de Shor trouverait rapidement une période (t,r) de la fonction (a,b) -> [a]𝑃 − [b]𝑄. Avec cette période qui satisfait [a − bn]𝑃 = [a]𝑃 − [b]𝑄 = [a+t]𝑃 − [b+r]𝑄 = [a+t−(b+r)n]𝑃 pour tout a et b y compris zéro, de sorte que 0 ≡ t−rn (mod l), où l est l’ordre de 𝑃, à partir duquel nous pouvons récupérer triviallement n ≡ r⁻¹t (mod l).

Le nombre de qubits, le nombre de portes logiques, et le temps d’exécution pour calculer ceci est une petite fonction polynomiale qui prend en paramètre le nombre de bits de l’ordre l, qui est ~256 dans une suite cryptographique classique.

La majorité du circuit quantique serait consacré au calcul de la multiplication scalaire (ie. un calcul du style R = [a]B avec R et B des points sur la courbe elliptique et a un scalaire/entier), avec une complexité égale à un ordinateur classique. La vraie plus value d’un système quantique se retrouve dans la transformation de Fourier quantique (qui permet de trouver la période citée précédemment : (t,r)).

L’algorithme de Shor peut être aussi utilisé pour factoriser la valeur publique du module d’un système RSA (ie. trouver p et q tel que n est le module et n = p * q). (Ce qui est le problème mathématique sur lequel RSA se base pour être sécurisé).

Quant à l’échange de clé Diffie-Hellman basé sur le logarithme discret sur un corps fini (ie. simplement trouver n tel que a,b,p ∈ ℤ, p premier et b = a^n % p, en ne connaissant que a, b et p), l’algorithme de Shor est tout aussi efficace ici que sur RSA et la cryptographie sur les courbes elliptiques.

Les solutions apportées jusqu’à présent

En 2016, le NIST a initié un processus pour solliciter, évaluer et standardiser un ou plusieurs algorithmes cryptographiques à clé publique résistants au quantique.

Parmis les schémas cryptographiques qui sont envisagés, voici les 6 qui sont a priori post-quantique d’après le NIST :

(“a priori” car il n’y a pas de preuve formelle comme quoi un système de chiffrement est robuste à 100%, c’est pourquoi il y a énormément de recherche en cryptologie pour conforter l’idée de la robustesse des systèmes cryptographiques)

  • Cryptographie basée sur les réseaux euclidiens : Exploite la difficulté de certains problèmes mathématiques comme l’apprentissage avec erreurs, offrant une résistance potentielle contre les ordinateurs quantiques. Des variantes comme NTRU sont étudiées depuis des années pour leur sécurité sans qu’aucune faille majeure ne soit trouvée. (Exemples aussi prometteurs : Kyber, Dilithium)

  • Cryptographie multivariée : Se base sur la complexité de résoudre des systèmes d’équations multivariées, proposant des schémas de signature sécurisés contre les attaques quantiques. Le schéma Rainbow est un exemple notable, bien que des tentatives antérieures de chiffrement aient échouées.

  • Cryptographie basée sur les hash : Inclut des signatures numériques résistantes aux quantiques, limitées par le nombre de signatures possibles par clé. Les signatures de Merkle et XMSS sont des exemples, avec XMSS étant normalisé dans le RFC 8391.

  • Cryptographie basée sur les codes : Utilise des codes de correction d’erreurs pour le chiffrement et la signature, avec le schéma de McEliece résistant à l’examen pendant plus de 40 ans comme référence principale. (À noter toutefois qu’en cherchant à réduire la taille de la clé, les chercheurs ont montré des faiblesses sur ces variants de ce système).

  • Cryptographie basée sur les isogénies : Sa sécurité repose sur les propriétés complexes des graphes d’isogénies de courbes elliptiques, offrant des alternatives à Diffie–Hellman résistantes aux attaques quantiques. SIDH/SIKE, bien que cassé en 2022 (attaque ensuite un peu plus généralisée, cocorico c’est un français !), est un exemple de cette approche. (Exemple prometteur : CSIDH)

  • Résistance quantique de la cryptographie à clé symétrique : AES et d’autres systèmes à clé symétrique, avec des tailles de clé adéquates, sont jugés sécurisés contre les attaques quantiques. Les systèmes de gestion de clés utilisant la cryptographie symétrique, comme Kerberos, offrent une solution de sécurité efficace et déjà largement déployée.

Ces solutions, en cours de développement et de normalisation, visent à offrir une résistance solide non seulement contre les ordinateurs classiques mais aussi contre les futurs ordinateurs quantiques, assurant ainsi la confidentialité et l’intégrité des communications numériques dans le futur.

Il y a par ailleurs des événements très intéréssants regroupant les spécialistes du domaine (et pas que) comme PKI Consortium ou PQCrypto qui proposent des conférences à propos des avancées tant bien en cryptographie qu’en cryptanalyse, en proposant des optimisations ainsi que des attaques sur des systèmes cryptographiques post-quantiques.

Conclusion

La cryptographie sur les algorithmes asymétrique n’est actuellement pas vulnérable aux ordinateurs quantiques car il n’existe pas d’ordinateurs quantiques assez grands et fiables pour être significatifs. Toutefois, la question de savoir quand un ordinateur quantique à grande échelle sera construit est complexe.

Le danger aujourd’hui concerne principalement la confidentialité à long terme des documents et des conversations face à l’analyse cryptographique quantique future : les accords de clé TLS avec Diffie–Hellman sur courbes elliptiques, par exemple, pourraient être attaqués avec l’algorithme de Shor, tout comme Diffie–Hellman (sur un corps fini), permettant le déchiffrement rétroactif des sessions TLS. (L’effacement des clés de session par toutes les parties impliquées n’est d’aucune utilité si l’adversaire peut casser la cryptographie d’accord de clé).

Pour l’authentification et la signature, par exemple les signatures Ed25519, le danger n’est pas si grand tant qu’un plan de mise à niveau pour changer le schéma de signature d’ici à ce que les ordinateurs quantiques capables existent. (ie. des ordinateurs quantiques qui possèdent assez de qubit et qu’ils soient stables pour pouvoir casser des systèmes cryptographiques robustes sur ordinateur classique).

En somme, bien que le danger immédiat soit limité, la préparation proactive est indispensable pour garantir la sécurité des informations numériques à l’avenir.