Déchiffrer l’indéchiffrable
Par Yan-Éric Jérôme, étudiant au baccalauréat en informatique à l’UdeS et stagiaire à l’AlgoLab à l’automne 2023.
Chaque jour, une quantité monstrueuse d’information circule à travers Internet, connectant des utilisateurs d’un bout à l’autre du globe… et exposant des informations sensibles à des entités malveillantes. Heureusement, il existe plusieurs techniques visant à protéger ces informations. Le chiffrement RSA est l’un des algorithmes les plus répandus pour assurer la confidentialité des données partagées. Grâce à une technique utilisant une paire de clés (chaînes de caractères) publique et privée, l’information est chiffrée de telle sorte que seul le destinataire peut décoder l’information. Toutefois, peut-on réellement garantir que l’information envoyée est à l’abri des pirates informatiques?
Il est en effet possible de déchiffrer ces chiffrements par force brute, en utilisant des techniques de factorisation, mais cela ne veut pas pour autant dire que vos données ne sont pas en sécurité! À ce jour, les plus grands nombres factorisés par ordinateur sont de l’ordre de quelques centaines de bits (voir Figure 1), tandis que la recommandation pour le chiffrement RSA se situe à 2048 bits, soit 617 chiffres! Et bien que les ordinateurs deviennent de plus en plus puissants, les ressources computationnelles requises par les meilleurs algorithmes classiques croissent exponentiellement avec la taille du nombre à factoriser, tel que présenté à la Figure 2.
La menace quantique
Toutefois, l’informatique quantique présente un fort potentiel pour la factorisation de tels nombres. En 1994, Peter Shor remarque un parallèle entre le problème de factorisation et celui de la recherche d’ordre, un problème d’arithmétique modulaire qui permet d’exprimer certaines caractéristiques d’un nombre comme une fonction périodique. Il parvient à mettre au point un algorithme qui utilise les propriétés des systèmes quantiques afin de rapidement extraire les caractéristiques recherchées et ainsi déterminer les facteurs premiers d’un nombre. La découverte de cet algorithme a joué un rôle pivot dans l’engouement et l’intérêt de la communauté scientifique pour le calcul quantique puisqu’il offre un gain exponentiel de performance sur les meilleurs algorithmes classiques, et ce pour un problème présentant un grand intérêt économique.
Malgré l’aspect révolutionnaire de l’algorithme de Shor, toute implémentation concrète de cette technique dans un avenir proche semble hors de portée. Les ressources requises en termes de qubits excèdent largement les capacités actuelles des meilleurs ordinateurs quantiques, et ces derniers sont beaucoup trop sensibles au bruit et à la décohérence pour effectuer le nombre d’opérations de base exigées par l’algorithme.
Les alternatives d’aujourd’hui
Considérant les limitations des systèmes quantiques actuels, de nombreux groupes de recherche tentent de développer des alternatives visant à réduire les ressources requises par l’algorithme de Shor. Dans leur papier publié en 2021, Unathi Skosana et Mark Tame établissent un nouveau record en factorisant le nombre 21 sur un vrai ordinateur quantique. Malgré le fait qu’il s’agisse d’un petit nombre, les auteurs ont tout de même dû simplifier et adapter l’algorithme de Shor à un point tel que leur solution ne peut factoriser nul autre nombre.
Au courant de mon stage au sein de l’équipe de l’Algolab, j’ai moi-même eu l’occasion de concevoir et mettre à l’épreuve mon propre circuit pour la factorisation du nombre 33 (quelle ambition!). Malgré des résultats encourageants sur simulateur, l’expérience sur ordinateur quantique s’est conclue en échec. La Figure 3illustre le problème : alors qu’on parvient à mettre en évidence les états-solutions sur simulateur (résultats de simulation en bleu, les bandes « 3 » et « 13 » étant la solution cherchée et « 0 » la solution triviale), la distribution des mesures sur un système quantique ne s’apparente nullement aux résultats attendus (résultats en rouge). Ici, les valeurs associées à chaque bande ne représentent pas les facteurs, mais plutôt des valeurs intermédiaires qui permettent de calculer ceux-ci grâce à un algorithme classique.
Et demain?
Malgré les limites évidentes des systèmes quantiques actuels, ceux-ci présentent une certaine menace à moyen terme pour les méthodes de chiffrement couramment utilisées. Toutefois, de nouvelles techniques de chiffrement réputées à l’épreuve du calcul quantique ont été développées, et les efforts de recherche continuent dans cette direction. Vous pouvez donc dormir sur vos deux oreilles; ce n’est pas demain que la quantique dévoilera vos secrets!