La perspective de fabriquer des ordinateurs quantiques suscite des investissements massifs et des politiques publiques destinées à soutenir l’innovation technologique dans de nombreux pays. Si ceux-ci finissent par être opérationnels, ils pourraient avoir de très grandes puissances de calculs et permettre de traiter certains problèmes bien plus rapidement que les meilleurs ordinateurs classiques.

Néanmoins, pour faire un ordinateur quantique, il faut maîtriser plusieurs ingrédients extrêmement délicats à préparer et à manipuler, et c’est pour cela qu’un ordinateur quantique à même de faire concurrence aux ordinateurs classiques n’existe pas encore.

Ceci n’empêche pas les ordinateurs quantiques de susciter de nombreux fantasmes et parfois, une médiatisation qui n’est pas forcément en phase avec le rythme des développements technologiques.

Claire Goursaud travaille à l’Insa Lyon, où elle développe des algorithmes quantiques pour résoudre des problèmes rencontrés dans les grands réseaux, en particulier les réseaux d’objets connectés (IoT). Claire répond à nos questions sur les capacités actuelles des ordinateurs quantiques, et leurs limites, afin d’éclairer les avancées les plus récentes du domaine.

Aujourd’hui, qui peut utiliser un ordinateur quantique ?

Claire Goursaud : Un ordinateur quantique est construit autour d’un processeur (qui est la partie intelligente de l’ordinateur, c.-à-d., celle qui réalise les calculs), auquel on doit rajouter des périphériques/interfaces, une mémoire, et un circuit de refroidissement. Il existe des processeurs quantiques que les chercheurs et industriels peuvent utiliser à des fins de recherche et développement. Par exemple, IBM dispose dans ses fermes de calcul de systèmes quantiques qui sont mis à disposition des chercheurs. D-Wave proposait aussi un accès à ses processeurs jusqu’à fin 2024, mais l’a restreint à ces clients depuis le début d’année. Pour l’instant, ces processeurs sont assez petits — 133 qubits dans le cas d’IBM — ce qui limite ce que l’on peut en faire.

Si le nombre de qubits est affiché en augmentation régulière (avec une multiplication par 2 tous les ans pour les processeurs d’IBM), ce n’est pas le seul critère qui permet d’évaluer l’utilité d’un processeur quantique. En effet, c’est la fiabilité des qubits actuels et des calculs qui pêche aujourd’hui.

Les applications promises par les promoteurs des ordinateurs quantiques sont encore lointaines en pratique — simuler des molécules pour développer de nouveaux médicaments par exemple, améliorer la planification des vols commerciaux, ou booster encore davantage l’intelligence artificielle.

À lire aussi : De la cryptographie à l’intelligence artificielle, l’informatique quantique pourrait-elle changer le monde ?

Ces processeurs quantiques peuvent-ils déjà faire des calculs inaccessibles aux supercalculateurs classiques ?

C.G. : Pour le moment, les calculateurs quantiques n’apportent pas encore d’avantage par rapport aux supercalculateurs classiques pour des problèmes qui ont une application concrète tels que ceux cités précédemment.

En revanche, si, en théorie, tous les calculs que l’on sait écrire mathématiquement peuvent être programmés dans un ordinateur classique, la pratique est plus compliquée. En effet, certains calculs demanderaient trop de ressources pour un ordinateur classique : il nous faudrait soit des ordinateurs beaucoup plus grands que ceux dont on dispose (dont les capacités de calcul ne sont donc pas assez importantes), soit un temps que nous n’avons pas (pouvant aller jusqu’au millier ou million d’années pour certains calculs !).

À cet égard, un exemple connu est celui des « clefs de chiffrement », qui sont notamment nécessaires dans le domaine des télécommunications. Ces communications sont chiffrées avec un code que l’on pourrait cracker en principe (en les testant un par un) ; mais cela prendrait tellement de temps de le faire avec un ordinateur classique que ce n’est pas rentable en pratique pour des attaquants.

Comme les processeurs quantiques promettent de paralléliser massivement certains calculs, ils permettraient de résoudre des problèmes qu’on ne sait pas traiter assez rapidement avec un ordinateur classique… Ainsi, les ordinateurs quantiques pourraient permettre de décrypter ces messages actuellement inattaquables.

Mais les processeurs quantiques ne seront pas utiles pour toutes les applications. En effet, pour que le calcul quantique ait réellement un intérêt, il faut des problèmes avec une structure particulière. C’est le cas, par exemple, dans l’internet des objets — le domaine de recherche auquel j’applique le calcul quantique. On a des millions d’objets connectés : des montres, des radiateurs, des voitures… Ces millions d’objets transmettent des informations sans aucune coordination préalable. La station de base reçoit un mélange des messages de chacun de ces objets, qui ne sont pas facilement séparables. La difficulté pour la station de base est de savoir qui a transmis quoi à chaque instant.

Dans ce cas, l’intérêt du calcul quantique est d’attribuer une unité de calcul (un qubit) à chaque objet connecté ; de calculer tous les messages que l’on aurait pu recevoir en fonction de l’activité potentielle de chaque objet connecté, puis de comparer toutes ces possibilités au signal qu’on a réellement reçu… afin de trouver celle qui est la plus proche du message réel.

Pour simuler de cette manière un petit réseau de 20 objets connectés avec un ordinateur classique, il faut faire 2²⁰ calculs (soit 1 048 576) ; alors qu’avec un ordinateur quantique, il ne faut faire « que » sqrt(2²⁰) de calculs environ (en utilisant alors 20 qubits pour représenter les 20 objets auxquels se rajoutent une ou plusieurs dizaines de qubits pour contenir le résultat des calculs intermédiaires).

Ainsi, on peut réduire considérablement le temps de calcul. En pratique, le gain de temps dépendra des processeurs quantiques utilisés.

Qu’est-ce qui limite les processeurs quantiques actuels ?

C.G. : Ce qui limite l’utilisation de processeurs quantiques aujourd’hui est principalement leur taille et leur fiabilité.

Tout d’abord, les processeurs quantiques opérationnels actuellement font entre quelques dizaines et quelques centaines de qubits (par exemple IonQ avec 35 qubits et 1121 qubits pour le processeur Condor de IBM), mais avec des fiabilités variées.

Ces nombres ne sont pas suffisants pour qu’il soit réellement intéressant d’utiliser actuellement des processeurs quantiques pour autre chose que de la recherche, ou du développement de meilleurs processeurs. Par exemple, les processeurs quantiques qu’IBM met à disposition des chercheurs possèdent 133 qubits, ce qui me permet d’étudier un réseau de 20 objets connectés seulement.

Mais, ce qui limite la taille des ordinateurs quantiques aujourd’hui, c’est ce qu’on appelle le « bruit ». Aujourd’hui — ou du moins jusqu’à très récemment, comme nous allons le voir — plus il y a de qubits, plus il est difficile de contrer ce bruit. Ce « bruit » détruit les propriétés quantiques des qubits, ce qui provoque des erreurs de calcul, et diminue donc l’utilité des processeurs quantiques.

D’où vient le bruit dans les processeurs quantiques ?

C.G. : Dans les processeurs quantiques, on manipule des qubits, qui sont en fait des particules toutes petites et très sensibles à tout ce qui se passe autour d’elles : du « bruit » qui perturbe, voire détruit, leur état quantique.

À lire aussi : Ordinateur quantique : comment progresse ce chantier titanesque en pratique

Il y a plusieurs sources de bruit pour les ordinateurs quantiques aujourd’hui. Tout d’abord, la particule quantique « vieillit » lorsqu’elle interagit avec son environnement. C’est un phénomène que l’on appelle la « décohérence ».

Il y a aussi du bruit thermique : quand on n’est pas au zéro absolu, la particule bouge, ce qui peut perturber son état quantique.

Il peut aussi y avoir des impuretés dans les matériaux électroniques — c’est également le cas dans les processeurs classiques ; mais c’est particulièrement nuisible dans les ordinateurs quantiques.

Enfin, deux autres sources de bruits sont liées au fait qu’on met plusieurs qubits les uns à côté des autres. On est face à une injonction contradictoire : il faut à la fois isoler les particules les unes des autres pour limiter le bruit, mais aussi bien sûr les laisser interagir quand c’est nécessaire pour le calcul. Quand on demande aux qubits d’interagir pour faire le calcul, on le fait avec des impulsions (des « portes ») — si ces impulsions sont mal réglées, ça introduit des perturbations qui modifient l’état quantique du qubit.

Ce bruit induit des erreurs de calcul ?

C.G. : Oui, et on distingue deux types d’erreurs de calcul quantique.

La première s’appelle un « bit flip » : c’est quand l’état quantique de la particule passe de 0 à 1 ou l’inverse. On maîtrise très bien ces erreurs dans le domaine des télécommunications, qui est depuis toujours basé sur des 0 et des 1 (les « bits » des ordinateurs classiques). Pour réparer ces erreurs, on peut utiliser les « codes correcteurs d’erreurs » hérités des télécommunications classiques.

En revanche, le second type d’erreur est plus problématique. Il s’agit de ce que l’on appelle une « erreur de signe » : on conserve le 0 (l’erreur n’est pas un bit flip) mais le signe est erroné (un signe « moins » au lieu d’un signe « plus », ou l’inverse). Les erreurs de signe sont très importantes aujourd’hui en calcul quantique, parce que les codes correcteurs historiques ne corrigent pas ces erreurs de signes… qui sont tout à fait spécifiques au monde quantique, parce qu’elles sont liées au fait que l’on décrit les états quantiques avec des nombres complexes.

Pour contrer les effets du bruit qui perturbe les qubits et obtenir des processeurs quantiques utiles, les chercheurs développent aujourd’hui de nouveaux codes correcteurs d’erreurs qui prennent aussi en compte les erreurs de signe.

Ces « codes correcteurs d’erreur » qui sont au cœur des recherches et des avancées actuelles ?

C.G. : Aujourd’hui, une des tendances les plus porteuses pour ces nouveaux codes correcteurs d’erreurs s’appelle les « codes de surface » : le principe est de dupliquer le qubit physique (l’état de la particule), et à l’aide de liens entre tous les qubits dupliqués, de générer un « qubit logique ». Ce qubit logique est donc composé de plusieurs qubits physiques, et il est en principe dépourvu d’erreurs, ce qui permet de l’utiliser dans le calcul.

Cette stratégie demande d’avoir de nombreux qubits physiques pour obtenir un seul qubit logique. Or, on a vu que plus il y a de qubits, plus il y a de problèmes de bruit. C’est pourquoi on craignait jusqu’à récemment que les problèmes ajoutés par la démultiplication des qubits physiques n’annulent les gains obtenus avec cette stratégie de code de surface.

Or, en décembre 2024, Google a montré que cette stratégie marche en pratique : les chercheurs ont présenté un processeur appelé « Willow », qui contient 105 qubits physiques formant un qubit logique : c’est un code correcteur d’erreur plus grand et plus difficile à manipuler que les codes précédents, mais, au global, il est plus performant.

Il faut bien réaliser que Willow ne contient qu’un seul qubit logique. Il faudrait en associer plusieurs pour pouvoir faire des calculs utiles. Dans l’exemple de mon réseau d’objets connectés, il faudrait un Willow pour chacun des objets connectés du réseau puisque les 105 qubits physiques équivalent à un seul qubit logique suffisamment résistant aux perturbations pour faire des calculs. Le nombre de qubits annoncés par les fabricants, qui sont des qubits physiques, ne sont donc pas suffisants pour évaluer les capacités d’un processeur quantique.

Néanmoins, cette avancée suggère que l’on va désormais voir se développer des codes encore plus grands, pour une probabilité d’erreur encore plus petite — en d’autres termes, la stratégie des codes correcteurs de surface semble avoir de l’avenir devant elle.

Claire Goursaud a reçu des financements de l'ANR et de l'INRIA pour travailler sur les algorithmes quantiques.

Découvrez l’histoire tragique de Marie Stuart, reine d’Écosse, qui fut condamnée à mort pour haute trahison par la couronne d’Angleterre. La preuve du complot a été apportée par le décryptage des lettres échangées entre les conspirateurs. Une histoire redécouverte par un projet de recherche réunissant historiens, cryptographes, et experts en intelligence artificielle.

1587, château de Fotheringhay au cœur de l’Angleterre : ce n’est qu’au troisième coup de hache que le bourreau, ivre, parvient à décrocher la tête de la reine d’Écosse. C’est le cou de Marie Stuart qui vient de rompre, comme un fil qui lâche, en raison d’un code secret qui avait lui-même été cassé.

Marie Stuart était coupable de haute trahison. Elle avait pris part au complot visant à assassiner la reine d’Angleterre, Elizabeth, sa cousine. L’Angleterre avait intercepté des lettres échangées entre Marie et les autres conspirateurs mais Marie s’était sentie protégée car elle avait pris des précautions : les lettres étaient chiffrées, c’est-à-dire protégées par un code secret. Cela signifie qu’un regard naïf ne pouvait y voir qu’une succession de symboles inintelligibles. Comment la reine Elizabeth pouvait-elle alors y lire la preuve du complot ?

Nouveaux décryptages de Marie Stuart en 2023

En 2023, une cinquantaine de lettres perdues relatives à Marie Stuart ont pu être réattribuées à leurs auteurs. Elles étaient conservées à la Bibliothèque nationale de France mais n’étaient liées ni à une époque correcte ni au bon contexte géographique, faute de date, de signature et surtout de contenu lisible. Une équipe de déchiffreurs étrangers qui arpentaient Internet à la recherche de documents numérisés et codés les ont ainsi trouvées. Grâce à leur décryptage, c’est-à-dire à la méthode qui permet de redécouvrir les mots cachés derrière les symboles, 55 lettres ont pu être reliées à leur corpus originel. Les techniques utilisées sont similaires à un projet de recherche de plus grande ampleur, réunissant historiens, cryptographes, et experts en intelligence artificielle. Ce projet que je porte et dont l’objectif est à terme de fournir un outil de lecture et de déchiffrement de textes manuscrits chiffrés et anciens se nomme Back In Time. Il a reçu en novembre le prix de l’innovation du magazine Historia, et le grand prix du jury Historia 2024.

La reine exilée, veuve et prisonnière

Marie, orpheline de père à une semaine, devient reine d’Écosse à 9 mois, en 1542, dans un contexte de guerres entre l’Écosse catholique et l’Angleterre protestante. Après la mort de son père, le roi d’Angleterre Henry VIII cherche à marier son fils pour unir les royaumes, mais l’Écosse préfère une alliance avec la France. En réponse, Henry VIII attaque l’Écosse. À 6 ans, Marie est envoyée en France pour sa sécurité et devient reine de France en épousant François II à 16 ans, mais celui-ci meurt rapidement. Veuve à 18 ans, elle revient en Écosse où la noblesse protestante se détourne d’elle.

Marie se remarie avec un homme cruel et violent, qui assassinera son secrétaire. Son mari est retrouvé mort dans des circonstances suspectes, et Marie, maintenant veuve deux fois et mère d’un fils, se remarie encore. Cependant, la noblesse écossaise la contraint à abdiquer en faveur de son fils. Elle tente de récupérer le trône avec 6 000 hommes, mais échoue et se réfugie en Angleterre. Là, sa cousine Elizabeth l’emprisonne, craignant que Marie, catholique, ne fasse figure de rivale pour le trône anglais, où les catholiques la soutiennent comme leur véritable reine : Elizabeth est de lignée plus directe, mais elle est issue d’un deuxième mariage du roi Henry VIII que le pape n’a pas permis. Officiellement cependant, Elizabeth emprisonne Marie en raison du meurtre de son second mari.

Marie passe dix-huit années privée de liberté, tandis que son fils, élevé par ses ennemis, apprend à la détester.

Le complot Babington

Nous sommes en 1586, Marie a 44 ans. Elle n’a plus aucun contact avec l’extérieur lorsqu’elle reçoit pourtant un surprenant paquet de lettres. Ces lettres ont été emballées dans une poche de cuir, cachée elle-même dans une bonde creuse qui ferme une barrique de bière livrée au manoir. Elle est certes privée de liberté, mais Marie n’est pas maltraitée. Ce procédé qui consiste à cacher l’existence d’un message s’appelle la stéganographie.

Les lettres de Marie attendaient à l’ambassade de France à Londres, en quête d’un moyen de contourner ses geôliers. Gifford, un catholique anglais, se porte volontaire en 1585 pour aider Marie. Il se rapproche de l’ambassade de France et, avec l’aide d’un brasseur local, il parvient à lui faire passer son courrier.

Mais Gifford n’est pas seul. En mars 1586, Babington, un jeune catholique, forme une conspiration pour libérer Marie, tuer Elizabeth et placer Marie sur le trône anglais. En juillet, ils parviennent à entrer en contact avec Marie grâce à l’aide miraculeuse de Gifford. Marie a déjà eu écho du complot par ses alliés français, et demande des précisions à Babington, qui lui expose son plan. Il légitime l’assassinat d’Elizabeth par l’excommunication de celle-ci par le pape en 1570.

Bien sûr, prudent, Babington utilise un code secret – que l’on appelle aussi chiffrement – non pas pour dissimuler l’existence d’un message, mais pour brouiller le sens de celui-ci. La lettre ressemble alors à une succession de symboles variés qui rendent le plan de Babington inintelligible à tout espion. La table de chiffrement de Marie fonctionne ainsi : chacune des lettres de notre alphabet correspond à 4 symboles différents, tous synonymes, que l’on peut choisir selon son envie pour chiffrer une lettre. D’autres symboles ont pour valeur non pas une mais deux lettres, comme le fréquent « TH » en anglais. Plus compact encore, une centaine de symboles représentent des mots courants, des titres, des lieux, comme « The pope » ou « Scotland ». Un symbole possède le pouvoir de faire doubler la lettre du symbole qui le suit. Enfin, et c’est terrible pour un déchiffreur ennemi, des symboles pièges, appelés symboles nuls ne sont présents que pour faire diversion. Ils ne représentent rien, ni ponctuation, ni espace, et sont au nombre d’une vingtaine.

Pour déchiffrer, Marie utilise la même table de correspondance. Elle est aidée dans cette tâche par trois secrétaires : Nau de la Boisselière qui est vraisemblablement le créateur de ce chiffre et qui rédige la correspondance de Marie sous sa dictée, en français ; Curle, qui traduit en anglais ; et Pasquier, les petites mains qui chiffrent et déchiffrent le courrier.

Décryptage et agents doubles

Mais Gifford est un traître, un agent double ! Avant son retour en Angleterre, il avait écrit à Walsingham, le premier secrétaire de la reine Elizabeth pour se mettre à son service. Son passé de prêtre catholique lui permettait de jouer un double jeu aux yeux de Marie Stuart. L’idée d’approcher l’ambassade de France venait de Walsingham, et chaque fois que Gifford faisait passer un courrier de Marie, il le remettait en réalité à Walsingham, qui copiait le contenu des lettres sans que Marie ne s’en aperçoive.

Lorsque la lettre de Babington arriva, Walsingham la présenta à son meilleur déchiffreur, Phelippes. Le message de Babington autorisait l’assassinat d’Elizabeth, mais Marie stipulait que cela ne devrait se faire que si elle était d’abord libérée. Walsingham, insatisfait, ordonna à son cryptographe de se faire passer pour Marie et de forger un post-scriptum chiffré demandant subtilement le nom des « gentilshommes qui accompliront notre dessein ». Et Babington les donna tous.

L’histoire de Marie Stuart nous prouve tragiquement que l’utilisation d’un code secret peut s’avérer plus dangereuse qu’aucune procédure de chiffrement. En effet, Marie comme Babington se sont autorisés à décrire précisément leurs intentions. La confiance dangereuse qu’ils ont placée dans cette technique les a tous les deux conduits à leur mort.

Babington ainsi que tous les complotistes passèrent aux aveux. L’historien William Camden rapporte l’horreur de leurs exécutions : « on coupa la corde qui les pendait, on les émascula, ils furent étripés vivants et conscients, puis écartelés ».

Marie cependant bénéficia d’un procès ; toutefois sans avocat ni témoin comme c’est le cas pour une accusation de trahison. Sa principale défense consista à nier tout rapport avec Babington, pensant, à tort, qu’elle serait protégée par son chiffrement. Des extraits déchiffrés de sa correspondance furent lus à son audience. Elle fut condamnée à mort et décapitée à 44 ans.

Méthodes de cryptanalyse

La cryptanalyse, c’est-à-dire l’art d’attaquer un code secret, est ma spécialité tout comme celle de Phelippes. Ne trouvant aucune information sur les méthodes utilisées par Phelippes, j’ai longtemps cru qu’il avait fait preuve de beaucoup d’observations : compter les symboles, étudier leur fréquence, analyser les liens de proximité entre les symboles (certains sont souvent proches, d’autres ne se retrouvent jamais côte à côte…) pour en tirer des conclusions en comparaison avec des statistiques de la langue anglaise du XVI^e siècle. C’est tout du moins ce que nous ferions sans ordinateur, et cela prendrait quelques semaines ou mois.

Mais Phelippes savait décrypter en quelques heures ! C’est que la vérité, hélas, est moins romantique qu’un génie isolé : Walsingham avait placé Morgan – un second agent double – auprès de Marie Stuart. Morgan concevait les tables de chiffrement utilisées par le secrétaire de Marie, et il était également un ami proche de Phelippes. De ce fait, doit-on être surpris que Phelippes ait su briser le code secret de Marie ? Malgré le mythe qui s’est créé autour d’elle, tout porte à croire que la reine d’Écosse ait davantage été victime d’un piège que des talents d’un déchiffreur.

Cécile Pierrot a reçu des financements de l'Agence Nationale de la Recherche (projet Kleyptomaniac).

Un spectre hante le petit monde des économistes : les pseudonymes utilisés de 2013 à 2023 pour envoyer des messages sur le forum Economics Job Market Rumors (EJMR), dont le site prétendait qu’ils étaient totalement sûrs et garantissaient de pas de remonter aux auteurs et autrices des messages, permettent en réalité d’identifier de quelle adresse Internet ces messages ont été postés. Un récent article (Anonymity and identity online, par les chercheurs Florian Ederer, Paul Goldsmith-Pinkham et Kyle Jensen) donne le procédé suivi pour cela. Cet article met en lumière de graves erreurs d’utilisation de la cryptographie par le gestionnaire du site.

Pour comprendre ce qui s’est passé, considérons tout d’abord le chiffrement le plus simple, par substitution de lettres : on remplace chaque lettre de l’alphabet par une autre, ou par un symbole, et la clef secrète est la table de ces substitutions. Quiconque a lu Sherlock Holmes (Les Hommes Dansants) sait que l’on peut attaquer un tel chiffrement en repérant que le E est la lettre la plus fréquente, puis en faisant des inférences par rapport aux mots rencontrés.

De fait, si pour chiffrer un message on applique toujours exactement le même chiffrement, on a une vulnérabilité : si on utilise toujours le même message chiffré pour le texte en clair OUI et toujours le même message chiffré pour le texte en clair NON, une personne espionnant la conversation a vite fait d’identifier ces réponses. Aussi, quand on chiffre un message, on va habituellement le faire précéder de données tirées au hasard, de sorte que le message chiffré dépendra de ces données et qu’on obtiendra deux messages chiffrés différents en chiffrant OUI deux fois ; on jettera ces données au moment du déchiffrement.

Hachage cryptographique

Dans le procédé qui était utilisé par le site EJMR, l’adresse IP de l’utilisateur (une adresse formée de nombres qui lui est attribuée par son fournisseur d’accès Internet) était combinée avec le sujet de discussion dans lequel il intervenait, puis passée à une fonction de hachage cryptographique (pas un chiffrement, mais la différence entre les deux n’est pas importante pour la vulnérabilité du procédé), sans ajout de donnée supplémentaire. Cette combinaison se faisait tout simplement en les mettant bout à bout, ce que les auteurs de l’article ont vite trouvé. Ensuite, le pseudonyme de l’utilisateur dans le fil de discussion était formé de quatre chiffres extraits de la sortie de cette fonction de hachage.

Avec un tel procédé, il est facile de tester si un message a pu être posté depuis une certaine adresse : il suffit de prendre cette adresse, de la mettre bout à bout avec le sujet de discussion, de passer le tout au hachage cryptographique, d’extraire les quatre chiffres pertinents et de comparer le résultat avec le pseudonyme identifiant la personne dans ce fil. Les auteurs de l’article ont fait cela pour toutes les adresses possibles (il y en a environ 4 milliards) et tous les fils de discussion. Pour chaque message, pour chaque fil, ils ont ainsi identifié les possibles adresses d’où il aurait pu être posté. Ceci donne, pour chaque message, environ 65 000 adresses d’origine possibles.

On pourrait penser qu’avoir une liste de 65 000 adresses possibles, ce n’est pas pointer les auteurs. Mais, de même que pour l’énigme des hommes dansants, Sherlock Holmes pouvait exploiter le fait que la même convention de chiffrement était utilisée pour plusieurs lettres et que celles-ci devaient former des mots, ici on peut exploiter le fait que le même utilisateur, à la même adresse, risque de poster des messages sur plusieurs sujets. Or, seule une infime proportion des utilisateurs d’Internet poste sur EJMR. Si une même adresse apparaît parmi les adresses possibles pour des utilisateurs postant à des dates voisines sur plusieurs sujets de ce site, alors c’est probablement elle l’adresse de ces utilisateurs.

[Plus de 85 000 lecteurs font confiance aux newsletters de The Conversation pour mieux comprendre les grands enjeux du monde. Abonnez-vous aujourd’hui]

L’article se livre ensuite à diverses analyses : certaines adresses utilisées appartiennent aux réseaux de prestigieuses universités ou institutions étatsuniennes ; une proportion des messages postés avaient un caractère raciste et/ou sexiste ; etc. C’est ce dernier point qui, peut-être, fait réagir certains qui n’aimeraient pas que leurs propos orduriers soient rapportés à leur employeur ou soient publiquement associés à leur personne.

Procédé absurde

Du point de vue de l’informaticien et notamment du cryptographe, le procédé utilisé pour anonymiser, ou plutôt pseudonymiser, les utilisateurs de ce site, était absurde. Dès que l’article explique comment le site fonctionnait, la messe est dite : l’attaque est évidente. Comment se fait-il que ce mécanisme de pseudonymisation ait été choisi ?

Au vu de certains messages laissés par l’auteur du site, celui-ci avait une très grande confiance dans l’impossibilité de remonter aux adresses des auteurs des messages, probablement fondée sur le choix d’une fonction de hachage cryptographique. Ces fonctions, en effet, sont censées être à sens unique : on ne peut pas remonter aux données originales. Cependant, cela ne vaut que si on utilise convenablement ces fonctions, et ici il aurait fallu, par exemple, ajouter aux données une donnée secrète, connue uniquement du gestionnaire du site.

La morale de cette affaire est que si, de nos jours, des outils cryptographiques sont largement disponibles depuis des langages de programmation destinés à un large public, ces outils sont difficiles à utiliser. On dit souvent don’t roll your own security – « ne déployez pas des mécanismes de sécurité de votre propre conception », et ce notamment s’agissant d’individus ou d’entreprises dont la sécurité ou la cryptographie n’est pas le sujet d’expertise.

Dans certains cas, on peut se féliciter de l’incompétence des auteurs. Ainsi, une étude a relevé en 2016 que de nombreux logiciels malware, c’est-à-dire utilisés à des fins malveillantes, de piratage, d’exigence de rançons, etc. comportent des erreurs d’utilisation de la cryptographie. Les auteurs attribuent cela à ce que les auteurs de malware utilisent la cryptographie sur la base d’intuitions, de superstition, et sautent sur les occasions de réinventer la roue (proposer leur propre solution à des problèmes déjà bien connus et traités et pour lesquels il existe des solutions très convenables), mais aussi d’utiliser des éléments logiciels préexistants mais qui résolvent d’autres problèmes que celui posé. Par ailleurs, ils bluffent afin de décourager les victimes.

Le précédent OpenSSL

Hélas, les dysfonctionnements cryptographiques dus à de la rédaction ou modification hasardeuse de logiciels ne sont pas limités aux logiciels malveillants. Un exemple célèbre est la découverte en 2008 que, depuis 2006, le générateur de clefs cryptographiques de la bibliothèque OpenSSL distribuée dans le système d’exploitation Debian Linux (et d’autres basés sur lui, comme Ubuntu), au lieu de tirer les clefs au hasard dans un énorme espace, les tirait en fait de sorte qu’il suffisait de les essayer toutes pour pouvoir faire des choses normalement interdites (intercepter des communications avec des sites web sécurisés, etc.).

Ce fiasco était dû à des modifications du logiciel par des gens qui ne comprenaient pas son fonctionnement et à des problèmes de communication avec l’équipe chargée du développement du logiciel.

Pour en revenir au forum EJMR, cet épisode devrait nous inciter à avoir un regard critique sur les prétentions à la sécurité (« cryptographie de qualité militaire », « inviolable », etc.) de prestataires, de sites, de fournisseurs, qui ne reposent pas sur des études publiques et documentées.

David Monniaux does not work for, consult, own shares in or receive funding from any company or organisation that would benefit from this article, and has disclosed no relevant affiliations beyond their academic appointment.

Alors que les cyberattaques se multiplient, chacun d'entre nous peut potentiellement y être confronté. Certes, nous avons tous nos astuces pour les mots de passe que nous utilisons dans nos ordinateurs et nos portables : cachés sous un clavier, écrits sur un bout de papier ou issus de la date d’anniversaire du petit dernier.

Mais comment faire pour s'assurer que son mot de passe est véritablement in-cra-qua-ble ?

De nombreuses études constatent qu’une part importante des mots de passe ne protègent pas suffisamment les utilisateurs : les mots de passe sont trop faibles et trop souvent réutilisés. Par exemple, 51 % des Français utiliseraient le même mot de passe pour des usages professionnels et personnels – une statistique que l’on retrouve aux États-Unis.

À partir d’un mot de passe, les cybercriminels pourront récupérer des informations privées en se connectant à nos comptes en ligne (messageries, réseaux sociaux, etc.), notamment nos comptes bancaires ou de e-commerce, mais aussi pénétrer sur notre ordinateur et en chiffrer le contenu en vue d’obtenir une rançon.

Le vol d’un mot de passe peut avoir des conséquences financières, mais aussi psychologiques à travers des pratiques comme le « doxxing » (publier des informations sur l’identité ou la vie privée d’une personne dans le but de lui nuire) ou le « revenge porn ». Dans le cadre professionnel, les fuites de mot de passe exposent l’entreprise à des attaques par chantage, à des « dénis de service » (des cyberattaques consistant à interrompre ou malmener le service fourni par un tiers), ou encore à de l’espionnage économique.

À lire aussi : Cryptographie : comment ma carte à puce résiste-t-elle aux attaques ?

Comment un fraudeur récupère-t-il des mots de passe ?

Les deux grandes approches utilisées par les cybercriminels pour récupérer des mots de passe sont l’ingénierie sociale et le vol de bases de données d’identifiants.

L’ingénierie sociale consiste pour le cybercriminel à convaincre sa victime de révéler son mot de passe en ayant, typiquement, recours à l’hameçonnage : la grande majorité des attaques ne ciblent pas une victime prédéfinie et ces attaques de masse ont pour but d’hameçonner des victimes quelconques. C’est seulement dans un second temps que le cybercriminel concentrera ses forces sur la personne hameçonnée.

Quant au vol de bases de données d’identifiants, l’attaque consiste généralement à pirater un site web pour voler les noms et mots de passe des utilisateurs afin de se connecter sur le compte des victimes, de les utiliser sur d’autres comptes (par exemple, le fraudeur testera les identifiants Google de sa victime sur Twitter) ou de les revendre sur le dark web. Le site web « Have I been pwned ? » permet à chacun de vérifier si son mot de passe a fuité sur Internet ; il recense actuellement presque 12 milliards de comptes dont les identifiants ont fuité.

Dans la majorité des cas, ces bases de données d’identifiants ne contiennent pas des mots de passe, mais des empreintes de mots de passe : l’empreinte est le résultat d’une fonction dite « à sens unique » qui est appliquée sur le mot de passe. Par analogie, l’empreinte est au mot de passe ce que l’empreinte digitale est à l’humain : deux mots de passe différents ont des empreintes différentes et étant donné une empreinte, on ne peut pas identifier l’humain. Mais étant donné une empreinte et un humain, on peut dire si l’empreinte provient de cet humain. Dans le cas des mots de passe, on ne peut donc pas retrouver le mot de passe à partir de son empreinte, mais on peut tester un mot de passe pour voir s’il correspond à l’empreinte : on dit alors que le mot de passe est « cassé ».

Les casseurs de mots de passe utilisent différentes approches pour tester les mots de passe les plus probables : d’abord les plus courts, puis les mots du dictionnaire et leurs variantes (par exemple « repas », puis « Repas », « RepaS », « saper », « repas1 »…) et les mots de passe fortement structurés (par exemple démarrant par une majuscule, puis des minuscules, des chiffres et enfin des caractères spéciaux).

Les casseurs modernes peuvent également utiliser des techniques évoluées reposant sur l’intelligence artificielle ou l’algorithmique.

Enfin, tous les mots de passe possibles sont testés si les autres tentatives ont échoué : c’est ce que l’on appelle une recherche exhaustive, qui a généralement peu d’espoir de rencontrer un succès en un temps raisonnable. Notamment, les attaques qui consistent à tester directement sur un site web différents mots de passe pour un utilisateur donné jusqu’à réussir à se connecter sont peu praticables : elles sont très lentes à cause du temps de réponse du serveur web et facilement détectables.

Qu’est-ce qu’un mot de passe robuste ?

Pour se protéger efficacement, il faut utiliser des mots de passe robustes, ne pas utiliser un même mot de passe pour plusieurs usages et changer de mots de passe régulièrement.

Pour qu’un mot de passe soit robuste, il faut qu’il soit choisi aléatoirement dans un ensemble de mots de passe ayant la même chance d’être choisis : par exemple, un mot présent dans le dictionnaire serait cassé en une poignée de secondes. Ajouter une majuscule ou des chiffres à la fin n’apporte qu’une sécurité illusoire.

À lire aussi : Cryptographie : à quoi servent les nombres aléatoires ?

Afin de mesurer la robustesse d’un mot de passe choisi aléatoirement (cas idéal, rarement atteint sans gestionnaire de mots de passe), on compte le nombre de tests que devra faire un pirate dans le pire des cas pour le casser. Cette valeur est généralement calculée par la formule n^c_ où c est la longueur du mot de passe et n la taille de l’ensemble des éléments parmi lesquels piocher pour composer le mot de passe. Par exemple, dans le cas d’un mot de passe de longueur 8 (c=8), composé de lettres minuscules uniquement (n=26), le pirate devra tester 26⁸ mots de passe (soit 208 milliards) dans le pire des cas. Bien que le chiffre semble astronomique, un ordinateur standard mettra moins d’une seconde pour le casser en utilisant la puissance de calcul de sa carte graphique.

L’Agence Nationale de la Sécurité des Systèmes d’Information (ANSSI) définit la robustesse d’un mot de passe par la taille de l’espace dans lequel il est choisi aléatoirement, et distingue quatre catégories.

La robustesse d’un mot de passe d’après l’ANSSI

Un mot de passe aléatoire, construit à partir d’un alphabet constitué de lettres, de chiffres et de 8 caractères spéciaux, devra ainsi contenir au moins 17 caractères (par exemple, « b !sDzf5w,5+W2s3k ») pour être considéré comme fort selon l’ANSSI, et il sera considéré comme très faible s’il est de taille inférieure ou égale à 10 caractères (« b !sDzf5w,5 »). Même très faible, le mot de passe sera difficile à mémoriser… surtout qu’il faut en mémoriser des dizaines !

Pour faciliter la mémorisation des mots de passe, une technique de plus en plus recommandée consiste à utiliser des « phrases de passe », c’est-à-dire des suites de mots choisis aléatoirement. Une phrase de passe de sept mots choisis dans un dictionnaire de 60000 mots pourrait ainsi être « contrefort fatalement semelle signifié distance revergète fourguer », plus facile à mémoriser que « b !sDzf5w,5+W2s3k » pour une sécurité équivalente.

Mais il est difficile pour un humain de choisir aléatoirement des mots dans un ensemble suffisamment grand, car nous n’utilisons que quelques centaines de mots au quotidien. Il est alors conseillé de rajouter des minuscules, majuscules et caractères spéciaux dans la phrase de passe.

Faut-il utiliser un gestionnaire de mots de passe ?

Un gestionnaire de mots de passe est une application qui stocke de manière sécurisée tous les mots de passe de l’utilisateur pour qu’il n’ait pas besoin de les mémoriser. Il lui suffit de se souvenir d’un seul mot de passe, le mot de passe maître, qui doit être le plus fort possible tout en restant mémorisable. L’utilisation d’un gestionnaire de mots de passe, par exemple KeyPass, est recommandée par les grands acteurs de la cybersécurité tels que l’ANSSI, son homologue allemand, le BSI ou l’agence européenne ENISA, ainsi que par des organisations comme Reporters sans Frontières. Certains gestionnaires de mots de passe sont stockés dans le cloud, par exemple Bitwarden (gratuit et open source), 1Password (payant), DashLane (payant), ou encore LastPass (payant, mais il existe une version gratuite assez évoluée) qui est le gestionnaire le plus utilisé mais aussi le plus attaqué.

Notons que les gestionnaires intégrés dans les navigateurs (qui ne nécessitent pas d’installation) ne sont pas recommandés pour des raisons de sécurité, comme le souligne le BSI allemand.

Dans le cas où le gestionnaire stocke les mots de passe dans le cloud, il est fondamental que les mots de passe maîtres soient forts, au sens de l’ANSSI. Dans le cas contraire, un prestataire ayant accès au cloud pourrait les casser et ainsi accéder à tous les mots de passe qu’ils protègent. Il s’agit d’une menace sérieuse à prendre en compte par les entreprises, dans un monde où l’espionnage économique est légion. Recommander aux entreprises d’héberger elles-mêmes les gestionnaires de mots de passe de leurs employés n’est certainement pas un excès de prudence.

Enfin, l’usage de l’authentification par double facteur (par exemple la réception d’un code par mail) est fortement recommandé… même s’il ne faut pas pour autant baisser la garde.

Diane Leblanc-Albarel a reçu des financements du CNRS.

Gildas Avoine a reçu des financements du CNRS pour ses travaux sur la sécurité des mots de passe.

Treize, 53, 433… la taille des ordinateurs quantiques est donnée en termes de bits quantiques, ou « qubits ». Elle a augmenté considérablement ces dernières années grâce à d’importants investissements publics et privés. Clairement, il ne faut pas se focaliser seulement sur leur quantité, car la qualité des qubits que l’on arrive à préparer est aussi importante que leur nombre pour qu’un ordinateur quantique surpasse un jour nos ordinateurs classiques actuels – on parle d’atteindre « l’avantage quantique ». Pourtant, il est concevable que des dispositifs de calcul quantique offrant un tel avantage soient disponibles dans un avenir proche. Comment cela affecterait-il notre vie quotidienne ?

Il n’est jamais facile de faire des prédictions, mais il est admis que la cryptographie sera modifiée par l’avènement des ordinateurs quantiques. Il est devenu banal de dire que la protection de la vie privée est une question essentielle dans notre société de l’information : chaque jour, de grandes quantités de données confidentielles sont échangées, par exemple via l’internet. La sécurité de ces transactions est cruciale et dépend principalement d’un seul concept : la complexité, ou plus précisément la complexité informatique. Les informations confidentielles restent secrètes parce que tout ennemi ou espion désireux de les lire doit résoudre un problème mathématique extrêmement complexe.

[Près de 80 000 lecteurs font confiance à la newsletter de The Conversation pour mieux comprendre les grands enjeux du monde. Abonnez-vous aujourd’hui]

En fait, les problèmes utilisés pour la cryptographie sont si complexes pour nos algorithmes et ordinateurs actuels que l’échange d’informations reste sûr en pratique, car résoudre le problème puis pirater le protocole prendrait un temps ridiculement long (des années, voir plusieurs milliers d’années, par exemple).

L’exemple le plus emblématique de cette approche est le protocole RSA (pour ses inventeurs Ron Rivest, Adi Shamir et Leonard Adleman), le schéma utilisé de nos jours pour sécuriser nos transmissions d’informations (par exemple les transactions bancaires). Sa sécurité repose sur le fait que nous ne connaissons pas d’algorithme efficace pour factoriser les grands nombres. Alors que la factorisation est un problème mathématique facile, que beaucoup d’entre nous ont déjà rencontré à l’école (étant donné un grand nombre, le but est de trouver deux nombres dont le produit est égal au nombre initial, en laissant de côté la solution triviale donnée par le nombre initial et un – par exemple, si le nombre initial est 6, la solution est 2 et 3, car 6=2x3), les protocoles cryptographiques sont construits de telle manière que l’ennemi, pour décrypter le message, doit factoriser un très grand nombre (pas 6 !), ce qui est actuellement impossible en pratique.

Mais si l’on construit des dispositifs informatiques plus puissants, pour lesquels les problèmes mathématiques utilisés actuellement pour la cryptographie sont faciles à résoudre, notre paradigme actuel en matière de protection de la vie privée doit être repensé. En d’autres termes, tandis que les ordinateurs classiques peuvent avoir besoin de durées folles pour résoudre les versions les plus ardues d’un problème (l’âge de l’univers par exemple), les ordinateurs quantiques idéaux devraient être capables de le faire en quelques minutes… ou, si l’on considère des modèles plus réalistes d’ordinateurs quantiques, peut-être en quelques heures.

C’est pourquoi les cryptographes développent des solutions pour remplacer RSA et atteindre la « sécurité quantique », c’est-à-dire des protocoles cryptographiques qui sont sûrs contre un ennemi qui a accès à un ordinateur quantique. Pour ce faire, il existe deux approches principales : la cryptographie post-quantique et la distribution de clés quantiques.

Comment crypter des informations dans un monde équipé d’ordinateurs quantiques ?

La cryptographie post-quantique maintient le paradigme de sécurité basé sur la complexité : on cherche les problèmes mathématiques qui restent difficiles même pour les ordinateurs quantiques, et on les utilise pour construire des protocoles cryptographiques. L’idée est toujours qu’un ennemi a besoin d’un temps ridiculement long pour pirater le protocole. Les chercheurs travaillent d’arrache-pied pour développer des algorithmes de cryptographie post-quantique, et le NIST (le « National Institute of Standards and Technology » américain) a lancé un processus pour solliciter et évaluer ces algorithmes. Les candidats choisis ont été annoncés en juillet 2022.

La cryptographie post-quantique présente un avantage majeur : elle est basée sur des logiciels. Elle est donc bon marché et, surtout, son intégration dans les infrastructures existantes est simple, puisqu’il suffit de remplacer le protocole précédent, par exemple RSA, par le nouveau.

Mais la cryptographie post-quantique présente également un risque évident : notre confiance dans la « difficulté » des nouveaux algorithmes face aux ordinateurs quantiques est limitée. En effet, il faut rappeler qu’il n’est pas prouvé qu’aucun des protocoles cryptographiques basés sur la notion de complexité est sûr : il n’existe pas de preuve (mathématique) qu’ils ne peuvent pas être résolus efficacement sur un ordinateur classique ou quantique !

C’est par exemple le cas de la factorisation. On ne peut pas exclure qu’un algorithme classique de factorisation efficace soit trouvé un jour – auquel cas la sécurité basée sur le protocole s’effondrerait, même sans ordinateur quantique. On pense que c’est peu probable, car des chercheurs (très intelligents) cherchent depuis des siècles un algorithme efficace pour la factorisation, sans succès. Mais on ne peut pas l’exclure.

Dans le cas des nouveaux algorithmes, la preuve de leur complexité est beaucoup plus limitée, car ils ont été inventés récemment et ils n’ont pas encore été beaucoup mis à l’épreuve – ni par des chercheurs (toujours très intelligents) ni par un ordinateur quantique (car aucun n’est disponible). Parfois, les tests de difficulté sont assez rapides : l’un des algorithmes proposés dans l’initiative du NIST a été par la suite craqué en une heure sur un PC standard.

Exploiter les lois de la physique quantique pour sécuriser les communications

La deuxième approche de la sécurité quantique est la distribution de clés quantiques. Ici, nous avons un changement de paradigme, puisque la sécurité des protocoles n’est plus basée sur des considérations de complexité, mais sur les lois de la physique quantique. On parle donc de sécurité physique quantique.

Sans entrer dans les détails, une clé secrète est distribuée à l’aide de qubits et la sécurité du protocole découle du principe d’incertitude d’Heisenberg, qui implique que toute intervention de l’espion est détectée car elle modifie l’état de ces qubits.

Le principal avantage de la distribution de clés quantiques est qu’elle est basée sur des phénomènes quantiques, qui ont été vérifiés dans de nombreux laboratoires expérimentaux.

Le principal problème pour son adoption est qu’elle nécessite un nouveau matériel (quantique). Il est donc coûteux et son intégration dans les infrastructures existantes n’est pas facile. Pourtant, d’importantes initiatives sont en cours, par exemple pour le déploiement de la distribution de clés quantiques à l’échelle européenne.

Plus forts ensemble

Quelle approche adopter ? Cette question est souvent présentée comme une dichotomie et même cet article a pu donner cette impression jusqu’ici. En fait, je pense que la voie à suivre est de combiner la distribution de clés quantique (voir matérielle) et post-quantique (voie logicielle). La distribution quantique des clés nous a montré que la physique quantique nous fournit de nouveaux outils et recettes pour garantir nos secrets, au-delà des arguments de complexité standard. Si les deux approches sont combinées, les pirates informatiques auront beaucoup plus de mal à pirater les protocoles de sécurité, car ils devront faire face à la fois à des problèmes de calcul complexes et à des phénomènes quantiques.

Antonio Acín est ICREA Professor au ICFO-The Institute of Photonic Sciences. Il a reçu des financements de AXA Fund, la Union Européenne, et les gouvernements espagnol et catalan.

« Téléportation Scotty ! », ces mots célèbres sont ceux du Capitaine Kirk de la fameuse série Star Trek à la fin des années 60 à son ingénieur de vaisseau pour qu’il puisse le téléporter du vaisseau spatial Enterprise à une planète à explorer à proximité.

Si la téléportation de Kirk n’est pas pour demain, la physique quantique a montré que la téléportation est possible dans des conditions très particulières : pour de tout petits systèmes, comme la lumière, et s’ils sont bien « protégés ». La téléportation quantique est connue théoriquement depuis le début du XX^e siècle, a été démontrée expérimentalement dans sa seconde moitié, et aujourd’hui, ce phénomène est utilisé pour des applications bien concrètes… et notamment pour développer ce que l’on appelle l’« Internet quantique ».

Nos télécommunications actuelles, dont Internet, reposent sur des échanges d’informations codées, qui transitent, souvent sur de la lumière, via des fibres optiques ou à l’air libre entre les antennes relais et les téléphones et jusqu’aux satellites en orbite autour de la Terre. Un Internet quantique utiliserait les propriétés quantiques de la lumière, et en particulier le fait de l’on peut « intriquer » les particules de lumière, ce qui permet de « téléporter » l’information que portent ces particules. Ces propriétés permettraient d’échanger des informations de manière cryptée et infalsifiable, ce qui a des applications en cryptographie et donc pour la cybersécurité.

Des communications quantiques cryptées peuvent à l’heure actuelle être maintenues sur une distance maximale d’une centaine de kilomètres – ce qui reste un peu court pour les télécoms mondiales… mais des solutions techniques sont en développement.

Crypter ses communications

Il existe de nos jours différents protocoles de cryptographie quantique et plusieurs entreprises et start-up sont sur ce marché de niche mais en pleine expansion.

Le but ultime de la cryptographie est de crypter ou cacher un message qui ne doit être lu que par la personne que nous avons en tête, appelons cette personne Bob. Pour cela, l’expéditrice, que l’on appelle Alice, doit générer une clé cryptée qu’elle pourra combiner à son message pour le cacher du reste du monde. Bob, de son côté, doit être le seul à avoir cette même clé pour pouvoir décrypter le message (il fera en fait l’opération inverse du cryptage d’Alice pour décrypter le message).

Read more: De la cryptographie à l’intelligence artificielle, l’informatique quantique pourrait-elle changer le monde ?

On commence par coder le message « Passe prendre le pain s’il te plaît » par une série de 1 et de 0, c’est le codage binaire. Puis on crypte le message en générant en parallèle de celui-ci, une clé cryptée faite également de 1 et de 0, et qui sera combinée au message. Mais ce système de cryptage possède plusieurs défauts si l’on veut qu’il soit sécurisé. Tout d’abord, il faut générer une clé qui soit aussi longue que le message (en termes de 1 et de 0), de façon le plus aléatoire possible – pour qu’on ne puisse pas la prédire – ce qui est possible mais à un coût économique et énergétique très grand.

Dans les faits, ces clés que l’on utilise ne sont pas complètement aléatoires. Et surtout, elles sont réutilisées en tout ou partie, ce qui pose de sérieuses questions de sécurité. Le deuxième souci technique de cette méthode est qu’elle suppose que la clé est partagée de façon sécurisée entre Alice et Bob à un moment donné. A minima, cela sous-entend qu’ils doivent se rencontrer de temps en temps pour se donner une série de clés cryptées pour leurs futurs échanges. Il existe plusieurs façons de crypter les messages mais en général, tous les systèmes classiques actuels de cryptage/décryptage vont souffrir de ces inconvénients.

C’est là que la cryptographie quantique peut apporter des solutions.

De l’intrication quantique à la distribution de clés cryptées

L’intrication quantique une forme de « super-corrélation » entre deux systèmes quantiques.

Prenons des pièces truquées de telle façon que si on lance ces deux pièces en même temps, le résultat sera toujours face/face. Il s’agit ici d’une corrélation.

Supposons à présent que les pièces ne sont pas truquées. Alice et Bob en possèdent chacun une. Lorsqu’ils vont lancer ces pièces, ils vont chacun d’entre eux trouver, de façon aléatoire, pile ou face. Les lancers des deux pièces ne sont plus corrélés. Il y a une probabilité de 25 % de tomber sur face/face, ainsi que de tomber sur pile/pile, pile/face, face/pile : les quatre résultats sont équiprobables, contrairement à l’expérience de corrélations où la probabilité de trouver face/face est de 100 % et de 0 % pour les autres options.

Read more: Une brève histoire de l’ordinateur quantique

En revanche, si les deux pièces sont intriquées l’une avec l’autre, elles ne sont pas truquées pour tomber toujours sur face, mais pour tomber toujours du même côté que l’autre pièce. Alice a une probabilité de 50 % de trouver pile et 50 % de trouver face ; de même pour Bob. Mais lorsque Alice et Bob vont comparer leurs résultats sur un grand nombre de lancers de pièce, ils réaliseront que les résultats sont parfaitement corrélés : si la pièce d’Alice est tombée sur pile, celle de Bob aussi, et vice versa (en pratique, on peut préparer les systèmes quantiques pour qu’ils soient corrélés – face/face – ou anticorrélés – pile/face – mais l’idée est la même).

Ce qui est le plus impressionnant (et contre-intuitif), c’est que cette propriété est vraie quelle que soit la distance qui sépare Alice et Bob – et c’est ce phénomène « non-local » qui est à l’origine de la « téléportation » de l’information.’)

L’intrication quantique peut être utilisée pour servir de clé de cryptage. En partageant un système quantique intriqué, seuls Alice et Bob possèdent des corrélations parfaites entre leurs pièces : ils sont surs que cette clé, combinée à un message, ne pourra être décryptée que par eux.

C’est donc la nature quantique de la lumière, qui garantit gratuitement et naturellement la sécurité du système d’échange.

Le photon comme bit d’information

On peut créer des états quantiques sur un photon, ce grain de lumière qui constitue la lumière et qui est intrinsèquement quantique – dans le domaine de l’informatique quantique on parle de « coder des bits quantiques » (ou qubit) d’information. En effet, les photons peuvent être dans deux états de polarisation, qui jouent le rôle des « pile » et « face » des pièces d’Alice et Bob.

C’est précisément ce que John Clauser, dans les années 70, et Alain Aspect, dans les années 80, ont étudié avec leurs équipes : l’intrication « en polarisation » de paires de photons émis par des atomes qui se trouvaient dans une chambre à vide, en utilisant ce que l’on appelle la cascade atomique d’atomes de calcium. Cependant, cette méthode de produire des paires de photons n’est pas simple (d’où le prix Nobel).

Anton Zeilinger et son équipe ont ensuite réussi à créer des paires de photons intriqués en polarisation, mais en utilisant les propriétés de l’optique non-linéaire. Cette expérience n’est pas simple non plus, mais elle est plus facile à mettre en place et a donc permis le développement d’applications beaucoup plus rapidement, notamment dans les communications quantiques (d’où le prix Nobel aussi).

Ces sources de photons intriqués sont indispensables à Alice et Bob pour s’envoyer des messages.

Encore du chemin avant l’Internet quantique

Mais clairement, même s’il existe des entreprises qui vendent des systèmes de cryptographie quantique, même si tout s’accélère rapidement, le rêve d’un Internet quantique n’est pas encore pour demain. Bon nombre d’obstacles restent sur le chemin.

Read more: De l’électron au photon, le silicium fait sa (seconde) révolution

Par exemple, aujourd’hui, les sources les plus sophistiquées permettent au mieux de générer plusieurs millions de paires de photons par seconde, ce qui est encore mille fois moins que ce qu’il faudrait pour vraiment pouvoir déployer ce dispositif quantique.

De plus, l’intrication quantique est un phénomène fragile, ce qui limite toujours la distance sur laquelle on peut la maintenir et donc crypter les communications (avec une distance maximale d’une centaine de kilomètres).

Un peu comme nous avons besoin d’antenne-relai pour transmettre nos messages sur de grandes distances, Alice et Bob vont utiliser des « répéteurs quantiques » pour s’assurer que le signal ne perd pas en intensité et stocker l’information dans des « mémoires quantiques » – qui sont elles aussi des objets très difficiles à fabriquer et contrôler.

Tout cela ne fait que renforcer l’idée que les technologies quantiques restent fascinantes et qu’elles se développeront dans les prochaines décennies à venir, tout comme l’Internet et les fibres optiques se sont déployés dans les quarante dernières années.

Christophe Couteau a reçu des financements de la Région Grand Est, l'Union Européenne et l'ANR.

À l’origine, la cryptographie a pour but de permettre à deux intervenants (traditionnellement dénommés Alice et Bob) d’échanger des messages sans qu’un autre intervenant (traditionnellement appelé Ève) puisse en prendre connaissance. Alice et Bob vont donc se mettre d’accord sur une méthode pour échanger chaque message M sous une forme chiffrée C. Ève peut observer le médium par lequel transitent les chiffrés C, et prendre connaissance de chacun d’entre eux, mais elle ne peut pas retrouver les informations échangées sans la connaissance du secret adéquat, qu’on appelle généralement clé.

C’est un exercice très ancien, puisque l’on parle par exemple du « chiffre de Jules César ». Il a cependant pris une très grande importance ces dernières années, en raison de la nécessité croissante d’échanger des informations. La cryptographie est ainsi devenue un élément essentiel de notre vie quotidienne. Au-delà de l’échange de messages, les mécanismes cryptographiques sont utilisés dans de nombreux objets du quotidien, pour identifier et authentifier les utilisateurs et leurs transactions. On trouve ces mécanismes dans les téléphones, pour chiffrer et authentifier les communications entre le téléphone et les antennes radio, ou encore dans les clés de voiture, les cartes bancaires, etc.

Internet a aussi popularisé le cadenas dans les navigateurs, pour indiquer que les communications entre le navigateur et le serveur sont protégées par des mécanismes cryptographiques. Pour fonctionner correctement, ces mécanismes nécessitent d’utiliser des nombres aléatoires, dont la qualité (plus précisément leur non-prédictibilité) participe à la sécurité des protocoles.

Les algorithmes cryptographiques

Pour transformer un message M en chiffré C par le biais d’un algorithme A, on utilise des clés. Dans les algorithmes dits symétriques, on parle de clés secrètes (Ks), qui sont partagées et gardées secrètes par Alice et Bob. Dans le cadre d’algorithmes asymétriques, on trouve des paires de clés publiques (KPu) et privées (KPr). Pour chaque utilisateur, KPu est connue de tous, alors que KPr doit être conservée précieusement par son possesseur. L’algorithme A est également public, ce qui signifie que le secret de la communication repose uniquement sur le secret des clés (secrètes ou privées).

Parfois, le message M transmis n’est pas important en soi, et le chiffrement d’un message M donné a pour but de vérifier que son correspondant peut le déchiffrer. Cette preuve de la possession de Ks ou KPr peut servir dans certains schémas d’authentification. Dans ce cas, il est important de ne jamais utiliser plusieurs fois le même message M, puisque cela permettrait à Ève de connaître des informations relatives aux clés. Il est donc nécessaire de générer un message aléatoire NA, qui changera à chaque fois qu’Alice et Bob voudront entrer en communication.

L’exemple le plus connu et vraisemblablement le plus utilisé de ce mécanisme est l’algorithme de Diffie-Helman. Cet algorithme permet à un navigateur (Alice) et un site web (Bob) d’obtenir une clé secrète Ks identique, différente à chaque connexion, en ayant échangé leurs KPu respectifs au préalable. Ce processus s’exécute par exemple lors d’une connexion à un site marchand. Cela permet au navigateur et au site web d’échanger des messages chiffrés avec une clé qui sera détruite à la fin de chaque session. Cela signifie qu’on n’a pas besoin de la conserver (simplicité d’utilisation, sécurité car il y a moins de chance de perdre cette clé). Cela implique aussi qu’on ne chiffrera pas beaucoup de trafic avec une même clé, ce qui rend les attaques par cryptanalyse plus difficiles que si on utilise toujours la même clé.

La génération des nombres aléatoires

Pour qu’Ève ne puisse pas obtenir la clé secrète, il est très important qu’elle ne puisse pas deviner le message NA. En pratique, ce message est souvent un grand nombre aléatoire utilisé dans les calculs définis par l’algorithme choisi.

Initialement, la génération d’aléa a été utilisée pour de nombreux travaux de simulation. Pour obtenir des résultats pertinents, il est important de ne pas répéter la simulation avec toujours les mêmes paramètres, mais de répéter la simulation avec des paramètres différents, et ce des centaines voire des milliers de fois. On cherche alors à générer des nombres qui respectent certaines propriétés statistiques et qui ne permettent pas de différencier la suite de nombres d’une suite qui serait obtenue par des tirages de dés, par exemple.

Pour générer un nombre aléatoire NA utilisable dans ces simulations, on utilise généralement des générateurs dits pseudo-aléatoires, qui appliquent un algorithme de retraitement à une valeur initiale, dénommée « semence ». Ces générateurs pseudo-aléatoires ont pour but de produire une suite de nombres qui ressemble à une suite aléatoire, d’après ces critères statistiques. Cependant, en utilisant deux fois la même semence, on obtient deux fois la même suite.

L’algorithme du générateur pseudo-aléatoire est généralement public. Si un attaquant est capable de deviner la semence, il est capable de générer la séquence aléatoire, et donc d’obtenir les nombres aléatoires utilisés par les algorithmes cryptographiques. Dans le cas précis de la cryptographie, l’attaquant n’a même pas nécessairement besoin de connaître exactement la valeur de la semence. S’il est capable de deviner un ensemble de valeurs, cela suffit pour calculer rapidement toutes les clés possibles et casser le chiffrement.

Dans les années 2000, les programmeurs ont utilisé des semences qui pouvaient être facilement devinées, basées sur le temps par exemple, rendant les systèmes vulnérables. Depuis, pour éviter cette capacité à deviner la semence (ou un ensemble de valeurs de cette semence), les systèmes d’exploitation se basent sur un mélange d’éléments physiques du système (température du processeur, connexions sur le bus, etc.). Ces éléments physiques sont impossibles à observer pour un attaquant, varient fréquemment, et donc forment une bonne source de semence pour les générateurs pseudo-aléatoires.

Quid des vulnérabilités ?

Bien que le domaine soit aujourd’hui bien compris, les générateurs de nombres aléatoires font encore parfois l’objet de vulnérabilités. Ainsi, entre 2017 et 2021, les chercheurs en cybersécurité ont trouvé 53 failles de ce type (CWE-338). Cela ne représente qu’un petit nombre des failles logicielles (moins de 1 pour 1 000). Plusieurs de ces failles sont cependant de niveau élevé ou critique, indiquant qu’elles peuvent être assez facilement utilisées par des attaquants, et qu’elles sont largement répandues.

Un exemple emblématique en 2010 est l’erreur de Sony sur le système de signature des logiciels de la PS3. Dans ce cas, la réutilisation d’un aléa pour deux signatures distinctes a permis à un attaquant de retrouver la clé privée du fabricant : il devient alors possible d’installer n’importe quel logiciel sur la console, y compris des logiciels piratés ou des malwares.

Sur la période 2017-2021, des failles ont également touché des composants physiques : les processeurs Intel Xeon, les puces Broadcom utilisées pour les communications, et les processeurs Qualcom SnapDragon embarqués notamment dans les téléphones portables. Ces failles affectent la qualité de la génération des nombres aléatoires. Par exemple, CVE-2018-5871 et CVE-2018-11290 concernent un générateur de semence dont la périodicité est trop courte, c’est-à-dire qui répète la même suite de semences rapidement. Ces failles ont été corrigées et elles ne touchent que certaines fonctions du matériel, ce qui limite le risque.

La qualité de la génération des nombres aléatoires est donc effectivement un problème de sécurité. Les systèmes d’exploitation s’exécutant sur des processeurs récents (moins de 10 ans) disposent de mécanismes de génération de nombres aléatoires basés sur le matériel. Cela permet en général d’assurer une bonne qualité de ceux-ci et donc un bon fonctionnement des algorithmes cryptographiques, même si des vulnérabilités ponctuelles peuvent survenir. En revanche, la difficulté est spécialement marquée du côté des objets connectés, dont les capacités matérielles ne permettent pas d’implémenter des générateurs aléatoires aussi performants que ceux disponibles sur ordinateurs et smartphones, et qui s’avèrent souvent plus vulnérables.

Hervé Debar a reçu des financements de l'Agence Nationale de la Recherche (ANR), de l'Agence Innovation Défense (AID), de BPI France et de l'Union Européenne.

Olivier Levillain a reçu des financements de l'Agence Nationale de la Recherche (ANR), de l'Agence Innovation Défense (AID) et de l'Union Européenne.

Les ordinateurs sont de bien utiles compagnons : ils permettent de résoudre de nombreux problèmes auxquels nous sommes confrontés. Fort heureusement, il existe aussi des problèmes hors d’atteintes pour ces derniers. Pensons à nos cartes bleues : il serait problématique qu’un ordinateur soit en mesure de retrouver notre code… C’est justement la menace que fait désormais peser l’ordinateur quantique, un nouveau type d’ordinateur actuellement en conception et reposant sur les lois de la physique quantique.

Heureusement, ce nouvel ordinateur ne signe pas pour autant la fin de la sécurité liée à nos cartes bleues, et de façon plus générale la sécurité numérique. Il existe en effet des problèmes difficiles même pour un ordinateur quantique. La cryptographie post-quantique propose justement de les étudier et de les exploiter afin d’assurer notre sécurité numérique de demain !

Tasse, algorithmes et cryptographie

Nos vies sont aujourd’hui rythmées par les ordinateurs. La raison du succès de ces machines modernes est plutôt simple : elles nous aident à résoudre rapidement de nombreux problèmes du quotidien. Par exemple, étant donné une carte routière ou géographique, comment trouver le chemin le plus court pour aller d’un point A à un point B ? La réponse est finalement plutôt simple : posons la question à notre smartphone ! Ces petits ordinateurs peuvent calculer très rapidement « tous » les chemins possibles et donc nous répondre instantanément. Dès lors, il n’y a plus qu’un pas pour penser que nos compagnons peuvent résoudre presque tout problème imaginable…

Malheureusement, il n’en est rien. Les ordinateurs s’avèrent même extrêmement rapidement limités. Prenons une tasse de café tombant de notre main un matin. Notre smartphone pourra-t-il prédire en combien de morceaux notre tasse favorite va-t-elle se casser ? La tâche semble difficile, même avec une application dédiée. En effet, réaliser une telle simulation demanderait un temps bien trop important à notre téléphone et même un supercalculateur n’y suffirait pas : le nombre de dimensions impliquées dans ce problème est bien trop élevé.

La solution n’est pas à chercher non plus du côté de l’évolution technologique. Même si nous dépassons les espérances de la fameuse Loi de Moore (qui prédit un doublement de notre puissance de calculs tous les deux ans), il faudrait encore attendre des centaines d’années avant d’être en mesure de donner une réponse satisfaisante à notre problème. À l’inverse, nous avons un moyen simple d’y répondre sans avoir recours à la technologie : il suffit de se baisser et de compter les morceaux. Un exercice certes fastidieux, mais qui paraît dans nos cordes…

Cette métaphore de la tasse est inspirée d’une vidéo de Richard Borcherds, médaille Fields, en réaction aux récentes annonces de suprématie quantique, c’est-à-dire la réalisation par un ordinateur quantique d’une tâche inaccessible à un ordinateur classique (ce dont nous reparlerons un peu plus loin).

Or, le fait qu’il existe des problèmes qu’un ordinateur, et même tous les ordinateurs terrestres réunis, n’est pas en mesure de résoudre en un temps raisonnable est le principe fondateur d’une grande partie de la cryptographie moderne, science du secret nous permettant la sécurité numérique. Il existe quantité de problèmes qui sont présumés appartenir à cette catégorie, les plus célèbres dans le cadre de la cryptographie étant ceux dits de la factorisation des entiers et du logarithme discret. Un pan entier de la sécurité numérique repose sur leur difficulté, comme les cartes bleues, nos mises à jour logiciel…

L’écueil des ordinateurs quantiques

Malheureusement, les avancées en physique quantique laissent entrevoir l’arrivée d’un nouvel outil qui pourrait bouleverser l’ordre établi : l’ordinateur quantique. Cet ordinateur « nouvelle génération », n’ayant pas grand-chose à voir avec nos ordinateurs, fonctionnerait en remplaçant les bits, ces 0 et ces 1 qui constituent le langage universel de toutes les machines autour du globe, par des qubits, objets issus des principes de la physique quantique et qui représentent à la fois un 0 et un 1 en « superposition ».

Cette différence fondamentale offre de nouvelles possibilités algorithmiques puissantes, comme l’a démontré P. Shor en 1994, en prouvant qu’un ordinateur quantique fonctionnel (c’est-à-dire un ensemble de qubits sur lequel on serait capable d’effectuer un certain nombre d’opérations prédéfinies) était en mesure de résoudre les problèmes de la factorisation et du logarithme discret bien plus efficacement que ne le pourrait jamais un ordinateur classique. Adieu nos cartes bleues ! Depuis, d’autres domaines où les ordinateurs quantiques pourraient s’avérer révolutionnaires ont été découverts, de façon plus positive cette fois. C’est par exemple le cas de la chimie où le calcul quantique pourrait permettre d’améliorer la modélisation des états d’une molécule.

Aujourd’hui, nous sommes encore loin d’avoir un ordinateur quantique fonctionnel : ces fameux qubits sont difficiles à manipuler et la route est encore longue à la fois sur le plan théorique et pratique. Les annonces de suprématie quantique dont nous parlions plus haut, c’est-à-dire la réalisation d’une tâche avec un ordinateur quantique qui est hors d’atteinte de nos ordinateurs du quotidien, concernaient en réalité des problèmes qui avaient été spécialement conçus dans le but même d’être plus faciles pour un ordinateur quantique que pour un ordinateur classique. Les applications prometteuses des ordinateurs quantiques, par exemple casser notre sécurité numérique, restent pour l’instant hors de portée des acteurs les plus avancés.

Les efforts investis dans la poursuite de la suprématie quantique sont cependant à la hauteur de la tâche, et une véritable course est lancée entre les grands acteurs du domaine, comme Google ou IBM. La menace n’est donc pas à prendre à la légère pour les cryptographes : on pourrait bien voir arriver un ordinateur quantique fonctionnel d’ici une dizaine d’années.

La cryptographique post-quantique

« Est-ce donc la fin de la cryptographie ? » pourrait-on alors se demander. Fort heureusement, la réponse à cette question est sans doute non. Car tout comme les ordinateurs classiques, les ordinateurs quantiques ne sont pas tout-puissants. C’est précisément le postulat sur lequel se fonde une nouvelle branche de la cryptographie : la cryptographie post-quantique. Celle-ci a pour but d’étudier de nouveaux problèmes mathématiques qui seraient durs à la fois pour les ordinateurs classiques, mais aussi pour les ordinateurs quantiques.

Récemment, le NIST, institut de standardisation américain, a lancé une compétition dans le but d’identifier et de standardiser les candidats prometteurs. Après plusieurs tours d’écrémage successif, la compétition va bientôt arriver à son terme et l’annonce des premières solutions soumises à la standardisation devrait tomber dans les mois à venir. De la multitude de propositions initiales ont émergées plusieurs grandes familles, dont les plus notables sont sans doute les cryptographies à base de réseaux euclidiens et de codes correcteurs, mêlant efficacité, compacité et bonne expérience des problèmes mathématiques sous-jacents.

Cependant, en cryptographie traditionnelle comme post-quantique, rien n’est gravé dans le marbre. On ne peut pas exclure la possibilité de voir, demain ou dans six mois ou un an, arriver un groupe d’individus avec un nouvel algorithme qui permettrait de casser un problème sur lequel se fonde la cryptographie post-quantique. Nous en avons eu la preuve récemment avec l’un des protocoles finalistes de la compétition du NIST, dont la sécurité vient d’être sérieusement remise en cause par une nouvelle attaque, prouvant que la sécurité numérique induite par un tel système ne serait pas assurée.

Ceci est d’autant plus vrai que la cryptographie post-quantique doit se prémunir d’une menace encore plus sérieuse : les ordinateurs quantiques eux-mêmes ! Or nous sommes bien loin d’avoir compris toutes les possibilités de ces nouvelles machines. Cela justifie le besoin d’avoir des solutions de repli et c’est pour cela que d’autres familles d’objets mathématiques tels que les systèmes multivariés ou encore les isogénies sont aussi étudiées de très près.

En résumé, l’établissement de notre future sécurité numérique soulève encore de nombreuses questions ! Comme cela est illustré par l’appel du NIST, les scientifiques sont à pied d’œuvre pour proposer des solutions à la fois sûres et efficaces, prêtes à être déployées sur nos ordinateurs et smartphones dans les prochaines années.

Thomas Debris-Alazard a reçu des financements de l'Agence Nationale de la Recherche (ANR JCJC COLA) pour ses travaux en cryptographie post-quantique

Antonin Leroux does not work for, consult, own shares in or receive funding from any company or organization that would benefit from this article, and has disclosed no relevant affiliations beyond their academic appointment.

Le mot « algorithme » est utilisé couramment dans la presse pour désigner le fonctionnement opaque des moteurs de recherche et des réseaux sociaux.

Mais de quoi parlons-nous exactement ? Qu’est-ce qu’un algorithme ? Cette notion a traversé l’histoire, depuis Euclide jusqu’aux algorithmes des GAFAM. Les algorithmes peuvent-ils résoudre n’importe quel problème ? Quelles garanties a-t-on sur leur comportement ? Quels sont leurs impacts sociétaux ?

Au IX^e siècle, en Perse

L’étymologie fait remonter l’histoire des algorithmes au savant persan Muhammad Ibn Mūsā al-Khuwārizmī, qui aux alentours de l’an 800 a publié les premiers manuels de résolution d’équations. Ses méthodes, à l’origine de l’algèbre, concernent typiquement des problèmes de calcul pratiques : des questions d’héritage ou de mesure.

Ses ouvrages sont traduits en latin au cours du XII^e siècle et popularisés par des personnalités telles que le mathématicien italien Leonardo Fibonacci. C’est son nom, latinisé en « algoritmi » ou « algorismi », qui est à l’origine du terme « algorithme ». Près d’un millénaire avant lui, Euclide avait décrit dans les Éléments une méthode pour calculer le plus grand diviseur commun de deux nombres.

Au XX^e siècle, la notion d’algorithme construit des branches des mathématiques

Il faut pourtant attendre le début du XX^e siècle pour que la notion d’algorithme soit formalisée. Dans son célèbre discours au deuxième congrès international des mathématiciens à Paris en 1900, le mathématicien allemand David Hilbert propose 23 problèmes ouverts, 23 défis à relever pour la communauté mathématique, dont les énoncés auront une influence considérable sur le développement des mathématiques dans les décennies suivantes. Le dixième problème porte sur l’existence d’une « méthode par laquelle, au moyen d’un nombre fini d’opérations, on pourra déterminer l’existence d’une solution en nombres entiers à une équation polynomiale à coefficients entiers » (les équations « Diophantiennes »). C’est bien de l’existence d’un algorithme qu’il s’agit.

C’est par les travaux fondateurs d’Alan Turing et d’Alonzo Church, entre autres, que les algorithmes deviennent des objets mathématiques à part entière. Dans son article de 1936, Alan Turing donne sa définition de la « calculabilité » d’une fonction : il doit exister une machine qui donne sa valeur en un nombre fini d’étapes élémentaires, guidées par un système de transitions et le contenu d’un ruban, qui joue le rôle de mémoire. C’est la célèbre « machine de Turing ».

Alan Turing comprend le lien entre la calculabilité d’une fonction et le caractère démontrable d’une assertion mathématique dans un système d’axiomes. L’informatique théorique devient une branche des mathématiques.

On circonscrit la puissance des algorithmes, et certains problèmes sont démontrés indécidables : aucun algorithme n’existe pour les résoudre. En 1970, Julia Robinson et Youri Matiiassevitch résolvent finalement le dixième problème de Hilbert : la résolution des équations diophantiennes est un problème indécidable !

Au cours des années 1970, on établit des hiérarchies de problèmes en fonction du temps et de l’espace qu’un algorithme requiert pour les résoudre : c’est la théorie de la complexité.

Comment se présente un algorithme ?

Les algorithmes sont souvent comparés à des recettes de cuisine : une suite d’instructions précises permettant d’obtenir un résultat en un nombre fini d’étapes.

Cette image est juste, mais occulte sans doute un aspect fondamental, le fait qu’un algorithme reçoit des données à traiter (nombres, texte, relations), et certaines instructions sont conditionnelles : les étapes suivies dépendent de ces données, et les exécutions peuvent suivre un cours difficilement prévisible. On peut donner ces instructions sous différentes formes bien définies (organigramme, langage de description), ou même, avec les précautions de rigueur, en langage naturel.

Nous avons tous appris l’algorithme de multiplication de deux nombres à l’école primaire, sans l’aide d’un formalisme avancé. Les algorithmes sont en principe destinés à être mis en œuvre sous forme de programme, dans un langage de programmation compréhensible par un ordinateur. Mais l’algorithme existe indépendamment de cette traduction.

Pour cerner la portée des algorithmes dans nos vies modernes, il faut distinguer leurs familles

Pour mieux comprendre les enjeux et les défis actuels autour des algorithmes, il est important de cerner leur portée et les propriétés que nous sommes à même de garantir sur leurs résultats et leurs comportements. Une typologie des algorithmes est indispensable à cette compréhension.

On peut d’abord distinguer une famille d’algorithmes tellement omniprésents dans notre quotidien qu’ils y sont presque devenus invisibles. Il s’agit d’algorithmes exacts pour des tâches parfaitement bien définies, dont le résultat est facilement vérifiable : multiplier deux nombres, trier une liste de noms par ordre alphabétique, stocker et retrouver efficacement une information, effectuer la conversion d’un signal analogique vers un signal numérique, interpréter un programme.

Il s’agit là des algorithmes fondamentaux étudiés depuis les balbutiements des sciences informatiques. Ils ne font pas moins pour autant l’objet de recherches actuelles, tant des mystères subsistent autour de la complexité de certaines opérations fondamentales. La complexité exacte du problème de multiplication de deux nombres entiers, par exemple, est d’un point de vue théorique encore ouverte : nous sommes actuellement incapables de démontrer que la multiplication prend nécessairement plus de temps que l’addition ! Le meilleur algorithme de multiplication connu n’a été publié que très récemment.

Les algorithmes d’optimisation constituent une deuxième famille importante. Ils résolvent des problèmes dans lesquels on cherche à identifier des paramètres ou une configuration qui maximise ou minimise une valeur, appelée « fonction objectif ». Les applications concrètes consistent par exemple en la recherche d’un chemin le plus court entre deux points, l’ordonnancement des phases d’un projet pour en minimiser la durée, le choix des emplacements d’antennes pour couvrir à moindre coût une zone donnée, ou celui des paramètres des routeurs d’un réseau pour en minimiser la latence.

Les objectifs des algorithmes de ces deux familles sont quantifiables et leurs résultats sont mathématiquement garantis. Les méthodes formelles permettent de vérifier rigoureusement les propriétés d’un algorithme. Les algorithmes d’optimisation linéaire sont bien compris.

Une troisième famille d’algorithmes, plus spécialisés, est celle des algorithmes cryptographiques, destinés à garantir la sécurité des communications et transactions. Cette sécurité repose souvent sur des hypothèses liées à la complexité de problèmes algorithmiques. Le célèbre algorithme RSA (du nom de ses inventeurs : Ronald Rivest, Adi Shamir et Leonard Adleman), par exemple, fait reposer la sécurité des transactions commerciales électroniques sur l’hypothèse qu’il n’existe pas d’algorithme efficace pour décomposer un nombre en ses facteurs premiers.

Certaines procédures issues des recherches en intelligence artificielle, en revanche, ne se soumettent pas facilement à une analyse rigoureuse.

Les algorithmes changent de nature avec l’intelligence artificielle

Parmi ceux-ci, les algorithmes de classification cherchent à placer les données reçues en entrée dans une catégorie correspondant à une réalité extérieure. Un algorithme de reconnaissance d’animaux, par exemple, recevra en entrée une image sous forme d’un tableau de pixels, et devra déterminer si cette image représente plutôt un chat ou un dauphin. Cette tâche n’est pas formellement bien définie : on peut probablement trouver une image ambiguë pour laquelle les réponses fournies par des humains pourraient être différentes. Le caractère correct de ces algorithmes dépend d’une réalité extérieure, qui n’est pas formalisée, et leur exactitude, ou précision, ne peut être établie qu’expérimentalement.

De la même manière, les algorithmes de prédiction cherchent à anticiper l’évolution de certaines quantités mesurées dans le monde physique, ou des comportements dans une population. Ils sont utilisés par exemple en finance pour prédire l’évolution des marchés, ou en marketing, pour présenter aux visiteurs d’un site web les produits ou publicités les plus susceptibles d’attirer leur attention. La pertinence des résultats est ici encore validée empiriquement, et non mathématiquement. À tel point qu’en 2006, la société Netflix a lancé un concours pour améliorer les performances de son algorithme de prédiction d’évaluations de films, avec un prix d’un million de dollars à la clé.

Le développement des ces algorithmes fait massivement appel à des modèles probabilistes, mais aussi à des structures difficilement analysables rigoureusement. C’est le cas en particulier pour les algorithmes de réseaux de neurones artificiels utilisés dans ce qu’on appelle désormais l’« apprentissage profond », en référence au nombre de couches utilisées dans ces réseaux. Ces réseaux encodent implicitement la mémoire des données fournies lors d’une phase d’apprentissage, et permettent de classifier de nouvelles données en entrée.

À lire aussi : Intelligence artificielle : les défis de l’apprentissage profond

Que pouvons-nous exiger des algorithmes ?

L’omniprésence des algorithmes fait légitimement l’objet de craintes. Quelles sont les garanties que nous pouvons exiger ?

Un premier type de garantie porte sur l’efficacité. Combien de temps doit-on attendre pour avoir une réponse ? De quelle quantité de mémoire doit-on disposer ? Ces questions sont bien étudiées et ont des formulations et des réponses rigoureuses, mais partielles. Les lacunes dans notre compréhension de la complexité algorithmique laissent en particulier ouverte la possibilité d’attaques inédites mettant en péril la cryptographie basée sur l’algorithme RSA.

La question traditionnelle des performances est intimement liée aux questions de consommation de ressources, qui ont des impacts écologiques. On peut donner à cette question un cadre plus large, et s’interroger sur les ressources consommées par les logiciels, les serveurs. Dans le domaine des algorithmes cryptographiques, certains mécanismes au cœur du fonctionnement des cryptomonnaies, en particulier le principe de la « preuve de travail », ont un impact énergétique dramatique.

À lire aussi : Krach du bitcoin : cybercriminalité et surconsommation d’électricité, la face cachée des cryptomonnaies

Lorsque les objectifs sont facilement vérifiables, comme dans le cas d’un algorithme de tri, ou quantifiés explicitement, comme dans le cas d’un algorithme d’optimisation, il existe une mesure objective de la qualité de la solution. Dans le cas des algorithmes d’optimisation, cependant, le choix de la fonction objectif, la quantité que l’on optimise, peut avoir un impact humain considérable.

Des questions d’éthique

Les questions d’équité et de transparence des algorithmes de classification et de prédiction deviennent pressantes. Dans un ouvrage devenu classique, Cathy O’Neil alerte sur les dérives des systèmes de prise de décision dans les domaines de la justice, de l’action policière, des assurances, de l’évaluation des enseignants, entre autres.

L’algorithme de Gale-Shapley, utilisé par la plate-forme Parcoursup satisfait des propriétés d’optimalité, mais garantit également qu’un comportement stratégique de la part des postulants est impossible.

Les méthodes d’apprentissage supervisé pour la classification consistent classiquement en une collection d’exemples, de paires « entrée-sortie », dont on espère qu’ils peuvent être généralisés, de façon qu’une nouvelle donnée en entrée puisse être associée à une réponse en sortie qui fasse sens. En ne fournissant que des exemples connus lors de ces phases d’apprentissage, on inculque au système tous les biais présents de facto dans les exemples dont on dispose, et l’on apprend ainsi à la machine à les reproduire. C’est le thème du documentaire Coded Bias, relatant l’expérience d’une étudiante du MIT avec les algorithmes de reconnaissance faciale.

À lire aussi : Emploi, sécurité, justice : d’où viennent les « biais » des IA et peut-on les éviter ?

Le caractère parfois inexplicable des résultats termine d’expliquer le glissement sémantique récent du mot algorithme : de simple méthode de calcul, l’algorithme est perçu comme une boîte noire omnipotente, dont le fonctionnement interne est inaccessible, et dont les réponses finissent par se substituer à la réalité. Cette perception s’explique notamment par la résurgence des méthodes de réseaux de neurones, dont la complexité défie toute analyse formelle. Les succès expérimentaux dans les tâches confiées aux réseaux profonds sont indéniables et fascinants. Mais certaines expériences mettent en évidence leur fragilité : des chercheurs ont montré qu’en modifiant de manière imperceptible quelques pixels bien choisis d’une image, on peut changer du tout au tout la réponse fournie. En l’absence d’explicitation de la réponse (« c’est un chat, car il a des oreilles pointues et des moustaches »), les questions de confiance et de responsabilités se posent.

À lire aussi : Peut-on faire confiance aux IA ?

La communauté de recherche en intelligence artificielle et en apprentissage automatique s’est emparée des questions d’équité et d’explicabilité : le développement de méthodes d’apprentissage incluant des critères d’équité (fairness in AI) est en plein essor, tandis que le domaine de l’intelligence artificielle « explicable » (explainable AI) traite de la justification des résultats et de la confiance.

Al-Khuwārizmī aurait sûrement été surpris de la postérité de son patronyme !

Jean Cardinal ne travaille pas, ne conseille pas, ne possède pas de parts, ne reçoit pas de fonds d'une organisation qui pourrait tirer profit de cet article, et n'a déclaré aucune autre affiliation que son organisme de recherche.

« Retour sur… », un podcast pour décrypter l’actualité avec les expert·e·s.

Le 21 janvier 2021, Emmanuel Macron annonçait la mise en place du Plan Quantique National : 1,8 milliard d’euros destinés à accélérer les transformations de l’industrie et de la recherche informatique.

Nous faisons le point avec Eleni Diamanti, chercheuse CNRS au Laboratoire d’informatique de Sorbonne Université et au Paris Center for Quantum Computing.

Des capteurs aux ordinateurs en passant par la cryptographie, Eleni Diamanti explore avec nous la maturité des différentes technologies quantiques, dont certaines sont déjà utilisées actuellement, et nous explique quand les autres pourraient être déployées.

Pour aller plus loin, nous vous recommandons les articles suivants :

• Quand les technologies quantiques prennent le large, de Malo Cadoret et Jeanne Bernard, du CNAM.

• Au XXIᵉ siècle, la lumière s’invite dans les nouvelles technologies, d’Azzedine Boudrioua, de l’Université Sorbonne Paris Nord.

• L’ordinateur quantique, pour bientôt ?, de Jacques Baudron, de l’Université Paris-Saclay.

Conception, Elsa Couderc. Production, Romain Pollet.

Les auteurs ne travaillent pas, ne conseillent pas, ne possèdent pas de parts, ne reçoivent pas de fonds d'une organisation qui pourrait tirer profit de cet article, et n'ont déclaré aucune autre affiliation que leur organisme de recherche.

Une solution pour protéger son argent contre le vol est de le mettre dans un coffre-fort, basé sur la solidité du coffre et du mécanisme de protection, par exemple un cadenas et une clé. Vous ouvrirez le coffre… si vous avez la bonne clé.

En informatique, un cryptosystème est l’équivalent du coffre-fort : basé sur la solidité d’un mécanisme de protection dit « cryptographique » et la connaissance d’une donnée particulière que l’on appelle également « clé ». Ce système sert à protéger des données stockées ou échangées, par exemple des informations d’identité, bancaires ou empreinte digitale.

Lorsqu’on essaie de déchiffrer un message en cachette parce qu’on ne connaît pas la clé, on fait de la « cryptanalyse » : c’est la manière utilisée pour mettre en défaut un cryptosystème, c’est-à-dire de l’attaquer.

Comment marche une carte à puce ?

Les premiers mécanismes cryptographiques que l’on connaît remontent à l’Antiquité. Ces mécanismes visaient à garantir la confidentialité des messages échangés en temps de guerre : pour éviter qu’un adversaire ne les lise, ceux-ci étaient préalablement chiffrés. À cette époque, le chiffrement et le déchiffrement pouvaient être effectués « à la main » par une personne possédant l’information secrète et la clé pour la déchiffrer. Pour les cryptosystèmes les plus anciens, la clé pouvait être par exemple un bâton du bon diamètre, la « scytale »,

ou un simple code secret, comme le chiffre « pigpen » des francs-maçons.

L’histoire des codes secrets a beaucoup évolué au fil du temps, et de nos jours le chiffrement d’un message ne se fait plus « à la main », mais nécessite la puissance de calcul des ordinateurs et sa fiabilité est assurée par des principes mathématiques prouvés. Les clés secrètes sont devenues des séquences de plusieurs centaines, voire milliers de bits… c’est-à-dire un nombre de plus de mille chiffres.

L’évolution de la cryptographie a également permis de répondre à d’autres besoins de nos temps modernes : la confidentialité permet d’assurer que l’information ne soit pas divulguée, l’intégrité permet d’assurer qu’elle n’est pas modifiée, l’authentification permet d’assurer que la communication s’effectue avec la bonne personne ou le bon système et la non-répudiation empêche de nier le fait d’avoir bien été l’auteur d’un certain message.

Par exemple, lorsque nous effectuons un achat dans une boutique, nous souhaitons autoriser une transaction du bon montant, de notre compte vers celui du bon marchand, tout en gardant inaccessibles nos informations privées. Le marchand lui, souhaite être payé par le bon client, et ne souhaite pas que quelques minutes plus tard le client puisse nier d’avoir effectivement payé. La carte bancaire qui effectue des communications chiffrées avec le terminal du marchand joue un rôle important dans l’affaire, permettant de garantir une bonne partie de ces besoins.

La carte à puce, grâce à sa mémoire interne et sa capacité de calcul autonome, peut être en effet utilisée comme cryptosystème. Elle peut stocker des clés, ainsi que toute sorte de donnée électronique, et, une fois connectée à un terminal qui l’alimente en énergie, elle a la capacité d’effectuer des calculs cryptographiques.

C’est en réalité un petit ordinateur intégré dans une puce de quelques millimètres carrés. C’est pour cela qu’on l’appelle « système embarqué ».

Des failles dans le coffre-fort

Malgré tout, cela n’est pas toujours suffisant. Posséder un bon coffre-fort n’a pas d’intérêt, si sa combinaison traîne sur un papier posé à côté ou si la clé du cadenas est juste glissée sous le paillasson.

Il peut aussi exister des failles dans un cryptosystème si tout n’a pas été bien pensé. Afin d’assurer la confiance dans leur produit, les développeurs de cartes à puce demandent un certificat auprès d’un organisme de confiance. L’Agence Nationale de la Sécurité des Systèmes d’Information (ANSSI) est le schéma de certification étatique français, mais il existe aussi des schémas dans d’autres pays, ainsi que des schémas privés. Le certificat est attribué au développeur sur la base d’un rapport technique d’évaluation.

Le développeur s’adresse donc à un laboratoire comme le nôtre, le le CESTI du CEA-Leti situé à Grenoble, constitué d’une équipe d’experts aux compétences complémentaires – les « évaluateurs » – qui va plancher sur la sécurité du système embarqué dans son ensemble, afin de vérifier que tout a bien été pensé et qu’aucune faille n’existe. Aujourd’hui, les systèmes embarqués sont présents dans beaucoup d’applications, telles que les clés de voiture, les badges d’accès ou les cartes de transport, mais seules les cartes à puce ayant un certificat de bon niveau sont susceptibles d’être utilisées dans des marchés à haut risque, par exemple les cartes bancaires ou les passeports électroniques. Les évaluateurs s’assurent aussi que le produit est conforme aux spécifications et que le système n’a pas de faille de conception : cela revient à s’assurer que le métal du coffre-fort a la bonne épaisseur et que la combinaison est assez complexe par exemple.

Quelles stratégies pour attaquer un cryptosystème ?

Mais ce n’est pas tout. La fiabilité dépend aussi de l’environnement du cryptosystème. Posséder un bon coffre-fort n’a pas d’intérêt, si un attaquant près du coffre est capable de faire exploser la porte à l’aide de dynamite, ou d’écouter les sons émis par la gâchette de la serrure avec un stéthoscope. Il faudrait soit garantir que le coffre-fort est bien enfermé et inaccessible, soit montrer qu’il peut résister à toutes les attaques d’un adversaire déterminé et très inventif.

Dans le cas d’un système embarqué tel que la carte à puce, il est difficile de s’assurer de son caractère inatteignable. En effet, tout le monde a dans sa poche une carte bancaire, une carte vitale ou un passeport. Une carte à puce même bien protégée est un objet qui circule dans un monde potentiellement hostile, où un attaquant peut décider d’« exploser sa carte » ou d’« écouter les sons émis par la puce ». Un pirate moderne utilisera plutôt un laser pour perturber le bon fonctionnement de la puce et obtenir des effets non appropriés, tandis que la mesure du courant de consommation via un oscilloscope remplacera avantageusement le stéthoscope. Avec un peu de finesse, ces techniques peuvent s’avérer payantes.

Les attaques connues sur les cartes à puce sont classées en deux catégories : les attaques logicielles, où l’adversaire utilise les bogues du système, et les attaques physiques, par perturbation ou par observation, où il a la possibilité d’agir sur l’environnement du système.

Imaginons par exemple qu’une carte bancaire vérifie que le code PIN saisi par un utilisateur soit correct : interrompre cette vérification grâce à un faisceau lumineux (le fameux laser), qui va perturber la puce au bon moment, peut faire accepter par la carte n’importe quel PIN. C’est une attaque « par perturbation ».

Un peu plus discrète, une attaque « par observation » va par exemple consister à mesurer le temps de réaction de la puce lorsqu’elle vérifie le fameux PIN : imaginons que la vérification s’arrête quand le premier chiffre du PIN saisi est faux (pas la peine de vérifier les chiffres suivants !), elle mettra alors plus de temps si seul le dernier chiffre est faux. Le temps de réponse aidera l’attaquant à trouver le bon PIN.

Dans le même esprit d’« observation », la consommation de puissance d’une puce peut être mesurée à l’aide d’un oscilloscope pendant qu’elle effectue un calcul cryptographique complexe : la puce consomme plus ou moins selon la nature du calcul qui est exécuté. Lorsque ce calcul utilise des morceaux de clé, la consommation varie suivant les valeurs de ces morceaux qu’on peut donc deviner en observant la consommation.

En tant qu’évaluatrices de la sécurité d’une carte à puce, nous nous mettons dans la peau d’un hypothétique attaquant et nous tentons d’imaginer toutes les façons d’accéder au cryptosystème et de le mettre en défaut.

The authors do not work for, consult, own shares in or receive funding from any company or organisation that would benefit from this article, and have disclosed no relevant affiliations beyond their academic appointment.

L’intrication quantique a été découverte par hasard. En essayant de démontrer que la théorie quantique était incomplète, Einstein et des collègues inventèrent une expérience qui fut réalisée un demi-siècle plus tard, et qui ouvrit la voie aux développements technologiques que nous poursuivons toujours aujourd’hui.

Au début du XX^e siècle, la physique quantique venait à peine de naître et ses bases étaient encore fragiles. Les physiciens construisaient à grands pas une nouvelle théorie visant à décrire les atomes et tous les phénomènes à l’échelle microscopique, mais cette théorie s’accompagnait d’un lot de surprises et de conséquences inattendues pour des esprits habitués à la logique scientifique du XIX^e siècle. Il apparaissait notamment que les grandeurs physiques, comme la position d’une particule, ne pouvaient en général pas être connues exactement : seules les probabilités de prendre telle ou telle valeur pouvaient être prédites par la théorie. Par exemple, on ne peut pas prévoir qu’un atome se trouve ici ou là, mais seulement qu’il a une probabilité 1/3 de se trouver ici, et 2/3 de se trouver là. Le plus surprenant, c’est que ce défaut de prédictibilité n’est pas la conséquence d’une éventuelle difficulté pratique à mesurer la grandeur avec grande précision, mais bien une authentique impossibilité fondamentale de lui attribuer une valeur précise. Albert Einstein, que cet indéterminisme quantique heurtait profondément, avait lancé la phrase restée célèbre « Dieu ne joue pas aux dés ».

Une tentative de démonstration par l’absurde que la théorie quantique est incomplète

En 1935, avec Boris Podolsky et Nathan Rosen, Einstein écrit un article qui vise à démontrer par l’absurde que la théorie quantique est, en l’état, incomplète : il manque encore un pan de la théorie qui devrait permettre de rétablir le déterminisme et de donner une valeur comme il se doit à toute grandeur physique susceptible d’être mesurée. L’article des trois savants présente une « expérience de pensée », le scénario d’une situation dans laquelle deux particules manifestent la propriété surprenante d’intrication quantique : tout en étant situées à distance l’une de l’autre, la mesure de l’une d’elle (par exemple la mesure de sa position) semble avoir un effet instantané sur l’autre. En exploitant cette bizarrerie, les savants montrent qu’il apparaît possible d’attribuer une valeur précise à la fois à la position et à la vitesse d’une particule par la mesure de l’autre, là où la théorie quantique l’interdit en vertu du fameux principe d’incertitude de Heisenberg. Ils en concluent que cette théorie devrait donc être complétée, sans quoi elle induirait un « dommage collatéral » : l’intrication quantique.

Einstein reste en particulier perplexe devant l’éventuelle « action à distance » entre deux particules intriquées, qui porte atteinte à la localité des lois de la nature, un principe physique qui lui est cher. En effet, pour Einstein, on doit pouvoir définir toutes les grandeurs physiques localement, en chaque point de l’espace, indépendamment de ce qui se passe ailleurs.

L’intrication quantique existe bel et bien – c’est démontré par Alain Aspect et son équipe

Pendant plusieurs décennies, l’intrication quantique reste un concept négligé par la plupart des physiciens car il n’affecte pas le développement fulgurant et les nombreux succès de la physique quantique. Même lorsque John Bell identifie en 1964 une éventuelle façon de confirmer ou d’infirmer cette singularité quantique par une expérience, ce n’a que peu de répercussions. Mais finalement, après une première tentative par Stuart Freedman and John Clauser en 1972, c’est surtout en 1981 qu’une fameuse expérience menée par Alain Aspect et son équipe ouvre la voie à ce qui est bien la confirmation de la « non-localité » quantique, invalidant par la même occasion l’hypothèse du caractère incomplet de la théorie quantique. L’intrication quantique est une réalité !

Contrairement à ce que pressentait Einstein, la physique quantique n’est donc pas une théorie locale, même si elle reste malgré tout causale : l’action à distance induite par l’intrication quantique n’ouvre pas la voie à la possibilité de communiquer quoi que ce soit à une vitesse dépassant celle de la lumière. Les meubles sont sauvés et la physique quantique respecte au moins la relativité d’Einstein !

Des particules intimement liées alors qu’elles sont distantes de plusieurs dizaines de kilomètres

Aujourd’hui, l’intrication quantique est une propriété physique admise. Elle a été vérifiée par de nombreuses équipes dans le monde. L’intrication quantique de deux photons, grains de lumière, peut par exemple être obtenue par un processus appelé « fluorescence paramétrique » se produisant dans un matériau spécial illuminé par un laser. Il est alors possible d’envoyer des photons intimement liés depuis leur « naissance » via l’intrication quantique dans des directions différentes sur de grandes distances.

Ainsi, de nombreuses expériences ont pu démontrer l’intrication de photons transmis sur des distances de quelques dizaines de kilomètres à l’aide de fibres optiques ou directement, dans l’air libre. Le record de distance est actuellement détenu par le physicien chinois Jian-Wei Pan et son équipe : en 2017, ils ont lancé en orbite le satellite Micius équipé d’une source d’intrication quantique, grâce à laquelle ils ont pu envoyer des paires de photons jumeaux vers deux bases terrestres distantes de 1200 kilomètres.

L’intrication quantique ne se limite d’ailleurs pas aux photons ; on observe aussi en laboratoire des atomes ou des ions intriqués. Une expérience célèbre a été menée en 2015 par Ronald Hanson et ses collègues de l’Université de Delft, aux Pays-Bas, impliquant le spin d’un « centre coloré » dans une microplaquette de diamant. La distance entre les deux systèmes n’est que de 1,3 km, mais tout l’intérêt ici est de parvenir à une validation dite « sans faille expérimentale » de la non-localité, ce qui signifie en gros qu’on ne peut même pas envisager un hypothétique modèle physique qui serait local mais qui exploiterait les imperfections inévitables du dispositif expérimental pour prendre les apparences de la non-localité. On ne peut vraiment pas se soustraire à la non-localité quantique !

Pour être complet, il faut cependant remarquer qu’une expérience ne peut jamais totalement exclure un modèle physique local, où tout serait prédéterminé à l’avance, y compris l’apparent libre choix de l’expérimentateur et les résultats de toutes les mesures, mais une telle hypothèse touche plus à un questionnement philosophique et s’écarte de la logique opérationnelle prédictive de la physique. La communauté des physiciens est donc dans une extrêmement large majorité convaincue du caractère non local de l’intrication quantique.

Les applications de l’intrication quantique

Enfin, l’intrication quantique ouvre la voie à des applications qui n’étaient pas même suspectées il y a une trentaine d’années. On sait en effet qu’en plus d’être une propriété insolite de la physique quantique, elle peut aussi servir de ressource permettant de mettre en œuvre des procédés de télécommunication ou de calcul dépassant tout ce que permet la physique classique.

L’un des plus emblématiques est la téléportation quantique, qui, en dépit de ce terme aux accents de science-fiction, recouvre la possibilité bien réelle de « dématérialiser » l’état quantique d’une particule, puis de le « rematérialiser » sur un autre support. On peut aussi exploiter l’intrication quantique pour établir une communication cryptée entre deux personnes, la sécurité étant garantie par le simple fait que tout éventuel dispositif-espion doit obligatoirement respecter les lois de la physique quantique. L’intrication est également à la base des ordinateurs quantiques. Ces dispositifs, actuellement voie d’élaboration, devraient permettre d’exécuter des algorithmes quantiques qui battent les ordinateurs les plus performants. Ces développements sont au cœur des sciences de l’information quantique, domaine en plein essor dans le monde.

Nicolas Cerf does not work for, consult, own shares in or receive funding from any company or organisation that would benefit from this article, and has disclosed no relevant affiliations beyond their academic appointment.

L’univers des crypto-monnaies est une incroyable jungle, avec son ambition démesurée de changer le monde, ses clans (bitcoin, ethereum, et autres), ses hyper-riches qui spéculent et peut-être manipulent les cours, ses plates-formes d’échange qui créent une finance parallèle, ses malfrats qui exploitent son anonymat, son industrie du « minage » consommatrice inassouvie d’électricité, ses start-up par centaines, et maintenant les banques centrales qui réalisent que cela les concerne et qu’il ne faut pas laisser Facebook, ou la Chine remettre en cause leur puissance parce qu’elles n’ont pas compris assez tôt que c’était sérieux et qu’elles n’ont pas agi rapidement.

Rappelons en deux mots qu’une monnaie cryptographique ou crypto-monnaie est un actif numérique dont l’émission et la circulation fonctionnent sur Internet sans qu’aucune autorité centrale ne dispose du pouvoir de l’interrompre ou de le contrôler, cela grâce à un réseau d’ordinateurs validateurs dont aucun n’a plus de pouvoir que les autres : on parle de réseau pair-à-pair. En janvier 2009, le bitcoin dont 18 millions d’unités aujourd’hui circulent, chacune valant 9400 dollars (le 5-11-2019) a été la première crypto-monnaie mise en service. C’est de loin la plus importante puisqu’à sa capitalisation (18 millions x 7650 dollars = 137,7 milliards de dollars) dépasse celle de toutes les autres crypto-monnaies cumulées. Elles sont environ 4000 aujourd’hui même si seules une vingtaine comptent vraiment.

Malgré sa domination incontestable le bitcoin possède plusieurs graves défauts que ses défenseurs acharnés – on les dénomme « les maximalistes bitcoin » – tentent de nier, mais qui sont évidents à tout observateur indépendant, c’est-à-dire ne cherchant pas à influencer le cours du bitcoin… parce qu’il en possède !

Si on considère que les monnaies cryptographiques ont un intérêt réel – ce qui est mon point de vue – il faut donc accepter d’aller au-delà du bitcoin et écouter la multitude d’acteurs qui proposent et défendent des modèles de fonctionnement améliorés du système bitcoin. Nous allons énumérer un certain nombre de défauts majeurs du bitcoin et expliquer les solutions pour y remédier proposées par ceux qui aujourd’hui inventent l’avenir de ses crypto-actifs dont on doit être certain – qu’on le veuille ou non – qu’ils vont jouer un rôle important dans l’économie de demain.

La centralisation

L’idée de départ du bitcoin est de créer une monnaie qui ne soit aux mains d’aucun État ou acteur central. De ce point de vue, le bitcoin a échoué. En effet, aujourd’hui le pouvoir de décision sur l’évolution du réseau bitcoin appartient aux acteurs qui contribuent à fournir de la puissance de calcul au réseau – on les dénomme les « mineurs », nous allons y revenir – et ce pouvoir est exactement proportionnel à la puissance dont chaque mineur dispose ; cela semble être une sorte de démocratie.

Or, la puissance fournie aujourd’hui au réseau vient pour plus de 60 % de Chine, ce qui signifie que, s’il le veut, le gouvernement chinois en exerçant son autorité sur les mineurs chinois (regroupés en quelques pôles bien identifiés) peut faire ce qu’il veut du réseau bitcoin et par exemple le faire s’écrouler. La centralisation est maximale. Le chiffre de 60 % a récemment été confirmé par le rapport de juin 2019 de Coinshare research « The bitcoin mining network ».

Les maximalistes bitcoin se réjouissaient de ce que les autorités chinoises qui s’opposent à certaines utilisations du bitcoin ont un moment envisagé de chasser les mineurs de Chine, ce qui aurait réparti la puissance de minage plus uniformément dans le monde et aurait effectivement décentralisé le réseau, conformément à l’idée initiale des créateurs de bitcoin. Malheureusement le gouvernement chinois n’a jamais vraiment mis à exécution cette élimination du minage de Chine, et d’après les dernières informations cela ne semble plus être dans ses projets.

La solution à ce problème de centralisation est liée à l’abandon du mécanisme utilisé par bitcoin pour organiser l’activité des nœuds du réseau pair-à-pair, mécanisme appelé « preuve de travail ». Il peut en effet être remplacé par d’autres mécanismes ne conduisant pas à la centralisation du pouvoir.

Le nombre de transactions exécutables

Pour qu’un système se présentant comme une monnaie, ou un moyen de paiement s’impose et remplace ceux existants – les espèces, les comptes et cartes bancaires, Paypal, Alipay, etc. –, il faut qu’à l’échelle globale il puisse exécuter plusieurs milliers de transactions par seconde, et c’est bien sûr le cas des systèmes cités. Le réseau bitcoin ne peut exécuter que 10 transactions par seconde au plus et ne pourra donc pas jouer le rôle que ses promoteurs lui assignaient.

Des solutions existent à ce problème. Construire un système complémentaire qui évite de surcharger le réseau, et lier ce système complémentaire au réseau bitcoin. C’est l’idée du projet lightning network. Il se met progressivement en place, mais il n’est pas prouvé aujourd’hui qu’il puisse vraiment atteindre le nombre de transactions nécessaires. De plus, il complique sérieusement le fonctionnement du système ce qui le fragilise (plusieurs bug graves ont déjà été identifiés) et en change profondément la nature : bitcoin + lightning network n’est plus vraiment un système où la sécurité des transactions est assurée par une blockchain (le fichier que détient chaque nœud du réseau et qui assure la sécurité des informations sur les comptes). C’est peut-être une façon d’aller au-delà du bitcoin, mais comme cela ne résoudrait pas les autres problèmes et en créerait plutôt de nouveaux, nous ne croyons pas à cette solution.

D’autres idées pour accroître le nombre de transactions opérables par seconde ont été imaginées. Elles consistent soit à ajouter d’autres types de couches au réseau bitcoin (« sidechain ») donc à en sortir, ou à changer si profondément le protocole de base que cela ne sera probablement jamais fait vu le mode de gouvernance du réseau bitcoin et les intérêts très forts de certains qui ont bloqué déjà plusieurs propositions d’évolution qui auraient permis une augmentation de ses capacités de gestion de comptes.

La dispute sur la question de la taille des pages par exemple a conduit à une fission du réseau (on dit un « fork ») le 1 août 2017 donnant naissance à Bitcoin Cash, mais sans changer la taille des pages du réseau principal Bitcoin, ce qui signifie pour ce problème la victoire de ceux qui ne voulaient rien changer.

La consommation électrique du réseau

Aux deux premiers défauts majeurs de bitcoin s’ajoute celui de l’énergie consommée. Les mineurs qui fournissent sa puissance au réseau et détiennent des parcelles de pouvoir sur le réseau dont plus de 60 % se trouvent en Chine consomment globalement une puissance électrique qu’on évalue au minimum à 40 TWh par an. C’est environ l’équivalent de 5 réacteurs nucléaires de puissance moyenne, et cela représente environ 0,3 % de l’électricité mondiale. C’est le double de ce que produisent toutes le éoliennes installées en France.

Cette électricité est dépensée pour désigner toutes les 10 minutes environ le nœud du réseau qui aura la charge d’ajouter une page de transactions validées au fichier blockchain qui contient toutes les transactions passées ; ce nœud reçoit en paiement de son travail une certaine somme en bitcoins (12,5 bitcoins aujourd’hui). Cette électricité est dépensée pour résoudre un problème de nature mathématique, qui ne peut être résolu qu’en menant des calculs massifs d’où le nom de « preuve de travail ». Le premier qui résout le problème posé (et renouvelé toutes les 10 minutes) gagne. Plus on dispose de la puissance particulière qui permet de résoudre les problèmes posés, plus on a de chances de gagner. Si par exemple vous disposez de 10 % de la puissance du réseau, vous gagnerez dans 10 % des cas. Ce concours renouvelé toutes les 10 minutes permet de gagner beaucoup d’agent : au total plus de 6 milliards de dollars par an, au cours actuel du bitcoin. Cela a créé une compétition, et le développement d’une industrie spécialisée dans le « minage » dont le plus gros acteur est la firme chinoise Bitmain. Année après année, la concurrence entre les mineurs a fait s’accroître la consommation électrique liée à leur activité de calcul qui a fini par devenir bien plus importante que celle de tous les datacenter de Google, par exemple.

Il y a des solutions simples à ce problème. Puisque cette consommation a uniquement pour but de désigner le nœud qui valide de nouvelles transactions toutes les 10 minutes, il suffit d’imaginer d’autres modes de désignation du nœud validateur qui ne fonctionnent pas sur un concours de calcul coûteux en électricité. Une multitude d’idées ont été proposées ; certaines ont été mises en œuvre et fonctionnent très bien (crypto-monnaies EOS, [ripple](https://fr.wikipedia.org/wiki/Ripple_(protocole_de_paiement),cardano. La seconde crypto-monnaie (ethereum) a programmé de se débarrasser des preuves de travail pour passer à un fonctionnement les évitant.

Le fonctionnement de la crypto-monnaie libra dont Facebook est le promoteur se fonderait bien évidement sur l’un de ces modèles non consommateur d’électricité. C’est donc une folie de continuer à faire reposer le réseau bitcoin sur les preuves de travail et c’est clairement une erreur dans la conception de départ du protocole bitcoin.

La spéculation

La valeur d’un bitcoin est déterminée par la confiance qu’on a en lui, et ne s’appuie sur aucun actif matériel. Cela conduit au gré des événements et des média qui en parlent ou cessent d’en parler à des variations énormes du cours, le rendant très difficile à utiliser en pratique.

Les effets de la spéculation sont ahurissants : un bitcoin valait environ 1000 dollars début janvier 2017, et il a atteint 20 000 dollars en décembre 2017, pour retomber sous les 4000 dollars quelques mois plus tard, et pour aujourd’hui valoir environ 9000 dollars.

La solution à cette instabilité existe : faire reposer la valeur d’une crypto-monnaie sur une contrepartie conservée par un acteur qui garantit le cours. Ce sont les « stablecoin » dont la plus importante aujourd’hui est le tether qui vaut 1 dollar exactement (à 1 % près), car Tether International Limited achète et vend en continu tout tether contre 1 dollar ce qui empêche le cours de varier. La libra serait fondée sur un système de ce type et ne serait donc pas soumise aux variations spéculatives déraisonnables du bitcoin, le rendant inutilisable.

D’autres défauts du bitcoin peuvent être ajoutées à cette liste comme son incapacité à exécuter des smart-contracts. Ces derniers ont été introduits par ethereum et on les considère comme un atout majeur des crypto-monnaies pour le développement d’une économie et d’une finance numérique.

Ces smart-contracts rendent possibles de nouveaux types d’applications décentralisées créant plus de sécurité et de confiance entre des acteurs présents sur les réseaux. C’est d’ailleurs ce qui rend certain que ces nouvelles crypto-monnaies libérées et dépassant le modèle préliminaire du bitcoin s’imposeront. Plutôt que de laisser tether ou libra occuper cette place, les banques centrales (en Europe et même aux États-Unis) sont en train de réaliser que c’est à elles de créer des crypto-euros, des crypto-dollars, ou pourquoi pas si elles s’entendaient entre elles (on peut rêver), une sorte de crypto-monnaie-universelle qui serait au service de tous, et aux mains de personne, permettant d’exécuter des milliers de transactions par seconde, et des smart-contracts, tout en étant économe en énergie et en possédant une valeur stable.

Ce véritable argent liquide numérique universel éviterait que dans l’avenir, si nous en restons aux systèmes numériques de paiement centralisé existants, chaque centime gagné ou dépensé soit suivi et enregistré, rendant notre vie de tous les jours de moins en moins privée. S’il n’est pas trop tard déjà pour envisager de protéger nos données personnelles, une véritable crypto-monnaie bien conçue est nécessaire. Tout sur un plan théorique et informatique est prêt pour la créer et la rendre accessible à tous. Les maximalistes bitcoins freinent le mouvement, les États aussi jusqu’à présent en laissant leurs banques centrales en dehors de l’affaire.

Retrouvez Jean‑Paul Delahaye à la Cité des Sciences le mardi 17 décembre 2019 à 19h pour la conférence « Dépasser le bitcoin ».

Jean-Paul Delahaye ne travaille pas, ne conseille pas, ne possède pas de parts, ne reçoit pas de fonds d'une organisation qui pourrait tirer profit de cet article, et n'a déclaré aucune autre affiliation que son organisme de recherche.

La blockchain a dès ses débuts été présentée comme une technologie très novatrice et très prometteuse sur le plan de la confiance. Qu’en est-il réellement ? Certains évènements récents sèment le doute, comme les détournements d’argent réalisés récemment contre le wallet Parity (30 millions de dollars), ou la société Tether (31 millions de dollars).

Cet article revient sur les principaux éléments étayés dans le chapitre 11 du livre « Signes de confiance : l’impact des labels sur la gestion des données personnelles » produit par la chaire de l’Institut Mines-Télécom Valeurs et politiques des informations personnelles dont Télécom SudParis est cofondateur. Le livre est téléchargeable sur le site de la chaire. Cet article adresse exclusivement le cas de la blockchain publique.

Comprendre la technologie :

La blockchain peut être assimilée classiquement à un « gros » livre de comptes accessibles et auditables, qui est déployé sur le réseau Internet. Elle repose en effet sur un très grand nombre de ressources informatiques distribuées de par le monde, appelées « nœuds », qui participent au fonctionnement de la blockchain. Dans le cas de la blockchain publique, tout le monde peut contribuer ; il suffit de posséder un ordinateur d’une puissance suffisante et d’y exécuter le code associé.

L’exécution du code vaut pour acceptation des règles de gouvernance de la blockchain. Ces contributeurs ont pour tâche de collecter les transactions émises par ses clients, d’agréger les transactions dans une structure appelée « bloc » (de transactions) et de valider les blocs avant de les inscrire dans la blockchain. La chaîne de blocs (ou blockchain) qui en résulte peut atteindre des centaines de gigaoctets et est dupliquée un très grand nombre de fois sur Internet, ce qui assure une très grande disponibilité de la blockchain.

Eléments de confiance

La blockchain repose sur les principes conceptuels forts suivants qui la positionnent naturellement comme la technologie de confiance par excellence :

• Architecture décentralisée et neutralité de la gouvernance s’appuyant sur le principe de consensus : elle repose sur un très grand nombre de contributeurs indépendants et est donc par nature décentralisée. Cela signifie, contrairement à une architecture centralisée où les décisions peuvent être prises unilatéralement, qu’il faut atteindre un consensus ou bien réussir à contrôler plus de 50 % de la puissance de calculs de la blockchain (ressources informatiques), pour avoir un effet sur le système. Ainsi, tout changement de règles de gouvernance doit être préalablement approuvé par consensus par les contributeurs, qui doivent alors mettre à jour le code logiciel exécuté.

• Transparence des algorithmes offrant une meilleure auditabilité : toute transaction, tout bloc, toute règle de gouvernance est librement accessible et lisible par tout le monde ; à ce titre, n’importe qui peut auditer le système pour s’assurer de la bonne marche de la blockchain et de la légitimité des transactions. L’avantage est de permettre aux experts de la communauté d’utilisateurs de scruter le code et d’alerter en cas de suspicion. La confiance repose donc sur les lanceurs d’alertes.

• Technologies sous-jacentes sûres : Les techniques cryptographiques et les modalités d’utilisation garantissent que la blockchain ne peut pas être altérée, que les transactions inscrites sont authentiques même si elles sont émises sous couvert d’un pseudonyme, et enfin que la sécurité de la blockchain est en mesure de suivre les évolutions technologiques grâce à un niveau de sécurité adaptatif.

Des interrogations subsistent

Regardons maintenant les blockchains en pratique et revenons sur certains évènements qui ont amené de la suspicion à l’égard de la technologie :

• Attaque des 51 % : Plusieurs organisations contribuant significativement au fonctionnement de la blockchain peuvent s’allier et détenir à elles-seules au moins 51 % de la puissance de calculs de la blockchain. Par exemple, la Chine est connue pour concentrer une grosse partie de la puissance de calcul pour la blockchain bitcoin, plus précisément plus des deux tiers en 2017. Cela remet en question le caractère distribué de la blockchain et la neutralité de la gouvernance puisque le pouvoir de décision est à ce moment-là totalement déséquilibré. En effet, les organisations majoritaires peuvent censurer des transactions, ce qui a un impact sur l’historique de la blockchain, mais pire encore, elles ont un pouvoir non négligeable de faire approuver les règles de gouvernance qu’elles ont décidées.

• Hard fork : Lorsque de nouvelles règles de gouvernance sont poussées dans la blockchain et qu’elles sont incompatibles avec les règles précédentes, on assiste à un « hard fork », c’est-à-dire une modification définitive de la blockchain, qui nécessite qu’un large consensus soit atteint parmi les contributeurs de la blockchain pour voir les nouvelles règles de la blockchain acceptées. Sinon, la blockchain se dédouble avec au final l’existence simultanée de deux blockchains, une fonctionnant sur les anciennes règles et une autre sur les nouvelles. Ce dédoublement de chaîne a pour effet de décrédibiliser les deux blockchains résultantes et de provoquer la dévaluation de la crypto monnaie associée. On peut aussi remarquer qu’un hard fork commandité dans le cadre d’une attaque des 51 % aura plus de chance d’aboutir à l’adoption des nouvelles règles du fait que le consensus sera plus facilement atteint.

• Blanchiment d’argent : La blockchain est transparente par nature, mais la traçabilité des transactions peut être rendue très complexe facilitant ainsi les opérations de blanchiment d’argent. En effet, il est possible d’ouvrir un très grand nombre de comptes, d’utiliser des comptes à usage unique, par exemple, et d’effectuer des transactions sous couvert de pseudonymat. Cela questionne l’ensemble des contributeurs sans lesquels la blockchain ne pourrait pas fonctionner sur leurs valeurs morales et nuit à l’image de la technologie.

• Erreurs de programmation : De telles erreurs peuvent être commises dans des smart contracts, des programmes s’exécutant de façon automatique au sein de la blockchain et peuvent avoir des conséquences dramatiques pour les industriels. L’organisation The DAO a ainsi vu le détournement de 50 millions de dollars en 2016. Les organisations coupables de tels bugs peuvent vouloir invalider les transactions qui leur portent préjudice – The DAO ayant réussi à provoquer un hard fork à cette fin – ce qui remet en question le principe même de l’inaltérabilité de la blockchain. En effet, des blocs enregistrés comme valides dans la blockchain à un moment donné sont ensuite rendus invalides, ce qui questionne la fiabilité de la blockchain.

En conclusion, la blockchain est une technologie très prometteuse offrant de nombreuses propriétés d’intérêt pour garantir la confiance, mais le problème réside dans l’écart qui existe entre les promesses de la technologie et l’usage qui en est fait, ce qui introduit beaucoup de confusion et de mauvaises compréhensions, ce que nous avons tenté de lever dans cet article.

Maryline Laurent a reçu des financements de la fondation Mines-Télécom

Le 26 décembre 2017, J. Pace, G. Woltman, S. Kurowski, A. Blosser, et leurs co-auteurs ont annoncé la découverte d’un nouveau nombre premier : 2⁷⁷²³²⁹¹⁷-1. Faisons donc une petite incursion dans le monde des chercheurs de nombres premiers pour voir comment ce résultat a été obtenu, et aussi, à quoi ça sert.

Un nombre premier est un nombre qui est divisible uniquement par un et lui-même, c’est-à-dire essentiellement un nombre qui n’a pas de diviseur. Certains parlent des nombres premiers comme les atomes de l’univers mathématique, d’autres comme des pierres précieuses.

Nous devons à Euclide les deux premiers résultats :

• Ils sont en nombre infini. La démonstration de ce résultat est considéré comme la première démonstration par l’absurde. Supposons qu'il n'y a qu'un nombre fini de nombres premiers, ils sont donc tous plus petits qu'un certain entier n. Tout entier supérieur à n serait donc divisible par un nombre premier inférieur à n. Or le nombre (2*3*…*n)+1 n'est divisible par aucun des entiers de 2 à n puisque le reste de la division est toujours 1: ceci contredit la phrase précédente.

• Tout nombre est le produit unique de facteurs premiers.

Ératosthène (-276, -194) a proposé un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. Son crible consiste à éliminer d’une table des entiers de 2 à N tous les multiples d’un entier. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d’aucun entier, et qui sont donc les nombres premiers. La recherche d’algorithmes efficaces est un sujet de recherche actif (voici ici ou là) par exemple pour le test de Lucas-Lehmer)

Après l’école grecque, il y a une longue période noire qui va jusqu’à la fin du XVI^e siècle et en particulier l’arrivée de Marin Mersenne (1588-1648). Il est à la fois un défenseur de l’orthodoxie catholique et un catholique ouvert qui pense que la religion doit accueillir toute vérité mise à jour. Il adhère au cartésianisme et est le traducteur de Galilée.

Mersenne cherchait une formule donnant tous les nombres premiers. Il étudia plus particulièrement les nombres M_p=2^p-1, où p est premier, nombres désormais appelés nombres de Mersenne. Il affirme en 1644 que Mp est premier pour p=2,3,5,7,13,17,19,31,67,127,257, et composé (c’est-à-dire non premier) pour les 44 autres valeurs de p inférieures à 257. Il commet en fait 5 erreurs (M61, M89 et M107 sont premiers, M67 et M257 ne le sont pas).

Le nouveau nombre premier découvert à la toute fin de 2017 correspond donc à M77232917. Il a 23 249 425 chiffres – près d’un million de chiffres de plus que le nombre premier record précédent. Un Document word écrit en Times New Roman, avec une taille de police de 10 et les marges classiques, représenterait 3845 pages.

La date officielle de la découverte est le jour où un homme déclare le résultat. Ceci est en accord avec la tradition : M4253 est réputé ne jamais avoir été le plus grand nombre premier connu parce qu’en 1961, le mathématicien américain Alexander Hurwitz avait lu la sortie d’imprimante à partir de la fin et trouva M4423 quelques secondes avant de voir que M4253 était aussi premier. De même, le nombre de Mersenne précédent a vécu une histoire compliquée : l’ordinateur a signalé le résultat au serveur le 17 Septembre 2015 mais un bug a empêché l’envoi de l’e-mail. Le nouveau nombre premier est resté inaperçu jusqu’à la maintenance de la base, c’est-à-dire le 7 janvier 2016.

Cryptographie quantique

On cite souvent l’utilisation des nombres premiers en cryptographie mais celui-ci est trop grand pour être vraiment utilisable (mais les espoirs en cryptographie quantique vont probablement changer les choses). Historiquement, la recherche de nombres premiers de Mersenne a été utilisé comme un test pour le matériel informatique. En 2016, la communauté autour du logiciel prime95 a permis de découvrir une faille dans le dernier CPU Skylake d’Intel (ici) ainsi que dans beaucoup d’ordinateurs personnels. Ce nombre premier a été trouvé dans le cadre du projet Great Internet Mersenne Prime Search (GIMPS).

2⁷⁷²³²⁹¹⁷-1 est le 50^e nombre de Mersenne premier et si le défi de la découverte du 51^e vous tente, vous pouvez trouver un programme de vérification ici et peut être même gagner les 3000 dollars proposés à l’heureux(se) gagnant-e. (Attention Jonathan Pace, qui a le premier découvert ce nombre, y travaille depuis quatorze ans.)

Avner Bar-Hen does not work for, consult, own shares in or receive funding from any company or organisation that would benefit from this article, and has disclosed no relevant affiliations beyond their academic appointment.

Cet article est publié en collaboration avec le blog Binaire

La tâche est plus vieille que Le Monde : A (comme Angela) souhaite communiquer un message à B (comme Barack) tout en empêchant E (comme Edward) de l’intercepter. Nous savons faire avec des techniques sophistiquées de cryptographie comme RSA. Mais il paraît que la mécanique quantique va ouvrir de nouvelles possibilités. Nous avons demandé à un ami, Alexei Grinbaum, ce qu’il en est. Binaire

Partager un secret avec une clé secrète

Le lecteur de Binaire n’aura guère de difficulté à imaginer que le message soit une suite de 0 et 1. La méthode imbattable consiste à utiliser une « clé de chiffrement jetable ». C’est une séquence de 0 et de 1, aléatoire et au moins aussi longue que le message à transmettre. Supposons qu’Angela souhaite transmettre le message « 11111 » à Barack et que la clé aléatoire, tenue secrète, soit « 10110 ». Alors Angela intervertit le premier, le troisième et le quatrième bits du message (comme l’indiquent les 1 dans la clé) et publie en clair « 01001 ». Barack, qui connaît la clé secrète, intervertit les mêmes trois bits et reconstruit le message « 11111 ». Edward n’a aucune chance de rétablir ce message en ayant accès à la seule transmission chiffrée.

Mais une clé qui se renouvelle sans cesse !

Un problème est que la clé est « jetable ». Si par aventure Angela l’utilisait plusieurs fois, Edward finirait par la découvrir en faisant des analyses statistiques.

Ce que l’on aimerait, c’est un monde idéal où Angela et Barack disposeraient d’une source illimitée de clés. Imaginons qu’ils possèdent deux pièces de monnaie, A et B, qui, lorsqu’on les lance, tombent sur pile, qu’on comprendra comme « 0 », ou sur face, le « 1 », de façon aléatoire, mais, par un coup de magie, à chaque fois les deux tombent du même coté. S’ils pouvaient disposer de telles pièces, Angela et Barack pourraient jouer à pile ou face autant de fois qu’ils le souhaitent et se fabriquer sans limites des clés secrètes. Un détail : dans notre monde, à notre échelle, de telles pièces magiques n’existent pas. Alors ? Patience.

Mieux encore une clé qu’il serait inutile de voler !

Nous devons aussi garantir qu’Edward ne puisse intercepter le message en se procurant un troisième clone de la même pièce. Attaquons-nous à cette dernière condition. Pour y trouver une solution, nous allons tirer profit d’une valeur que l’on ne rencontre pas souvent dans un problème de sciences : la liberté !

Supposons qu’Angela et Barack possèdent deux pièces de monnaie magiques, A1 et A2 pour la première, B1 et B2 pour le second. Pour obtenir un bit, Angela choisit librement entre A1 et A2 et lance la pièce. Barack fait de même avec B1 et B2. Ils vont recommencer autant de fois qu’ils le souhaitent. Les quatre pièces sont magiques : à chaque coup, si Angela choisit A1 et Barack B1, les deux pièces disent la même chose ; idem dans les cas (A1, B2) et (A2, B1) ; mais dans le cas (A2, B2), les pièces disent le contraire l’une de l’autre. Bref, le résultat individuel ne dépend que du choix local d’Angela ou Barack, mais la relation entre ces choix dépend de ce que font A et B conjointement.

Maintenant Angela et Barack peuvent construire une clé secrète. Pour Angela, c’est juste la séquence de bits que lui indiquent les pièces. Pour Barack, il garde le bit que lui donne sa pièce dans trois cas, et il l’intervertit dans le cas (A2,B2). Ce mécanisme garantit que le message ne sera pas intercepté par Edward. Car, même s’il est capable de cloner une pièce d’Angela, il ne connaît pas le choix de Barack. S’il lance un clone de A1 au moment où Angela choisit – toujours librement ! – de jouer A2, alors ce lancement simultané, et de A1 (cloné) et de A2 entrave le libre arbitre de Barack, puisqu’aucune valeur ne peut être attribuée à ses pièces (rappelons que A1=B2, mais A2≠B2, d’où la possibilité de contradiction).

Oui, mais si tout cela n’existe pas ?

À notre échelle, de telles pièces magiques n’existent pas. Des corrélations aussi parfaites entre elles sont en réalité inatteignables. Et puis la liberté des agents elle aussi est douteuse. Mais à l’échelle de l’infiniment petit, la cryptographie quantique pallie d’une manière spectaculaire à ces défauts.

À la place des pièces, la cryptographie quantique utilise des paires de particules quantiques intriquées, souvent des photons. Grâce à un phénomène, l’intrication quantique, on arrive à des corrélations imparfaites, certes, mais proche de plus de 80 % de celles qu’ont les pièces de monnaie dans le monde idéal. En se servant alors de la propriété de non-localité quantique, c’est-à-dire d’un lien simultané entre deux phénomènes distants, séparés dans l’espace, Angela et Barack arrivent à partager des bits avec une corrélation suffisamment forte pour que la communication reste protégée contre les intrusions. En plus, Edward ne peut s’immiscer entre Angela et Barack et intercepter leurs communications à cause d’une propriété de l’intrication quantique dont le nom fort à propos est « monogamie » : à chaque particule, pas plus d’un partenaire intriqué à la fois !

Plus de 80 %, ce n’est pas idéal. Pourtant on prouve que c’est suffisant pour que les protocoles quantiques de distribution des clés secrètes puissent assurer la protection parfaite de la communication entre Angela et Barack.

Un enjeu de recherche colossal

Où en sommes-nous dans la réalisation pratique de ces procédés ? Depuis peu, la sécurité absolue qu’offre la cryptographie quantique est vraiment devenue atteignable. Nous entrons dans une ère où les expériences scientifiques, mais aussi des produits technologiques et industriels, se développent de plus en plus rapidement. L’Europe se prépare à lancer un nouveau financement gigantesque de ce secteur à la hauteur de 1 milliard d’euros. Bientôt, la cryptographie quantique prendra le relais des techniques conventionnelles de cryptage. Signalons qu’au moment où sort ce billet, un nouveau record de distance (plus de 400 km entre les points A et B) vient d’être publié.

Alexei Grinbaum est l'auteur de "Mécanique des étreintes, Intrication quantique", éditions Les belles Lettres