L’ordinateur quantique fait naître beaucoup d’espoirs et certaines inquiétudes. Ses capacités de calcul permettraient de résoudre certains problèmes plus rapidement que les ordinateurs actuels, y compris ceux sur lesquels se fonde la cryptographie moderne. Cela signifie-t-il que l’avènement de l’ordinateur quantique marquera la fin de la cryptographie telle qu’on la connaît aujourd’hui ? Si tel est le cas, quelles réponses la cryptographie post-quantique peut-elle apporter à ce changement de paradigme ?
L’ordinateur quantique devient peu à peu réalité
Le domaine de l’informatique quantique a connu de nombreuses avancées depuis les premiers travaux de recherche des années 80, notamment ceux de Richard Feynman, et l’apparition dans les années 90 des premiers algorithmes quantiques. Les premiers prototypes d’ordinateurs quantiques ont vu le jour dans les années 2000, et on constate depuis le début des années 2010 la multiplication d’annonces concrètes et encourageantes en la matière, comme la mise sur le marché par D-Wave Systems du premier ordinateur quantique commercial, la mise à disposition d’un ordinateur quantique dans le Cloud par IBM ou l’annonce récente par Google d’un nouveau processeur quantique. Au niveau européen, on peut également mentionner le lancement du simulateur quantique d’Atos l’année dernière, permettant de tester et d’optimiser des algorithmes quantiques en vue de leur utilisation en conditions réelles.
Comme nous l’expliquions dans un article précédent, la différence fondamentale entre un ordinateur classique et un ordinateur quantique vient de ce que l’ordinateur classique travaille sur une série de bits dont la valeur est soit égale à 1, soit à 0 tandis que l’ordinateur quantique travaille sur des qubits dont la valeur correspond à une superposition d’états. Il est parfois possible, pour un problème donné, d’écrire un algorithme quantique qui, tirant partie de cette superposition d’états et du principe d’intrication quantique, pourra le résoudre plus rapidement qu’un algorithme classique. Cette accélération quantique n’étant valable que pour un ensemble limité de problèmes pour lesquels un tel algorithme peut être écrit, il est vraisemblable que l’ordinateur quantique soit utilisé à l’avenir en complément de l’ordinateur classique, et qu’il ne sera pas amené à le remplacer totalement.
Les ordinateurs quantiques existants ont aujourd’hui une capacité très réduite. Le processeur quantique de Google est de 72-qubits, tandis qu’Intel a récemment annoncé le développement d’un processeur quantique de 49-qubits. A titre de comparaison, Google estime le nombre de qubits nécessaires pour une application réelle entre 1 et 10 millions. La difficulté principale de conception d’un ordinateur quantique de plus grande capacité réside dans le fait que toute interaction avec l’extérieur induit un phénomène de décohérence quantique qui ne permet pas de préserver l’intrication quantique nécessaire à son fonctionnement. Plus le nombre de qubits est élevé, plus il est difficile de maintenir cet état de cohérence. Cela nécessite l’isolation du système à très basse température. On peut estimer, au vu de l’évolution actuelle et des obstacles encore à franchir, être encore loin de toute application pratique des ordinateurs quantiques.
Les applications de la cryptographie classique
Pour saisir les implications que peuvent avoir les ordinateurs quantiques sur la cryptographie, il est important de bien comprendre les principes de la cryptographie classique et ses applications.
La cryptographie classique est composée de différents types d’algorithmes :
- La cryptographie asymétrique (ou à clé publique) utilisée pour établir un canal chiffré entre deux parties, pour l’authentification ou encore la signature électronique (exemples : Diffie-Hellmann, RSA, cryptographie sur les courbes elliptiques). La cryptographie asymétrique est généralement basée sur les problèmes de factorisation d’entiers ou du logarithme discret.
- La cryptographie symétrique (ou à clé secrète) utilisée pour chiffrer efficacement des données, notamment lorsqu’un canal chiffré a été établi au préalable par des algorithmes asymétriques (exemples : AES, DES). La cryptographie symétrique est basée sur les principes de diffusion et de confusion.
- Les fonctions de hachage utilisées pour vérifier l’intégrité d’un fichier ou des certificats électroniques (exemples : MD5, SHA-2). Les fonctions de hachage reposent sur les effets d’avalanche qui font que chaque bit de sortie dépend de chaque bit d’entrée.
En quoi l’ordinateur quantique change la donne
Parmi les algorithmes quantiques les plus connus et les plus anciens, on trouve l’algorithme de Shor permettant de factoriser des entiers ou de résoudre le problème du logarithme discret de façon efficace. Le jour où l’on pourra construire un ordinateur quantique suffisamment large pour traiter des grands nombres en utilisant l’algorithme de Shor, c’est toute la cryptographie à clé publique basée sur ces problèmes qui deviendrait caduque.
Un autre algorithme quantique notable est l’algorithme de Grover, qui permet d’inverser une fonction. Les applications de cet algorithme permettent de chercher des éléments dans une liste non-ordonnée ou dans une base de données non-structurée de façon efficace, ce qu’on peut imaginer être semblable à chercher une aiguille dans une meule de foin. L’algorithme de Grover permet ainsi d’accélérer la recherche d’une clé de chiffrement symétrique, sans pour autant remettre en cause les principes de la cryptographie à clé secrète.
Cryptographie post-quantique
La cryptographie post-quantique désigne des algorithmes cryptographiques qui ne se basent pas sur des problèmes pouvant être résolus plus rapidement par un ordinateur quantique. Ces algorithmes ne seront ainsi pas remis en cause par l’avènement d’un ordinateur quantique pour l’instant hypothétique. Elle ne doit pas être confondue avec la cryptographie quantique qui est une cryptographie exploitant les phénomènes quantiques pour parvenir à ses fins. Le challenge de la cryptographie post-quantique est double :
- Fonder une nouvelle cryptographie à clé publique qui ne se base pas sur les problèmes de factorisation d’entiers ou de logarithme discret ;
- Renforcer la cryptographie à clé secrète pour la rendre résistante aux capacités de recherche de clés des ordinateurs quantiques.
La cryptographie à clé publique devra être repensée entièrement, en employant de nouveaux systèmes cryptographiques basés par exemple sur les codes correcteurs d’erreurs ou les réseaux euclidiens. Si de nombreuses solutions théoriques existent, des recherches sont encore nécessaires pour les faire déboucher sur des solutions concrètes. Il existe plusieurs initiatives qui visent à stimuler la recherche dans ce domaine, comme la série de conférences PQCrypto qui ont lieu depuis plus de dix ans, ou encore le processus d’évaluation initié récemment par le NIST afin d’aboutir à une standardisation d’un ou plusieurs algorithmes cryptographiques post-quantiques.
La cryptographie à clé secrète est considérée robuste dans un monde post-quantique à condition que la longueur des clés utilisées soit suffisante. Le doublement de la taille des clés est une mesure de sécurité suffisante contre les ordinateurs quantiques. Par exemple, l’algorithme de chiffrement AES verra sa sécurité diminuée mais pourra encore être utilisé avec une taille de clé de 256 bits. La sécurité des protocoles basés sur ces algorithmes, comme Kerberos, ne devrait pas être fondamentalement remise en question.
Quant aux fonctions de hachage, les algorithmes quantiques ne semblent pas permettre de trouver plus rapidement que les algorithmes classiques des collisions qui les remettraient en cause. Les fonctions de hachage resteront donc sûres dans un monde post-quantique.
Une menace encore lointaine
La venue d’un ordinateur quantique d’une capacité suffisante pour poser une menace à la cryptographie classique est encore lointaine. D’ici là, on peut penser que les recherches en matière de cryptographie post-quantique seront bien avancées, et que le changement des constructions cryptographiques pourra être largement anticipé.
