Le cauchemar crypto-quantique des banquiers
Thème récurrent des romans comme de l’actualité récente, l’espionnage repose non seulement sur l’interception de messages secrets mais surtout sur leur décryptage. La plupart de nos échanges électroniques, de nos transactions bancaires ou de nos communications sont protégés à l’heure actuelle par un dispositif de cryptage inventé en 1977 par Ronald Rivest, Adi Shamir et Leonard Adleman (RSA) et qui s’avère particulièrement efficace. La physique quantique propose des méthodes susceptibles de casser cette précieuse protection mais la réalisation technique pose des problèmes encore insurmontables à cause de la fragilité des systèmes expérimentaux. De nombreuses pistes sont régulièrement explorées et, il y a quelques semaines, Zi Cai et Thomas Barthel de l’Université de Munich proposaient une analyse théorique laissant espérer des progrès prochains [1]. Malgré les effets d’annonce, il ne faut cependant pas espérer un bouleversement rapide de l’informatique ; et les conséquences pour l’utilisation bureautique resteront sans doute marginales.
Des bits quantiques
L’une des propriétés les plus surprenantes de la mécanique quantique est la superposition d’états : un système quantique peut être simultanément dans deux états différents, comme s’il était doué d’une forme d’ubiquité. Cette propriété est souvent illustrée par la mascotte de la mécanique quantique, le chat de Schrödinger : enfermé dans une boîte avec un dispositif ayant une chance sur deux de le tuer, le chat est à la fois mort et vivant. Lorsqu’il évoque cette expérience de pensée en 1935, Erwin Schrödinger voulait montrer que le raisonnement quantique ne s’applique pas à l’échelle macroscopique en prenant une expérience absurde [2] : tout le monde sait bien que dans une telle situation, le chat est ou mort, ou vivant. Cependant, à l’échelle de particules suffisamment petites ou de systèmes suffisamment bien contrôlés (et ces systèmes sont de plus en plus grands [3]), la superposition d’états garde tout son sens et transforme effectivement le OU classique (mort OU vivant) en un ET quantique (mort ET vivant).
Ce passage du ET quantique au OU classique a lieu au moment de la mesure. Dans l’exemple d’un chat quantique, tant que la boîte est fermée, l’animal est à la fois mort et vivant ; au moment où la boîte s’ouvre, le chat n’est plus que vivant ou mort. La prise d’information sur l’état du système force la superposition d’états à se réduire à un seul des états possibles ; cet effondrement du système est fondamentalement imprévisible : seule la probabilité de trouver tel ou tel état peut être estimée avant la mesure. Il ne s’agit pas d’une limite de notre compréhension, mais bien d’une limitation intrinsèque : l’état final du système n’est simplement pas fixé avant son interaction avec l’extérieur.
Cette propriété est susceptible de révolutionner l’informatique dans les années à venir. Nos systèmes actuels reposent sur une logique binaire : les ordinateurs utilisent des courants électriques, des mémoires magnétiques ou des impulsions optiques qui se traduisent en 0 (pas de courant, aimantation « vers le bas », pas de lumière) et en 1 (passage du courant, aimantation « vers le haut », présence de lumière). Un ordinateur est donc une machine qui manipule des « blocs » d’informations appelés bits et qui peuvent être dans deux états : soit 0, soit 1. La réalisation d'un calcul, l’enregistrement de données ou l’affichage d’une image à l’écran résulte d’algorithmes, c’est-à-dire d’une suite d’opérations, utilisant ces bits (si tel bit vaut 0 et tel bit vaut 1, alors il faut attribuer à tel bit la valeur 1, etc. )
L'idée proposée par Benjamin Schumacher en 1995 [4] est d'appliquer la notion de superposition d'états à l'informatique en considérant non plus des bits classiques restreints aux états 0 ou 1 mais des bits quantiques (qubits, prononcer « kyou – bit » /ˈkjuːbɪt/) susceptibles d'être configurés dans n'importe quelle superposition de ces états. Tout comme le chat est soit mort, soit vivant lorsqu'on ouvre la boîte, le qubit prend soit la valeur 0 soit la valeur 1 lorsqu'on le mesure sans que le résultat de la mesure ne soit fixé a priori (voir figure 1).
Figure 1 : À gauche : un bit classique est à chaque instant dans un de ses deux états, 0 ou 1. À droite : un qubit peut être représenté par une sphère, dont les pôles sont les états 0 et 1. L’état du qubit est alors représenté par une position à la surface de la sphère et la probabilité de trouver 0 ou 1 lors d’une mesure dépend de la distance aux pôles. En A, le qubit est dans l’état 1 et la mesure donnera 1 de manière certaine. L’état B est plus proche de l’état 1 que de l’état 0 ; une mesure aura 75 % de chance de donner 1 et 25 % de chance de donner 0. En C, une mesura aura 50 % de chance de donner l’une ou l’autre valeur. En D, très proche de l’état 0, une mesura aura 99 % de chance de donner 0 mais néanmoins 1 % de chances de donner 1.
Tout comme son homologue classique, un ordinateur quantique applique des algorithmes : inverse l'état de tel qubit, combine l'état de tel et tel qubit... Il peut ainsi reproduire non seulement tous les algorithmes d'un ordinateur classique mais aussi certains algorithmes spécifiques, qui n'ont aucun équivalent non quantique. Toute la force de l'informatique quantique vient de la capacité des qubits à être dans plusieurs états simultanément : si un qubit peut être à la fois dans l’état 0 et dans l’état 1, deux qubits peuvent être simultanément dans les états (0,0), (1,0), (0,1) et (1,1), etc. : le nombre d’états coexistants simultanément explose avec le nombre de qubits. En les manipulant convenablement, on peut parvenir à calculer d’un seul coup le résultat d’un calcul pour tous les nombres possibles. On parle alors de « parallélisme quantique », une approche qui ouvre la porte à une nouvelle génération de méthodes de calculs qui, s’ils n’auront que peu de retombées pour l’usage quotidien de l’utilisateur moyen, peuvent révolutionner la façon de concevoir l’informatique.
Un des premiers algorithmes quantiques a été inventé par David Deutsch et Richard Jozsa en 1992 [5]. Il présente le double intérêt de mettre en lumière le caractère bizarroïde des algorithmes quantiques et de pouvoir être illustré sur un exemple simple : en combien d’opérations peut-on savoir si une pièce de monnaie possède deux côtés identiques ? Un algorithme classique nécessite au minimum deux opérations : regarder la première face puis regarder l’autre. Deutsch et Jozsa ont montré qu’un ordinateur quantique n’aurait besoin que d’une seule opération pour comparer les deux côtés simultanément et trouver si la pièce est truquée ou non. L’algorithme ne permet cependant pas de savoir si les côtés sont tous deux piles ou tout deux faces, seulement s’ils sont identiques ou non ; en ce sens, il ne fournit pas plus d’informations qu’un algorithme classique, il fournit des informations différentes.
L’algorithme de Deutsch, si ses applications restent limitées, a largement servi d’inspiration aux deux algorithmes les plus puissants que l’on connaisse actuellement : l’algorithme de Grover [6] et l’algorithme de Shor [7]. L’algorithme de Grover est une méthode de recherche qui permet de trouver un résultat dans une liste désordonnée (par exemple retrouver à qui appartient un numéro de téléphone dans un annuaire) beaucoup plus vite que n’importe quel algorithme classique. Proposé en 1994 par Peter Shor, l’algorithme du même nom a propulsé l’informatique quantique, révolutionné le domaine et donné des sueurs froides à tous les cryptologues de la planète. Son usage peut sembler anodin : il ne sert qu’à factoriser un nombre en un produit de nombres premiers, ces nombres qui n’ont pas d’autres diviseurs qu’eux-mêmes. Par exemple, il permet de trouver que 42 s’écrit 2x3x7. Cependant, s’il était utilisé, il pourrait décoder presque instantanément la plupart des échanges cryptés de la planète, que ce soit ceux des transactions bancaires, des communications militaires ou messages électroniques !
Le cryptage RSA et l’algorithme de Shor
À l’heure actuelle, la protection de tous ces échanges repose sur une méthode de cryptage extrêmement astucieuse inventée en 1977 par Ronald Rivest, Adi Shamir et Leonard Adleman et nommée RSA en leur honneur. Le cryptage RSA permet à la fois de rendre une communication incompréhensible pour quiconque à l’exception de son destinataire et de prouver l’authenticité de l’origine d’un message. Il est à l’œuvre en permanence dans notre quotidien : nos cartes bleues l’utilisent pour être reconnues par les lecteurs de cartes et nos navigateurs web s’en servent pour toutes les transactions sécurisées HTTPS.
Pour illustrer son fonctionnement, il est coutume d’imaginer une scène faisant intervenir deux personnages fictifs, Alice et Bob [8]. Bob veut communiquer avec Alice de manière sécurisée en utilisant le cryptage RSA. Il commence par choisir deux nombres premiers et les multiplie entre eux. À partir du produit de ces nombres, et de quelques opérations de calculs, il obtient deux nombres : un qu’il garde secret (la clé privée) et un qu’il communique à tout le monde et en particulier à Alice (la clé publique). Avec chacun de ces nombres, on peut crypter ou décrypter un message (voir figure 2 pour un exemple simple).
Figure 2 : Comment un nombre peut-il crypter un message ? Un exemple simple, pour fixer les idées. On convertit le texte en nombres (A=1, B=2 etc.) puis on transforme chacun des nombres à l’aide d’une clé (ici, on additionne la clé 2542691088) pour obtenir un message crypté. L’exemple donné ici (cryptage par décalage) est symétrique : la clé de cryptage permet également de décrypter le message.
Le système RSA est asymétrique : la clé qui sert à crypter le message ne permet pas de le décrypter. Ainsi, si Alice veut transmettre un message à Bob, elle utilise la clé publique qu’elle a reçue et, une fois le message codé, elle-même ne peut plus le décoder. Seule la clé privée, dont Bob est seul détenteur, peut réaliser l’opération inverse. À l’inverse, si Bob veut prouver son identité, il lui suffit de transmettre un message codé par sa clé privée : la clé publique ne décode que la clé de Bob et aucune autre ; si elle décode un message, c’est que ce message a bien été codé par la clé privée correspondante (voir figure 3).
Figure 3 : Le cryptage asymétrique génère une clé publique et une clé privée. À gauche : La clé publique qui sert à crypter un message est incapable de le décrypter ; seul le propriétaire de la clé privée peut donc décoder un message émis avec la clé publique. À droite : la clé publique ne peut décoder que ce qui a été codé avec la clé privée associée. Le cryptage RSA permet donc d’authentifier l’origine d’un message : si on peut le décoder avec la clé publique, c’est nécessairement qu’il a été émis avec la bonne clé privée, qu’une seule personne possède.
Pour casser la protection RSA, il faut parvenir à trouver la clé privée à partir de la clé publique ; c’est-à-dire à trouver quels sont les deux nombres premiers initialement utilisés pour générer les clés. Mais factoriser un nombre quelconque en deux nombres premiers est un problème difficile et le temps de calcul augmente exponentiellement avec le temps. Le record date de 2010 : une équipe de chercheur est parvenue à casser un code de 232 chiffres en deux ans environ, avec un matériel de pointe ; pour un ordinateur standard, le calcul est estimé à 1 500 ans [9]. Actuellement, les codes utilisés représentent des nombres de plus de 300 chiffres et constituent encore des forteresses imprenables. Pour en tester la fiabilité, l’entreprise RSA Security d’ailleurs avait mis en place de 1991 à 2007 une compétition mathématique, le RSA Factoring Challenge : la première équipe à trouver la factorisation de nombres de plus en plus longs se voyait attribuée des prix de plus en plus élevés, jusqu’à 200 000 $. Malgré la motivation et les multiples tentatives, la plupart des codes ont résisté et résistent toujours.
On pourrait donc croire qu’il suffirait de trouver des nombres premiers de plus en plus longs pour générer des clés de plus en plus complexes, garder une longueur d’avance sur la capacité de calculs des ordinateurs et assurer la fiabilité des transferts de donnés. C’est sans compter l’algorithme de Shor qui, en utilisant la puissance du parallélisme quantique peut factoriser des grands nombres infiniment plus vite qu’un ordinateur classique ! Pire encore, le temps de calcul n’augmente pas exponentiellement avec la taille de la clé : impossible d’espérer trouver la sécurité dans l’allongement des nombres utilisés ! L’algorithme de Shor annonce donc la mort programmée du cryptage RSA.
De la théorie à la pratique
Si les cryptologues de la planète dorment encore tranquilles (et nous avec), c’est que la mise en œuvre de l’algorithme de Shor se heurte à des problèmes techniques jusqu’à maintenant insurmontables. La manipulation de qubits est en effet particulièrement difficile : puisque toute mesure les projette soit sur l’état 0, soit sur l’état 1, il faut parvenir à les manipuler sans jamais les observer en cours de calcul sous peine de perdre la superposition des états. Pour reprendre l’analogie du chat de Schrödinger, si on entend miauler le chat, on est renseigné sur son état avant même d’ouvrir la boîte. De la même manière, toute interaction non contrôlée avec les qubits fournit des renseignements sur leurs états et fait disparaître la superposition ; cette dissipation s’appelle la décohérence et représente le plus grand obstacle à la réalisation d’un ordinateur quantique. Par ailleurs, il faut parvenir à manipuler tous les qubits simultanément : le parallélisme quantique repose sur une superposition d’états de plusieurs qubits à la fois et ne peut être obtenu en travaillant sur chacun des qubits séparément.
En 2001, une équipe d’IBM aux États Unis est parvenue à manipuler 7 qubits pour appliquer l’algorithme de Shor au nombre 15 et le décomposer en 3x5 [10] ; à ce jour, c’est le calcul le plus complexe qu’on a pu réaliser. S’il ne présente pas un grand intérêt mathématique ni informatique (pour des petits nombres, l’algorithme de Shor est moins efficace qu’un algorithme classique !), il a néanmoins le mérite de prouver le fonctionnement de la théorie.
Ainsi, pour tirer parti de la nature quantique des qubits et utiliser l’algorithme de Shor de manière efficace, il est indispensable de réduire au maximum l’influence du monde extérieur sur le système ou de rendre le système plus robuste face à ces interactions. C’est la voie qu’explorent de nombreuses équipes de recherche : certaines tentent d’imaginer des dispositifs de stockage ou de contrôle de mémoires quantiques, d’autres espèrent trouver des systèmes protégés contre la décohérence. Le mois dernier, une équipe allemande publiait dans la prestigieuse revue Physical Review Letters une analyse théorique [1] montrant qu’en exploitant les interactions entre les particules d’un système, on peut réduire l’effet des interactions externes et donc la décohérence. Malgré de très nombreuses propositions analogues, le passage à la réalisation pratique est néanmoins loin d’être évident, à tel point que certains se demandent si l’ordinateur quantique verra jamais le jour.
Il faut cependant noter que la physique quantique est déjà à l’œuvre dans nos ordinateurs : les composants électroniques (transistors, microprocesseur…) ou optiques (diode laser pour lire les CD…) exploitent des propriétés quantiques et ne peuvent être compris par la physique classique. Enfin, paradoxalement, la physique quantique offre des alternatives au cryptage RSA qui sont de plus en plus étudiées. Ainsi, l’entreprise IDQuantique propose un dispositif quantique monté sur clé USB [11] pour générer des nombres aléatoires sans aucun biais et assurer la sécurité de certains protocoles. Plus généralement, la cryptographie quantique utilise la fragilité des qubits, qui bascule dans l’état 0 ou l’état 1 à la moindre mesure, pour s’assurer que la transmission n’a pas été espionnée. Si la transmission est bien libre, alors il n’est pas nécessaire d’utiliser un cryptage sophistiqué, puisque seul le destinataire a reçu le message. Si la transmission a été interceptée, il suffit de ne pas dire quelle partie du message contient les informations pour éviter toute fuite – et retenter la communication plus tard en espérant que l’espion sera parti. Cette technique a déjà été mise en œuvre à de nombreuses reprises ; une communication quantique a même été échangée entre Lausanne et Genève, à 70 kilomètres de distance !
Si l’ordinateur quantique reste un rêve à l’heure actuelle, le domaine de l’informatique quantique est particulièrement actif, comme en témoigne le nombre de publications. Des alternatives au cryptage RSA [12] susceptibles de résister à l’algorithme de Shor existent et assureront sans doute la sécurité des communications à l’avenir. Néanmoins, si la période de transition risque néanmoins d’être turbulente, elle impactera moins les ordinateurs de salon que les télécommunications.
Références
[1] Zi Cai and Thomas Barthel, Algebraic versus Exponential Decoherence in Dissipative Many-Particle Systems, PRL 111, 150403 (2013)
[2] « We never experiments with single electrons, atoms or small molecules…In thought experiments we assume that we do. It always results in ridiculous consequences… » (Litt. “Nous ne réalisons jamais d’expériences avec des électrons, des atomes ou des molécules uniques. Dans les expériences de pensée, nous nous permettons de le faire. Cela entraîne toujours des conséquences ridicules…”) (Schrödinger, Are there quantum jumps?, British Journal for the Philosophy of Sciences, 3, 233 1952)
[3] Le prix Nobel de 2012 attribué à Serge Haroche et David Wineland récompense précisément la réalisation expérimentale de superpositions d’états dans des systèmes presque macroscopiques !
[4] Benjamin Schumacher, Quantum coding, PRA 51(4), 2738-2747
[5] David Deutsch and Richard Jozsa, Rapid Solution of Problems by Quantum Computation, Proceedings: Mathematical and Physical Sciences, Vol. 439, No. 1907 (Dec. 8, 1992), pp.553-558
[6] Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996, p. 212-219, disponible ici
[7] Peter W. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, IEEE Symposium on Foundations of Computer Science, 1994, p. 124-134
[8] Alice et Bob apparaissent pour la première fois en 1978 dans un article de Ron Rivest expliquant le cryptage RSA. Depuis, ils constituent une running joke de cryptologues et sont utilisés, avec d’autres personnages, dans tous les exemples.
[9] L’exploit est dû à une équipe suisse, qui s’est attaquée au monstre suivant :
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
Les détails sont présentés dans l’article Factorization of a 768-bit RSA modulus, disponible ici.
[12] Zhang et al, Reference frame independent quantum key distribution server with telecom tether for on-chip client, http://arxiv.org/abs/1308.3436
La formule du jour : superposition d’états dans un qubit
L’état d’un qubit détermine la probabilité avec laquelle une mesure donnera 0 ou 1. On peut représenter n’importe quel état par une position à la surface d’une sphère dont les deux pôles correspondent aux états |0 > et |1 > ; l’état est alors caractérisé par deux angles, θ et ϕ, analogues de la latitude et de la longitude.
La description mathématique de l’état, combinaison de |0 > et de |1 >, s’écrit
On peut en déduire que la probabilité de tomber dans l’état 0 (respectivement 1) en faisant la mesure est donnée par :
Pour θ = 0, cos(θ/2)=1 et sin(θ/2)=0. L’état | ψ > correspond exactement au pôle |1 >, car l’état |0 > n’apparaît pas dans la superposition. La probabilité de trouver l’état |1 > vaut alors 1 et la probabilité de trouver l’état |0 > vaut 0 : on est bien certain de trouver l’état |1 >.
De la même manière, pour θ = 180°, cos(θ/2)=0 et sin(θ/2)=1. La position sur la sphère correspond au pôle | 0 > et on retrouve p|1>=0 et p|0>=1 : on est certain de trouver l’état |0 >.
En revanche, pour θ = 90°, cos(θ/2)=1 et sin(θ/2)= 1/√2. la position est au niveau de l’équateur, à même distance des deux pôles. On trouve alors p|0> = p|1> = ½ : on a autant de chance de tomber sur un pôle que sur l’autre !
On peut remarquer l’expression des probabilités ne fait pas intervenir l’angle ϕ : seule la distance aux pôles compte et l’angle ϕ ne change pas cette distance.
Daniel Suchet