Présentation de l’éditeur

 La cryptologie, cet art de coder un message de telle sorte qu’il puisse tomber sans conséquence entre les mains de l’ennemi, est aussi ancienne que la diplomatie et le commerce. Elle se complexifie en même temps que les techniques, et devient, au XXe siècle, avec l’équipe réunie autour d’Alan Turing pour briser le code de la machine allemande Enigma, une branche à part entière des mathématiques.

Avec l’avènement d’Internet, et les milliards de messages cryptés qui s’y échangent quotidiennement, elle prend une importance considérable. Aucune méthode de cryptage n’est incassable en soi, la seule limite est celle de la puissance de calcul des machines utilisées. Cette puissance ne cessant de croître, les cryptographes (qui élaborent les codes) et les cryptanalystes (qui cherchent à les percer) sont engagés dans une course sans fin.

C’est cette histoire que nous conte ici Jacques Stern, qui en est un des acteurs incontournables.

Médaille d’or du CNRS, Jacques Stern est mathématicien, spécialisé en informatique et cryptologie, professeur à l’École normale supérieure.

La version audio du présent ouvrage
est disponible à l’achat sur le site www.devivevoix.com

Couverture Paul Cox

© CNRS Éditions / De Vive Voix,
coll. « Les Grandes Voix de la Recherche »,
Paris, 2021.

ISBN : 978-2-271-13362-5

ISSN : 2680-2708

www.cnrseditions.fr
www.devivevoix.com

Ce document numérique a été réalisé par PCA

Les Grandes Voix de la Recherche

Une collection CNRS Éditions / De Vive Voix

Donner la parole aux lauréats et lauréates de la médaille d’or du CNRS, la plus prestigieuse récom-pense scientifique française : telle est l’ambition de la collection Les Grandes Voix de la Recherche.

En des textes courts et vivants, les médailles d’or retracent leur parcours, nous transmettent leur pas-sion, nous présentent leurs travaux. Grâce à des contenus accessibles et à jour des dernières avancées scientifiques, ils nous introduisent au meilleur de la recherche française.

En passeurs et médiateurs, ces grandes voix de la recherche explorent tous les domaines de la connais-sance et présentent de manière claire les grands défis de la science.

À écouter ou à lire, ces grandes voix de la recherche sont disponibles sous forme de livre audio et de livre papier.

Jacques Stern.
© David Monniaux

Introduction

La cryptologie moderne est une partie de l’informatique, qui est quant à elle l’étude des processus qui permettent la manipulation, le stockage et la communication d’informations numériques. La cryptologie a pour objet de protéger ces processus contre un adversaire hostile. Elle doit notamment garantir une trilogie fondamentale : intégrité, authenticité, confidentialité. Il s’agit, par exemple, de vérifier l’intégrité d’un fichier sauvegardé, d’authentifier l’origine d’un message électronique, d’empêcher l’accès à des données sensibles durant leur transfert.

La discipline se divise en deux : la cryptographie et la cryptanalyse. La première, ce sont les méthodes qui permettent d’assurer la protection des informations numériques, généralement à l’aide de conventions partiellement ou totalement secrètes. La seconde, c’est la science ou l’art permettant de déjouer les méthodes mises en place sans avoir connaissance des éléments secrets. Cette science est source de paradoxes. Comment un art ancestral peut-il devenir une science moderne ? Comment un savoir si longtemps restreint aux univers de la défense et de la diplomatie peut-il avoir désormais une place de choix au cœur du monde numérique ? Comment cette science réalise-t-elle des fonctionnalités que l’on a considérées pendant longtemps impossibles ? C’est ce que je veux évoquer ici, ainsi que le chemin qui m’a conduit à devenir cryptologue. Je citerai quelques livres qui sont pour moi autant de points de repère. Je terminerai enfin en décrivant la discipline en lien avec d’autres savoirs avec lesquels elle interfère : algorithmique, mathématiques, technologies, finance, physique.

Un souvenir personnel pour commencer : en troisième, j’étais un enfant studieux intéressé par toutes les sciences, surtout les mathématiques. Au détour d’une lecture, j’ai appris que la solution de l’hypothèse du continu de Cantor était apparue, et que le problème s’était révélé indécidable. Je connaissais le nom de Georg Cantor, un mathématicien allemand de la fin du XIXe siècle, qui avait montré que l’on ne pouvait énumérer les points d’une droite en les plaçant dans une liste indexée par des nombres entiers (le premier point, le deuxième, le troisième, etc.). Je comprenais à peu près l’énoncé de l’hypothèse du continu : puisque l’infini des points d’une droite est plus grand que l’infini des nombres entiers, y a-t-il quelque chose entre ces deux infinis ? Mais je ne comprenais pas ce que voulait dire exactement « indécidable », ni surtout comment on pouvait prouver qu’un énoncé mathématique n’admettait pas de preuve, pas plus que l’énoncé contraire. J’ai ensuite oublié cette anecdote et, lorsque je suis entré à dix-neuf ans à l’École normale supérieure (ENS), j’ai fait des premiers choix. La physique et la chimie ne me tentaient pas. Je ne me sentais pas prêt pour l’expérimentation. L’informatique à l’époque, c’étaient des cartes perforées où chaque erreur de saisie était fatale. J’en faisais pas mal et m’en suis détourné. Je suis donc devenu mathématicien. Après la licence, au lieu de m’engager dans des disciplines où l’école mathématique française excellait, j’ai opté pour un cursus à base de logique, théorie des ensembles, calculabilité.

La logique a conduit à une thèse. La théorie des ensembles m’a offert la possibilité de revenir à Cantor, et j’ai enfin pu comprendre la preuve de l’indécidabilité de l’hypothèse du continu. J’ai moi-même contribué à la solution de problèmes analogues, et notamment du problème restreint du continu posé par un mathématicien russe, Nicolas Lusin, en 1930. Quant à la calculabilité, elle est devenue mon chemin vers la cryptologie. J’y reviendrai.

Je ne vais pas décrire ici les mathématiques que j’ai étudiées, mais je ne peux passer sous silence les scientifiques exceptionnels qui les ont créés. J’ai déjà évoqué le nom de Cantor. Mais il me faut aussi citer Kurt Gödel et son célèbre résultat d’incomplétude de 1931 (tout système mathématique suffisamment puissant admet des énoncés indécidables) et Alan Turing qui, en 1936, a été l’inventeur génial de la machine qui porte son nom, modèle abstrait d’ordinateur, et qui a étendu le résultat de Gödel.

En 1979, j’ai été nommé, assez jeune, professeur à l’université de Caen, ce qui m’a donné du temps pour réfléchir à la suite. Le résultat sur le problème de Lusin avait réalisé mes rêveries d’enfant, mais les avait également dissoutes. Je ne souhaitais plus poursuivre dans cette voie. Cantor affirmait que c’était Dieu lui-même qui l’avait inspiré et Gödel avait produit une preuve mathématique de son existence : je ne voulais pas être face-à-face avec Dieu. Je m’interrogeais aussi sur le destin tragique de tous ces mathématiciens. Cantor était dépressif et a fini ses jours dans un hôpital psychiatrique. Turing s’est suicidé à l’âge 41 ans : condamné à cause de son homosexualité, il a ingéré une pomme au cyanure. Atteint de délire de la persécution, Gödel avait peur d’être empoisonné et ne s’alimentait plus ; il est mort en 1978, à 72 ans. L’un de mes collègues l’avait rencontré à Princeton juste avant ; il n’était plus qu’une ombre. Je devais donc changer de voie et un autre chemin s’est imposé.

Je pressentais, comme beaucoup de scientifiques, l’émergence et l’importance de ce que l’on appelle aujourd’hui la révolution numérique. Je voulais y participer et je pensais en avoir les moyens. La calculabilité que j’avais étudiée s’était entre-temps enrichie. Elle ne s’intéressait plus seulement à ce que l’on peut calculer sur des données, numériques ou non, mais également à la complexité même du calcul par la mesure du temps passé ou de l’espace nécessaire pour le faire. On pouvait ainsi séparer ce que l’on calcule facilement de ce que l’on calcule beaucoup plus difficilement. Si l’on multiplie deux nombres entiers, par exemple 5 × 7 = 35 et que l’on oublie les deux entiers de départ, comment les retrouver à la seule lecture du résultat ? C’est simple pour 5 et 7, mais qu’en est-il pour de très grands nombres ? Il est notablement plus difficile de résoudre cette question que de vérifier la solution une fois qu’elle est proposée. La généralisation de cette dichotomie conduit paradoxalement à l’un des sept problèmes du millénaire posés en l’an 2000 à tous les mathématiciens, ce que l’on appelle le problème P = NP (en simplifiant, il s’agit de déterminer si le fait de pouvoir vérifier facilement une solution d’un problème implique que l’on puisse trouver aussi facilement une solution de ce problème). Je m’en suis tenu soigneusement à l’écart, surtout quand j’ai réalisé que Gödel avait écrit en 1956 une lettre à John von Neumann, un autre géant des mathématiques, dans laquelle il envisageait déjà ce problème comme une variante de celui de la décision, qu’il avait résolu grâce à son théorème d’indécidabilité.

Dans la construction d’un monde numérique auquel je voulais participer et où tout était à faire, les fondations, les murs et les fenêtres de la nouvelle cité virtuelle, je me suis modestement tourné vers les serrures, les cadenas et les clés. Était-ce important ? Je le pensais, et il se confirme aujourd’hui que la protection des données personnelles dans un monde ouvert à tout vent est essentielle. C’était suffisamment important également pour que Turing y ait consacré plusieurs années de sa vie. Il avait en effet fait partie d’une équipe, réunie par les Britanniques pendant la Seconde Guerre mondiale, chargée de casser les codes de l’ennemi. Dès 1942, les Alliés lisaient les messages secrets des Allemands chiffrés par la célèbre machine Enigma.

Ce que je voulais faire n’était pas si simple et j’ai connu ma traversée du désert. Pendant plusieurs années, j’ai lu des livres d’informatique, étudié des articles de cryptologie, pratiqué les langages de programmation. J’allais à des conférences et je me trouvais dans une étrange situation : j’étais passé du rang de chercheur confirmé à celui d’étudiant autodidacte. Mais ces efforts ont porté leurs fruits. En 1987, j’ai publié un premier article significatif où j’ai analysé un générateur d’aléas proposé par Donald Knuth, le pape de l’algorithmique, auteur de la Bible du domaine : The Art of Computer Programming (L’Art de la programmation).

La production d’aléas par un algorithme relève du paradoxe : il n’y a pas de dés dans l’ordinateur. Or, le but est de produire des tirages imprédictibles. J’ai montré que le générateur de Knuth n’y parvenait pas, ce qui a constitué mon ticket d’entrée dans la communauté scientifique de la cryptologie. À 38 ans, un peu tard pour un mathématicien, j’avais enfin trouvé ma voie.

Chaque communauté a ses rites et ses points de repère. Pour la cryptologie, c’est l’université de Californie à Santa Barbara, où se tient une réunion chaque été. Santa Barbara n’est pas tout à fait l’épicentre de la révolution numérique, ce n’est pas la Silicon Valley, mais c’est assez près pour en percevoir l’esprit et assez loin pour en être indépendant. J’y vais chaque année et j’y ai aussi conduit mes élèves. Vingt ans après avoir quitté l’École normale supérieure, j’y suis en effet revenu comme professeur et j’ai eu la chance d’y recevoir des étudiants exceptionnels venus d’horizons divers (grandes écoles, universités…). J’ai pu ainsi faire école, et c’est ensemble que nous avons contribué aux différents progrès de la discipline, tant en cryptographie qu’en cryptanalyse.

Dans son ouvrage Souvenirs d’apprentissage paru en 1991, le mathématicien français André Weil raconte qu’il séchait les cours de l’ENS et qu’il apprenait bien plus en lisant les auteurs dans le texte original. Je vous invite donc à une brève introduction à la cryptologie au travers de quelques livres originaux, anciens et récents.

Commençons par le traité de Al-Kindi, philosophe et savant du IXe siècle, directeur de la Maison de la sagesse fondée à Bagdad par les califes abbassides. Cet ouvrage, qui avait disparu, a été redécouvert en 1987 par des collègues de Bagdad au sein de la bibliothèque de la mosquée Süleymaniye, à Istanbul. Il présente les méthodes ancestrales de la cryptologie : la substitution, qui consiste à remplacer, dans un texte, une lettre par une autre et la transposition, qui consiste à changer l’ordre des lettres. Il présente d’autres idées extrêmement originales pour l’époque, comme le chiffrement d’une suite de lettres par des mots d’une catégorie donnée. Par exemple, pour coder le mot « Noël », on peut convenir de coder la lettre N par le genre, la lettre O par un bijou, la lettre E par un liquide et la lettre L par un pays. On peut ainsi remplacer le mot Noël par la phrase Une femme avec un bracelet puise de l’eau au Danemark, ou par une autre, L’homme au collier boit une vodka en Russie. Ce traité est également connu comme le premier ouvrage de cryptanalyse. Il utilise notamment la fréquence des lettres en arabe pour décrypter les textes chiffrés par substitution, mais aussi la méthode dite « du mot probable ». Imaginons que nous ayons une version chiffrée du Coran, nous allons rechercher la phrase arabe Au nom de Dieu clément et miséricordieux, dont on sait qu’elle revient souvent. Cette méthode n’est apparue en Occident qu’au XVIe siècle, et a été utilisée par Turing dans sa cryptanalyse de la machine Enigma : ce sont les mots « bulletin météo » dans les messages (en allemand) du matin qui étaient alors recherchés.

Continuons avec Alberti, célèbre érudit et architecte. Son ouvrage original en latin date de 1466 et s’intitule De Componendis Cifris. On en connaît dans le monde une vingtaine d’exemplaires. Il est notamment célèbre grâce au cadran d’Alberti, un dispositif formé de deux disques concentriques, l’un fixe avec un alphabet ordonné, l’autre mobile avec un alphabet désordonné. Le disque permet d’opérer facilement, par lecture directe, une substitution. Il permet d’en changer en avançant la pièce mobile périodiquement.

Poursuivons avec l’ouvrage, toujours en latin, de l’abbé allemand Trithème : Polygraphia. J’ai la chance de posséder une version originale, non pas du texte latin, mais de la première traduction en français par Gabriel de Collange en 1561, un très beau livre avec ses centaines d’alphabets cachés. Ce sont des groupes de mots permettant de chiffrer par des phrases, comme chez Al-Kindi. Des cadrans aussi, comme chez Alberti, que l’on peut encore faire tourner. L’ouvrage est d’ailleurs connu comme source de l’un des plus célèbres exemples de plagiat scientifique. Il a été republié en 1620 aux Pays-Bas avec mot pour mot le texte français. Seul l’auteur diffère : il s’appelle Dominique de Hottinga. L’ouvrage ne fait référence ni à Collange ni à Trithème.

Après un saut de quelques siècles, mentionnons un ouvrage paru en 1883 : La Cryptographie militaire, d’Auguste Kerckhoffs, qui y énonce six principes. Voici les deux premiers : le système doit être matériellement, sinon mathématiquement, indéchiffrable ; il faut qu’il n’exige pas le secret et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi. J’aime regarder le premier principe sous l’angle de la dichotomie calculabilité/complexité. Quant au deuxième, il tranche définitivement la question des conventions secrètes. C’est la clé qui est secrète, pas le mécanisme de la serrure. Nous ne sommes plus dans la Maison de la sagesse, nous ne sommes plus dans les mains des érudits de la Renaissance ni des prêtres. Nous sommes dans l’efficacité militaire et le contexte opérationnel. C’est précisément ce contexte et le progrès des technologies qui ont conduit aux machines chiffrantes comme l’Enigma, puis plus tard à l’informatique, pour réaliser les multiples combinaisons de substitutions et de transpositions nécessaires à une cryptologie solide et déjà envisagées par Al-Kindi ou Alberti.

Terminons notre tour d’horizon bibliographique par deux articles qui ont une approche plus académique. Celui de Claude Shannon d’abord, et sa Théorie mathématique de la communication de 1948. Il y a une vraie analogie entre Turing et Shannon. Tous deux ont travaillé pour les services secrets et tous deux ont contribué à l’avènement de la révolution numérique. Les travaux de Shannon pendant la guerre portaient sur la capacité à séparer le brouillage du message dans les communications des ennemis. Cela l’a conduit à considérer l’information comme une donnée purement physique, quantifiable, en utilisant la théorie des probabilités. Ses travaux sont à la base de toute l’infrastructure du monde numérique. Ce sont eux qui permettent le codage des signaux véhiculés sur les câbles en fibre optique ou transmis au smartphone par ondes électromagnétiques. En cryptologie, ils ont conduit à la notion de secret parfait, qui est l’impossibilité de distinguer par un test statistique ce qui est chiffré d’un bruit aléatoire.

Le dernier texte comporte seulement dix pages dues à deux chercheurs américains, Whitfield Diffie et Martin Hellman. Intitulé New Directions in Cryptography, il a été publié en 1976. Ces dix pages ont révolutionné la cryptologie en en faisant une véritable science et un objet de recherche académique. Explicitement inspirés par la complexité, Diffie et Hellman ont proposé de porter à son terme ultime le deuxième principe de Kerckhoffs. Ce n’est plus seulement le système qui peut tomber entre les mains de l’ennemi. Donnons-lui la clé de chiffrement. Après tout, seule la clé de déchiffrement protège le message. C’est la parabole du cadenas. La cryptologie à clé publique de Diffie et Hellman, c’est le cadenas. La fermeture est libre, seule l’ouverture est contrôlée par une clé. En réalité, il reste bien deux clés : celle qui sert au chiffrement est connue de tous, on l’appelle la clé publique ; celle qui sert au déchiffrement est secrète, on l’appelle la clé privée. Naturellement, un adversaire ne doit pas être capable de calculer la clé privée à partir de la clé publique, du moins un adversaire au sens de la théorie de la complexité, c’est-à-dire dont la puissance de calcul n’est pas illimitée. Plus important encore : dans l’article de Diffie et Hellman, l’authenticité acquiert un rôle tout aussi essentiel que la confidentialité, s’agissant des fonctionnalités de la cryptologie. Diffie et Hellman montrent en effet qu’un système de cryptographie à clé publique permet l’analogue d’une signature numérique, ce que l’on appelle la non-répudiation.

Entrons maintenant dans le vif du sujet. Ce détour par mon parcours et par quelques livres choisis a fait plus que planter le décor. Il faut maintenant mettre en perspective la cryptologie avec d’autres branches du savoir : l’informatique, et en particulier les algorithmes, les mathématiques, la technologie, la finance et enfin la physique.

Cryptologie, algorithmes et mathématiques

Cryptologie et algorithmes

Cryptologie et algorithmes sont intimement liés. Le mot « algorithme » vient du nom du savant perse Al-Khwârizmî, qui a exercé avec Al-Kindi au sein de la Maison de la sagesse. Cette parenté ne s’est jamais démentie. Turing, l’un des pères de l’informatique, n’a pas seulement inventé la machine qui porte son nom, il a aussi contribué à la définition de véritables ordinateurs vers la fin de la Seconde Guerre mondiale. L’avènement de l’informatique a conduit à faire effectuer par un algorithme les enchaînements de substitutions et de transpositions nécessaires à la cryptologie. C’est ainsi qu’est né le concept d’algorithme cryptographique, opérant à la fois sur un texte clair et sur une clé pour calculer ce que l’on appelle un cryptogramme ou chiffré. Cet algorithme doit répondre à des exigences contradictoires. Tout d’abord, il doit être le plus simple possible pour l’ordinateur. On a donc éliminé les références aux alphabets et travaillé sur les unités minimales d’information : les bits 0 ou 1. Ensuite, il doit être, comme l’avait énoncé Kerckhoffs, indéchiffrable ; mieux, il faudrait qu’il réalise le secret parfait au sens de Shannon. Mais là on en demande trop. Ce secret parfait ne peut être réalisé qu’avec une clé aussi longue que le texte clair. Un compromis est donc nécessaire, et celui-ci vient de la théorie de la complexité. On demande que le secret apparaisse parfait à un adversaire dont la puissance de calcul est limitée – par le temps d’exécution ou par le coût. La réalisation concrète de ce compromis est-elle un art ou une science ? S’agit-il de créer ou d’expliquer et de prévoir ? La question se pose pour toute l’informatique, mais aujourd’hui, à l’heure de l’intelligence artificielle, tant en ce qui concerne la cryptologie que les autres domaines du numérique, la réponse est claire : c’est une science. Mais qu’en était-il il y a cinquante ans, avant l’apparition de l’article de Diffie et Hellman ?

Pour pouvoir parler de science, il faut disposer au moins d’un premier objet d’étude emblématique, même si ce n’est qu’un artefact. Cet objet, ce fut le DES (Data Encryption Standard), un algorithme conçu en 1975 par une équipe d’IBM, normalisé un peu plus tard et très utilisé ensuite, notamment dans le milieu bancaire. Il s’agit d’un algorithme de chiffrement par bloc. Le chiffré est une suite de 64 bits obtenue à l’aide d’une clé de 56 bits. Ce sont de petits blocs, puisque 64 bits permettent de chiffrer au plus huit lettres. Il existait une autre espèce d’algorithme, l’algorithme de chiffrement par flot, qui consiste à générer une suite de bits aussi aléatoire que possible à partir de la clé et à combiner cette suite au texte clair par une addition – une addition de cryptologues et d’informaticiens, où 1 + 1 ne fait plus 2, mais 0.

Le chiffrement par bloc s’est révélé plus versatile. Il permet d’abord la création d’un flot, par exemple en chiffrant des nombres entiers consécutifs. Il permet aussi de chiffrer des messages plus longs en décomposant le message bloc par bloc, ou mieux, en chaînant les blocs, c’est-à-dire en modifiant chaque bloc du texte clair par l’addition du bloc précédent du texte chiffré. Il permet enfin la création d’un authentifiant en ne conservant que le dernier bloc chiffré d’un tel chaînage. L’authentifiant est vérifié par quiconque possède la clé, en appliquant simplement au texte clair à authentifier l’algorithme de chaînage. Voilà pour la confidentialité et l’authenticité, mais que devient l’intégrité, cette troisième fonctionnalité de la cryptologie ?

L’intégrité peut être assurée par un algorithme sans la moindre clé secrète. Encore un paradoxe, bien illustré par la parabole des tiroirs. Dans la pratique, on constate que, si l’on a un grand nombre d’objets à ranger dans un petit nombre de tiroirs, deux objets au moins vont dans le même. Appelons cela une collision. En algorithmique, ce n’est pas tout à fait la même chose. Si l’on manipule les objets et les tiroirs avec un algorithme qui retourne le numéro du tiroir où on range l’objet, on peut envisager que deux objets en collision soient concrètement hors de portée d’un adversaire de puissance de calcul limitée. L’algorithme prend alors le nom de fonction de hachage cryptographique et garantit l’intégrité de l’objet auquel on l’applique. Je reviendrai sur ce concept qui est devenu, au-delà du paradoxe, un véritable couteau suisse de la cryptologie moderne.

Mais restons-en pour le moment au DES. Il s’est révélé un bon algorithme durant la vingtaine d’années où il a été recommandé. Il a bien sûr été disséqué dans tous les sens par la communauté cryptologique qui s’est constituée après l’article de Diffie et Hellman. Mais ce n’est qu’au bout de dix-sept ans que sont apparues presque coup sur coup deux méthodes d’analyse, que l’on pourrait considérer comme des faiblesses de l’algorithme, bien qu’elles ne le mettent pas, en pratique, en danger. Ces méthodes très profondes et innovantes s’appellent la cryptanalyse différentielle et la cryptanalyse linéaire.

La première est l’étude de l’effet de différences d’informations minimes entre deux clairs de 1, 2 ou 3 bits. Certaines de ces différences peuvent être suivies à la trace tout au long de l’exécution de l’algorithme. Cela montre que les deux chiffrés correspondants sont distinguables de couples aléatoires, ce qui ouvre, selon la règle de Shannon, une brèche qui permet une attaque. Cette attaque requiert toutefois une quantité massive de couples constitués d’un clair et d’un chiffré, ce dont on ne dispose pas en général. Le biais statistique est en effet très faible.

La seconde est la cryptanalyse linéaire qui étudie de manière probabiliste certaines sommes de bits de clairs et de chiffrés, toujours avec la règle 1 + 1 = 0 de calcul sur les bits. Ces approximations linéaires ne se comportent pas comme des bits aléatoires et permettent là encore d’accéder à la clé. La méthode nécessite toujours un nombre très important de couples clair/chiffré, trop important pour constituer une attaque pratique. Si le DES a succombé, c’est uniquement à cause de la taille des clés, 56 bits, un choix critiqué dès l’origine, qui a permis une recherche exhaustive, c’est-à-dire l’essai l’une après l’autre de toutes les clés de 56 bits en les mettant bout à bout. Cela ne fait que 256 téraoctets à examiner, et c’est donc parfaitement possible aujourd’hui.

Dans le milieu académique, cette recherche exhaustive a été pratiquée dès la fin du XXe siècle, de plusieurs façons. D’abord, des compétitions ouvertes sur Internet. Par la méthode du calcul distribué, qui consiste à résoudre un problème en utilisant à distance des processeurs oisifs mis à disposition par les membres d’un réseau, on est parvenu à cryptanalyser le DES. On l’a fait également par la construction d’une machine composée d’un ensemble de processeurs informatiques dédiés.

Le grand mérite du DES est d’avoir permis que la conception d’algorithmes cryptographiques ne soit plus seulement un art, mais s’appuie sur un minimum de critères vérifiables, qui garantissent notamment la résistance à l’application des méthodes différentielles et linéaires. Ainsi, la cryptanalyse n’est plus, comme par le passé, la capacité à gagner un avantage stratégique sur l’adversaire, mais devient une méthode de recherche destinée à progresser dans la conception d’algorithmes cryptographiques plus solides. C’est bien une démarche scientifique, et nous y avons participé avec l’équipe que j’ai créée et animée à l’École normale supérieure. Nous avons inventé des algorithmes, nous en avons expertisé d’autres, nous avons pris part à l’aventure intellectuelle qui a conduit au remplacement du DES par un autre algorithme, l’AES (Advanced Encryption Standard).

Cela s’est fait au moyen d’un appel d’offres ouvert. Pour participer, il fallait soit concevoir et proposer un algorithme, soit chercher à casser ceux des autres. Nous avons fait les deux. Nous n’avons pas gagné, mais nous avons vu avec plaisir nos voisins et amis belges remporter cette compétition. La méthode de l’appel d’offres ouvert a d’ailleurs fait florès. Elle a été utilisée également pour remplacer diverses fonctions de hachage cryptographiques conçues dans les années 1990. Ces fonctions, répondant aux noms codés de MD4, MD5 (Message Digest 4 et 5) et SHA1 (Secure Hash Algorithm 1), ont toutes fait l’objet d’attaques, souvent d’ailleurs par des variantes de la cryptanalyse différentielle.

Dans l’appel d’offres qui a permis de définir la fonction de hachage SHA3, il y a eu vingt-cinq propositions, sans compter celles qui ont été retirées parce que des failles avaient été trouvées. Entre-temps, il y a eu une fonction SHA2, mais ça n’était pas un appel d’offres. Le vainqueur de la compétition pour SHA3 a été annoncé en 2012 : il était temps. En 2017, une véritable collision a été calculée pour la fonction de hachage SHA1. Cinq ans, ça n’était pas trop pour éliminer l’usage d’une fonction qui était largement utilisée.

Cryptologie et mathématiques

Depuis des siècles, les cryptologues s’appuient sur les mathématiques. D’ailleurs, le mot « chiffre », d’origine arabe, désigne à la fois une méthode de cryptographie et la suite des symboles de la numération décimale. Toute l’analyse des fréquences des lettres dont il a déjà été question repose sur l’utilisation de statistiques. On a donc affaire à un long compagnonnage. Mais les véritables fiançailles des mathématiques modernes et de la cryptologie, c’est l’article de Diffie et Hellman de 1976. Le mariage a eu lieu deux ans plus tard avec l’algorithme RSA, du nom des inventeurs du premier système de chiffrement à clé publique : Ronald Rivest, Adi Shamir et Leonard Adleman.

Mathématiques modernes, mais pas tant que ça. Tous les ingrédients de la cryptologie à clé publique étaient disponibles depuis plus de deux siècles. Il suffit pour s’en convaincre de feuilleter les commentaires de l’Académie des sciences de Saint-Pétersbourg de l’année 1763. On y trouve un très bel article écrit en latin par un autre Leonard, Leonhard Euler, l’un des plus grands mathématiciens de tous les temps. Euler a fait des contributions multiples, mais ce qui nous intéresse ici, c’est la théorie des nombres : l’étude des nombres entiers (1, 2, 3, etc.) et des nombres premiers, ceux qui n’ont pas de diviseurs autres qu’eux-mêmes et l’unité (2, 3, 5, 7, etc.). La théorie des nombres s’intéresse à leurs propriétés, et aux opérations auxquelles on peut les soumettre : addition, multiplication et élévation à une puissance, que l’on appelle aussi exponentiation. L’exponentiation, c’est la répétition de la multiplication : 2 puissance 3, c’est 2 × 2 × 2, soit 8, et 2 puissance 4 c’est 2 × 2 × 2 × 2, soit 16. L’article d’Euler établit une très belle propriété de l’exponentiation dans une arithmétique dite modulaire. Dans l’arithmétique des bits, 1 + 1 = 0. Dans l’arithmétique modulo 3, 1 + 1 reste bien égal à 2, mais c’est 1 + 2 qui vaut non plus 3, mais 0, et ainsi de suite.

Rivest, Shamir et Adleman ont magistralement vu que le théorème d’Euler avait des conséquences sur l’exponentiation modulaire, dans le cas où le modulo n est le produit de deux nombres premiers p et q. L’élévation à une puissance fixe est alors facile à calculer, même sans connaître p et q. Elle peut être inversée par un calcul facile à qui connaît p et q. En revanche, elle semble incroyablement difficile si on ne connaît que n. Le cryptosystème RSA était né.

Les symboles n, p et q sont les mêmes dans l’article d’Euler de 1783 et dans celui de 1978 qui définit le RSA. Ce n’est pas un hasard. Les plus beaux textes mathématiques se perpétuent et restent souvent, y compris leurs notations, gravés dans le marbre. Leurs usages futurs restent mystérieusement imprédictibles. Certes, Euler ne dédaignait pas les tâches pratiques. Au-delà de sa productivité mathématique intense, il établissait les cartes géographiques du tsar – on dit qu’il s’y est abîmé les yeux. Mais si on lui avait demandé de deviner lequel de ses articles serait la source d’une invention utilisée quotidiennement par des milliards de personnes, il aurait peut-être cité sa célèbre solution au problème des sept ponts de Königsberg, établissant qu’on ne pouvait visiter cette ville sans revenir sur ses pas, plutôt qu’un article d’arithmétique modulaire.

L’invention du RSA a soulevé de nombreuses questions auxquelles se sont attachées plusieurs équipes, dont celle que j’ai réunie à l’ENS. Comment choisir les paramètres ? Peut-on garantir le niveau de sécurité ? RSA est-il l’unique exemple de cryptologie à clé publique ? Le choix de ses paramètres est une question profonde qui vient de la théorie de la complexité. RSA pourrait succomber si l’identité P = NP était un jour établie. Mais il pourrait aussi succomber sous l’effet d’avancées en théorie des nombres conduisant à un choix de paramètres totalement impraticables, c’est-à-dire des entiers p, q et n de taille gigantesque.

Où en sommes-nous aujourd’hui ? Les compétitions ouvertes dans le style de celles que j’ai évoquées pour le DES apportent des réponses. Concernant le RSA, le record est longtemps resté celui établi en 2009 : la factorisation d’un nombre n de 768 bits aboutissant aux deux entiers cachés p et q, dont il est le produit, par un effort de calcul distribué très significatif. Ce record a été amélioré à deux reprises, fin 2019 et début 2020, par une équipe comprenant plusieurs de mes anciens élèves de l’ENS. On en est ainsi à 829 bits, soit 250 chiffres décimaux. Cela conduit, du côté des défenseurs, à utiliser un modulo d’une taille supérieure à 500 chiffres ou plus, ce qui reste praticable pour les machines actuelles. La sécurité est-elle ainsi garantie ? Oui, au sens du premier principe de Kerckhoffs : le système est matériellement indéchiffrable ; mais non, au sens de Shannon : il n’est évidemment pas mathématiquement indéchiffrable.

Il y a un autre problème, plus concret : les messages ne se présentent pas naturellement comme des entiers de 500 chiffres. Il faut les formater pour que l’ordinateur les traite sans ambiguïté. Ce n’est pas compliqué, mais c’est source d’erreurs. De plus, ce formatage peut être trop naïf. En effet, le RSA ne résiste pas aux méthodes de mots probables d’Al-Kindi et de Turing. Si l’on souhaite déchiffrer un mot du dictionnaire chiffré par un codage connu, on peut appliquer l’algorithme de chiffrement RSA à tous les mots du dictionnaire et retrouver le bon. Le formatage doit donc nécessairement avoir une part d’aléa. Comment faire alors pour garantir que la sécurité du RSA formaté soit précisément celle qui découle de nos connaissances de théorie des nombres sur la factorisation, ni plus ni moins ? C’est une question qui a motivé d’intenses recherches dès l’invention du RSA. Le premier pas a été de formaliser, c’est-à-dire d’inventer, une notion de sécurité qui soit l’équivalent du secret de Shannon, mais dans le cadre de la théorie de la complexité, autrement dit face à un adversaire dont la puissance de calcul n’est pas illimitée. Après beaucoup d’efforts, on est parvenu à isoler une expérience de pensée que je vais décrire de manière simplifiée.

Imaginons un adversaire et laissons-le choisir deux messages, puis présentons-lui le chiffrement de l’un des deux choisis au hasard. Demandons-lui alors de deviner de quel message il s’agit. Notons la réponse et recommençons. La sécurité est acquise si l’adversaire ne fait significativement pas mieux que de donner la bonne réponse une fois sur deux, ce que n’importe qui peut faire en tirant à pile ou face. Cela semble bien ludique, mais ce formalisme autorise de véritables preuves mathématiques. Il conduit à ce que l’on appelle la sécurité prouvée, à laquelle mon équipe a consacré de nombreux travaux. Par exemple, nous avons garanti la sécurité d’un mécanisme de formatage pour le RSA appelé OAEP (Optimal Asymmetric Encryption Padding). Nous avons ainsi établi la solidité du lien entre les mathématiques du RSA et l’algorithmique qui le met en pratique.

Ayant clarifié le statut de la sécurité du RSA, tournons-nous vers les alternatives. Évidemment, il y a eu de nombreuses tentatives pour proposer d’autres systèmes de cryptologie à clé publique et de nombreux travaux pour les cryptanalyser. Dans ce domaine, mes élèves et moi étions plutôt du côté des attaquants. Mais l’attaque en cryptologie ouvre parfois la voie à une défense plus efficace.

Une dizaine d’années après le RSA, on a proposé d’utiliser les courbes elliptiques. Ce sont des structures géométriques munie d’une opération d’addition. Méfions-nous de la terminologie, car ce ne sont pas des courbes qui ressemblent à des ellipses. Des travaux d’Euler, encore lui, ont conduit à la définition des intégrales elliptiques qui servent à calculer la longueur des arcs d’ellipse. Une vision géométrique de ces intégrales a mené aux courbes elliptiques. C’est un domaine profond et élégant des mathématiques qui est essentiel à la démonstration du célèbre théorème de Fermat, démontré en 1994, plusieurs siècles après avoir été énoncé. Les cryptologues se sont également emparés des courbes elliptiques, et cela leur a permis de produire des analogues du chiffrement et de la signature RSA avec des tailles de clés plus réduites pour une sécurité équivalente au regard de l’état de l’art. Ces solutions sont normalisées et utilisées, dans une moindre mesure que le RSA toutefois.

Un autre domaine a été exploré avec beaucoup moins de succès : celui des corps finis. Ce sont des structures finies munies d’une addition et d’une multiplication, avec les propriétés habituelles de ces opérations. L’exponentiation peut naturellement y être considérée, mais elle ne conduit pas directement à un système à clé publique. On a cherché à contourner astucieusement cette difficulté, mais tous les efforts ont conduit à l’échec. Le dernier en date est le système de signature SFLASH, qui s’est éteint en 2007, six ans après son invention. Cela lui avait laissé juste le temps d’être adopté comme norme, mais heureusement pas d’être mis en œuvre massivement. La cryptanalyse que nous en avons faite dans mon équipe s’est inspirée de la recherche d’invariants de la cryptologie traditionnelle, mais ce sont cette fois-ci des invariants algébriques, et non plus seulement statistiques.

Une autre source fructueuse de sujets de cryptanalyse, vient d’une série de propositions dite « du sac à dos ». On dispose d’une suite d’objets de longueur fixée, qui sont des nombres entiers, et on chiffre un message formé d’une suite de bits de même longueur. Chaque bit sélectionne l’objet situé à la même position. On met l’objet dans le sac si le bit vaut 1, sinon on l’abandonne. Finalement, on additionne tous les objets du sac. Tout cela est très simple, trop simple. Ce qui est intéressant ici, ce sont les outils mathématiques qui permettent les attaques : les réseaux euclidiens. Ce sont des outils que j’aime bien car je les ai moi-même utilisés dans mon premier travail sur le générateur d’aléa de Knuth. Ils réalisent des arrangements réguliers de points dans l’espace à n dimensions. En dimension 3, on peut les voir comme les sommets des mailles d’un cristal. Avec un peu d’imagination, on passe en dimension n. Dans ce cas, le nombre de sommets de la maille est exponentiel en n. Un résultat du mathématicien allemand du XIXe siècle, Hermann Minkowski, montre qu’il existe toujours deux points distincts du réseau assez proches l’un de l’autre. On peut borner la distance de ces deux points en fonction du volume de la maille. De même, étant donné un point quelconque de l’espace, il y a un point du réseau qui lui est proche. Du point de vue algorithmique, comme toujours, les choses se compliquent. Il existe en effet plusieurs façons de mailler le réseau et, en général, le calcul semble très difficile. Au mieux, on peut se rapprocher de l’optimum, c’est-à-dire du point le plus proche d’un point donné. Cela suffit néanmoins pour beaucoup d’attaques que nous avons menées. Là encore le réseau s’introduit comme un invariant algébrique lié à un algorithme de chiffrement et des points proches donnent une indication précieuse sur la clé. Mais ce n’est pas la fin de l’histoire.

La suite s’écrit du côté de la cryptographie et non plus de la cryptanalyse. Elle commence une année après le RSA par un scénario simple. On sauvegarde des données à distance, on dirait aujourd’hui dans le cloud. Ces données, on va bien sûr les chiffrer pour atteindre un bon niveau de sécurité. Puis on désire modifier l’une d’entre elles. Y a-t-il un moyen de le faire sans déchiffrer la donnée et la rechiffrer, c’est-à-dire en calculant directement la modification à effectuer ? On parle de chiffrement homomorphe, le mot venant de l’algèbre et désignant des transformations qui préservent certaines opérations mathématiques. Aujourd’hui, ce type de chiffrement a des applications potentielles dans des industries très régulées en matière de protection des données personnelles sensibles, comme les industries de santé.

Mais revenons à la première solution proposée en 2009, c’est-à-dire trente ans après le RSA. Par un paradoxe dont la cryptologie est coutumière, ce sont les réseaux, un des outils privilégiés des cryptanalystes, qui sont à l’œuvre. L’opération de base du chiffrement est l’ajout d’une petite erreur à un point d’un réseau, celle du déchiffrement repose sur la connaissance secrète d’une représentation particulière de la maille du réseau, qui permet de corriger l’erreur. Comment expliquer que ces réseaux soient une sorte de Janus, ce dieu romain à deux faces ? Il n’y a pas de mystère. Les algorithmes de calcul sur les réseaux sont, tout comme ceux qui factorisent des entiers, de type sous-exponentiel. Leur efficacité diminue avec la dimension, mais pas exponentiellement. Pas si brutalement que ça. Tout l’art du cryptographe, c’est de trouver des dimensions où son adversaire, le cryptanalyste, est démuni car son algorithme préféré n’opère plus, mais en même temps des dimensions qui restent pratiques pour les applications. Autre enseignement : une fois encore, la cryptanalyse n’est plus, dans le milieu académique ouvert, un moyen de se doter d’un avantage compétitif sur un adversaire, mais fait partie des méthodes de conception et d’évaluation des algorithmes.

Le même paradoxe de retournement d’un outil de cryptanalyse vers la cryptographie s’est produit lors de la solution d’un autre problème posé très tôt après l’invention du RSA. C’était en 1984, lors du premier congrès de cryptographie tenu à Paris. La question est naturelle : puisque la clé de chiffrement d’un système de cryptologie à clé publique est connue de tous, ne pourrait-on pas la choisir ? Ça permettrait de prendre son numéro de téléphone, son email ou un autre élément de son identité facile à retenir. La solution n’est venue qu’au début des années 2000 par un détour étonnant : les courbes elliptiques. Comme je l’ai déjà dit, le principal intérêt de ces courbes pour la cryptologie, c’est qu’elles autorisent des dimensions de clés plus réduites que le RSA, au regard de l’état de l’art. Toutefois, on a rapidement réalisé que certaines courbes devaient être évitées, celles qui admettent une opération supplémentaire, le couplage, introduit par André Weil. Les cryptanalystes ont vu que le couplage de Weil menait à des algorithmes sous-exponentiels, et qu’ainsi l’avantage compétitif de la taille des clés était perdu. Fin de l’acte 1.

L’acte 2 commence par un jeu. Il y a trois joueurs. Chacun a le droit de parler une et une seule fois. Une fois ces annonces faites, chaque joueur peut en déduire un secret, le même pour les trois. Comment est-ce possible ? C’est un jeu très sérieux. Cette question avait déjà été résolue pour deux joueurs dans l’article fondateur de Diffie et Hellman de 1976. L’opération est connue sous le nom d’échange public de clé, et c’est d’ailleurs un substitut à la cryptologie à clé publique dans un grand nombre d’applications. C’est précisément le couplage sur les courbes elliptiques qui a permis la généralisation, c’est-à-dire le passage de deux à trois joueurs, et, quelques mois plus tard, l’invention de la cryptologie fondée sur l’identité. Tout n’était donc pas perdu pour l’utilisation des courbes elliptiques munies d’un couplage, à condition de choisir convenablement les paramètres. Au contraire, tout comme le chiffrement homomorphe, la cryptographie par l’identité s’est révélée une fructueuse voie de recherche permettant de nouvelles fonctionnalités et de nouvelles applications. La cryptologie ne s’est ainsi pas arrêtée à la fin du XXe siècle, et la communauté de recherche a montré sa capacité d’innovation en résolvant des problèmes anciens et en ouvrant de nouvelles pistes. Elle est ainsi prête pour de nouveaux défis.

Cryptologie et technologies

De manière insoupçonnée, la proximité entre la cryptologie et les technologies liées aux infrastructures numériques est tout aussi forte que celle que l’on vient d’appréhender pour les mathématiques. Pour résumer de façon un peu provocatrice, des milliards de personnes portent en permanence sur elles un processeur cryptographique, et des milliards de clés cryptographiques sont régulièrement créées. Il n’y a rien de mystérieux dans cette affirmation que l’on peut illustrer par quelques exemples : téléphone, moyens de paiement, Internet.

Le téléphone portable

Chaque appareil embarque un processeur cryptographique. Je ne parle pas seulement des appareils les plus récents, ni des processeurs généralistes qui gèrent l’écran, les communications, la localisation, l’appareil photo. Ceux-ci réalisent aussi des opérations cryptographiques, notamment dans certaines applications comme WhatsApp ou Telegram, qui font du chiffrement de bout en bout, c’est-à-dire directement entre les deux appareils qui échangent des messages. Non, je parle de la puce amovible présente dès les années 1990 et dont la fonction essentielle est de permettre l’authentification de l’abonné par l’opérateur au moyen d’un algorithme conventionnel, et non par une méthode à clé publique. Il y a d’ailleurs, concernant ces algorithmes, un historique de défense et d’attaque. Comme souvent en cryptographie, ce qui a été conçu à l’origine était parfois un peu faible. Des attaques permettant de récupérer la clé secrète de l’abonné ont vu le jour dans un contexte restreint où l’on a accès à la puce, par exemple en empruntant le téléphone. Incidemment, l’algorithme ne respectait pas le deuxième principe de Kerckhoffs. Et c’est précisément quand la spécification secrète de l’algorithme a été publiée que sont apparues les attaques. Tout cela a été rapidement corrigé. Les algorithmes sont devenus publics. Ils sont expertisés par des laboratoires industriels et académiques, comme le mien.

Moyens de paiement

Si l’on veut un exemple de processeur cryptographique manipulant des algorithmes à clé publique, celui des cartes de crédit s’impose. Aujourd’hui, les cartes de crédit ont toutes ou presque un cryptoprocesseur et disposent de toute la panoplie des algorithmes cryptographiques, clé publique et clé conventionnelle, qu’elles utilisent efficacement. Je ne parle évidemment pas du code PIN à quatre chiffres, qui est très utile, mais qui n’identifie que le lien entre le porteur et la carte, mais bien des algorithmes qui authentifient les cartes elles-mêmes et leurs transactions. Le succès a été au rendez-vous.

J’ai fait partie pendant quelques années d’un observatoire sur la sécurité des cartes de paiement. Les rapports publiés par cet organisme ont montré une forte corrélation entre le renforcement des moyens cryptographiques et la diminution de la fraude. De plus, c’est une success story française. C’est en 1985 que les cartes de crédit ont été dotées en France d’une puce. Il a fallu attendre dix ans pour que le Royaume-Uni adopte à son tour le chip and PIN (puce et code), et encore dix ans de plus pour les États-Unis.

Internet

Comment passer sous silence la présence d’algorithmes cryptographiques dans de nombreux protocoles de l’Internet, ces ensembles de règles qui régissent les échanges de données entre machines connectées au réseau et qui sont mises en œuvre au moyen d’algorithmes appropriés ? Je me bornerai à évoquer ici le protocole TLS (Transport Layer Security), utilisé par les navigateurs dans l’extension sécurisée du protocole de transfert de données HTTP. La combinaison prend alors le nom HTTPs et est signalée par le navigateur au moyen d’un petit cadenas évocateur. Pour comprendre la nécessité de ces protocoles cryptographiques, il faut revenir au début des années 1990, quand sont apparus les premiers navigateurs. Je me souviens de mon enthousiasme lorsqu’un collègue m’a fait une première démonstration de l’un d’eux, qui s’appelait Mosaic. Instantanément, nous nous sommes mis à créer des pages Web pour le laboratoire.

Dans le grand public, l’adoption n’a pas été aussi rapide. Il y avait à l’époque une certaine réticence, notamment à entrer des données sensibles dans un navigateur. Cette réticence s’opposait au développement du commerce électronique. Elle était parfaitement légitime compte tenu des risques de piratage, et c’est ce qui a motivé l’invention du protocole SSL, devenu entre-temps TLS. Lors de l’établissement d’une session TLS entre deux machines informatiques, est réalisé un échange de clé par un mécanisme de cryptologie à clé publique. Ceci permet à ces machines de disposer d’une quantité relativement minime d’information secrète en commun, quelques centaines de bits. C’est largement suffisant pour créer des clés cryptographiques partagées pour chaque connexion sécurisée de la session en utilisant une fonction de hachage comme générateur d’aléas. Avec ces clés cryptographiques partagées, on authentifie et on chiffre, à l’aide d’algorithmes conventionnels, les messages échangés lors de la connexion. Ce scénario convient parfaitement à des situations courantes, par exemple celle où le client d’une banque se connecte au serveur pour effectuer un virement. Il suffit en effet que la banque lui communique sa clé publique RSA.

Mais comment éviter la célèbre attaque dite de l’homme du milieu, en anglais man in the middle, où une troisième machine intercepte des communications en ayant échangé à leur insu une clé avec le client d’une part et avec la banque d’autre part ? Il faut, et c’est toute la subtilité du protocole, que le client, ou au moins son navigateur, valide l’adresse et la clé publique du serveur. Cela ne peut se faire ex nihilo et nécessite une infrastructure de clés publiques. Les données à vérifier doivent être signées par une autorité à l’aide de sa propre clé privée, et sa clé publique doit être signée par une autorité supérieure, et ainsi de suite, jusqu’à aboutir à une clé connue par le navigateur. Celui-ci peut alors vérifier la chaîne de signatures, qui prend le nom de certificat. La boucle est bouclée.

Comme des milliards de personnes ont aujourd’hui accès à Internet et établissent chaque jour des connexions sécurisées, cela fait bien des milliards de clés cryptographiques. La plupart sont des clés de cryptographie conventionnelle. En effet, la clé publique n’intervient que dans la phase d’établissement du TLS. D’autre part, la sécurité repose sur la vérification du certificat. Il faut donc prendre au sérieux les messages indiquant que cette vérification a échoué. Ce certificat est simplement composé d’une suite de signatures. Ainsi, ce sont les algorithmes assurant l’authenticité, plus que ceux assurant la confidentialité, qui forment la clé de voûte de la sécurité sur Internet. Enfin, ces algorithmes de signature n’opèrent que sur des données de taille fixe et réduite. Ils ne signent donc pas directement des messages, mais un condensé obtenu par application d’une fonction de hachage. Leur résistance aux collisions suffit à garantir que le message, une fois signé, ne peut plus être modifié. Le rôle des algorithmes d’intégrité est donc tout aussi essentiel que le reste de la cryptographie. Ainsi la sécurité est holistique. Si l’on essaie d’analyser le rôle que joue la cryptologie dans l’établissement ou le renforcement de cette sécurité, on doit aussi prendre en compte l’environnement, et pas seulement les algorithmes.

Il est préférable évidemment d’effectuer les opérations de cryptographie sur un matériel dédié, non connecté à Internet et enterré dans un bunker sans fenêtres. Ce n’est malheureusement pas possible. On préfère utiliser une tablette, un ordinateur, un smartphone, potentiellement vulnérables aux intrusions. Même sans parler d’intrusion, il y a d’autres voies qui permettent d’obtenir de l’information sur l’exécution d’un algorithme cryptographique : les canaux cachés, qui sont ouverts par des mesures physiques sur le comportement de la machine qui exécute l’algorithme. Par exemple, le temps de réponse dans l’établissement d’une connexion sécurisée ou bien la mesure de la puissance électrique consommée par une carte à puce. Discuter de ces environnements, qui font partie de la sécurité informatique au sens large, nous mènerait trop loin. Disons simplement qu’ils sont pris en compte, qu’ils sont l’objet d’une recherche extrêmement active et que cette recherche analyse les menaces et propose des contre-mesures.

Cryptologie et finance

Comme on l’a vu, les algorithmes cryptographiques se sont révélés précieux pour la sécurisation des transactions bancaires, des virements en ligne et des cartes de crédit. Mais je veux maintenant parler d’une tout autre ambition, née seulement quelques années après l’invention du RSA : celle de substituer à ces transactions des moyens de paiement numériques aussi anonymes que le papier monnaie, voire d’éliminer purement et simplement les États du processus de création et de contrôle de ces moyens de paiement numériques. Les premières tentatives n’allaient pas si loin. Elles suggéraient seulement un mécanisme de retrait cryptographique auprès d’une banque de devises numériques utilisables une seule fois de manière anonyme, mais elle se heurtait au problème de la double dépense. Comment empêcher une fraude consistant à dépenser deux fois, ou plus, ces billets de banque numériques ? Seule solution en apparence : la création d’une autorité centrale enregistrant les transactions au fur et à mesure et permettant leur compensation. Ce n’était pas ce qui était recherché. Une autre solution est venue bien plus tard. En octobre 2008, un chercheur japonais, Satoshi Nakamoto, a proposé un système résolvant le problème de la double dépense par l’utilisation d’un réseau de pairs. Dans un livre blanc d’une dizaine de pages, il a présenté son idée : des machines communiquant entre elles en permanence plutôt qu’une autorité centrale. Le Bitcoin était né.

Satoshi était parfaitement inconnu dans la communauté de la cryptologie, et il l’est toujours. On ne sait pas qui il est, on ne l’a jamais vu, bien que de nombreux journalistes l’aient cherché. On soupçonne bien sûr qu’il s’agit du pseudonyme de quelqu’un de très discret. Vu l’envolée des cours du Bitcoin, il est sans doute riche à milliards, mais il semble qu’il n’ait rien dépensé de sa fortune.

Le système Bitcoin repose sur plusieurs méthodes informatiques déjà connues, mais dont la combinaison est exceptionnellement remarquable. Tout d’abord, le grand livre distribué et public, maintenu par tous les membres du réseau de pairs. On y trouve une suite numérotée d’entrées, les blocs, contenant toute l’information sur chaque transaction depuis l’origine. La chaîne de blocs inscrits dans le grand livre est protégée en intégrité par l’insertion, dans chaque bloc, d’une valeur de hachage calculée sur le bloc précédent. Chaque transaction est authentifiée par l’usage de signatures numériques. Pour être plus précis, ce sont des signatures fondées sur les courbes elliptiques. Les transactions contiennent toute l’information nécessaire à la vérification, à l’aide du grand livre, qu’il n’y a pas de double dépense. Au moment d’un paiement, la transaction correspondante est diffusée au réseau et mise en attente. Et c’est là qu’intervient l’idée proprement révolutionnaire de Nakamoto. Pour permettre de confirmer les transactions en les incluant de manière ordonnée dans un bloc du grand livre, il faut réaliser un consensus entre les pairs. Satoshi y parvient en organisant une loterie compétitive entre eux. Tels des chercheurs d’or, les pairs participants, que l’on appelle les mineurs, ont à faire un travail difficile : ils doivent résoudre un puzzle cryptographique nécessitant une puissance de calcul déterminée. Les mineurs calculent successivement, pour résoudre le puzzle, un très grand nombre de valeurs de hachage. Le plus chanceux, ou celui qui a le plus d’ordinateurs, termine le calcul en premier et gagne le droit d’inscrire le bloc. Et surtout, il gagne une récompense en Bitcoins. Dans le même temps, les transactions du bloc sont confirmées. Et tout cela fonctionne.

À l’heure où je parle, la taille du grand livre est de l’ordre de 250 gigaoctets et le Bitcoin vaut plusieurs milliers d’euros alors qu’au début sa valeur était celle d’un billet de Monopoly. D’ailleurs, on connaît le nom de celui qui a reçu de Satoshi lui-même la première transaction en Bitcoins. Paradoxalement, c’est l’un des candidats les plus sérieux qu’on puisse identifier à Nakamoto. Il ne dira pas son secret car il est décédé en 2014 des suites d’une maladie invalidante.

Il est intéressant de noter qu’il était, comme beaucoup d’adeptes de la première heure du Bitcoin, un militant radical proche du transhumanisme, convaincu de la possibilité d’un progrès illimité par les sciences et les techniques, et assignant en particulier à la cryptographie un rôle essentiel de transformation sociale vers un monde libre et sans contraintes, un monde où le pouvoir serait aux mains des individus plutôt que dans celles des gouvernements. On comprend donc que le Bitcoin était à ses débuts une philosophie. Il est aujourd’hui une technologie que l’on présente parfois comme universelle, la chaîne de blocs ou blockchain, en faisant l’impasse sur son principal inconvénient : elle est très gourmande en puissance de calcul et l’ensemble des mineurs de Bitcoin consommerait aujourd’hui autant d’électricité qu’un pays comme la Suisse. Et c’est sans compter les autres cryptomonnaies : Ethereum, Litecoin, Ecash, Monero, etc. Or, sans le concept de preuve de travail qui est central dans les puzzles du Bitcoin, il devient très facile de mettre en œuvre des attaques en créant, sans effort et sans coût, de multiples participants fantômes permettant le détournement du système.

Pour se passer de preuves de travail, on a imaginé d’autres mécanismes permettant de maintenir le consensus sur le grand livre. La preuve d’enjeu, une autre forme de loterie compétitive pour désigner celui qui valide un bloc supplémentaire, procède par tirage au sort. Chaque participant reçoit un nombre de billets de loterie proportionnel à la quantité de cryptomonnaie qu’il possède. Il y a pas mal de variantes. La plus extrême et la plus simple est celle où la validation est faite par des participants habilités. Mais là on revient à l’autorité centrale, c’est-à-dire au point de départ il y a quarante ans, et on est bien loin de la philosophie qui guidait le ou les inventeurs du Bitcoin.

Cryptologie et physique

En finance, le possesseur d’un euro ou d’un Bitcoin le dépense ou non. En physique quantique, c’est plus compliqué ; un chat peut être à la fois mort et vivant. Je fais référence à la célèbre expérience de pensée proposée en 1935 par le physicien autrichien Erwin Schrödinger. La vie de ce chat, enfermé dans une boîte avec un dispositif détectant un seuil de radiation et libérant alors un produit mortel, dépend de la désintégration d’un atome. Cette désintégration n’est pas représentée par un bit 0 ou 1, comme en informatique, mais par un bit quantique, un qubit, qui est une superposition d’états. Ce chat, qui est à la fois mort et vivant tant qu’on n’a pas ouvert la boîte, allait devenir un siècle plus tard une menace existentielle pour les infrastructures construites autour de la clé publique et du RSA.

En fait, il y a eu, comme souvent en cryptologie, un effet de balancier, et celui-ci est parti cette fois de la cryptographie vers la cryptanalyse. L’histoire débute dès 1984 par un mécanisme quantique d’échange de clé cryptographique qui a été proposé et expérimenté. L’échange consistait en une suite de photons polarisés émis dans l’air ou sur une fibre. Ceci est particulièrement adapté à l’échange de clé avec un satellite. Ces photons ont des propriétés quantiques, mais, convenons-en, ils sont plus simples à manipuler que des boîtes avec des chats. Des bits classiques étaient émis en parallèle sur une voie conventionnelle. Une élégante combinaison des deux, le quantique et le classique, permettait à deux participants de s’accorder sur une suite secrète de bits, des vrais, 0 ou 1. La sécurité vis-à-vis d’un adversaire tentant d’intercepter tout ou partie de l’échange et d’en déduire tout ou partie de la clé était d’une nature nouvelle. Ce n’était pas le secret parfait de Shannon, mais c’était bien plus que le secret algorithmique de la cryptologie. C’était un secret fondé sur les lois de la physique. La crypto quantique n’est pas une expérience de pensée. Elle fonctionne. Le record de distance a été établi en 2018 par un échange à 421 kilomètres de distance, sur une fibre optique de très haute qualité. Malgré tout, la cryptologie quantique reste limitée par le fait qu’elle ne gère pas simplement la question de l’authenticité. Elle se heurte aussi à des problèmes opérationnels dans la gestion des clés. N’oublions pas que ce sont des milliards de clés qui permettent chaque jour l’établissement de connexions sécurisées sur Internet. La cryptologie quantique ne sera donc pas la solution face aux menaces qui se profilent sur la cryptologie à clé publique et qui viennent aussi de l’univers quantique.

Quelles sont ces menaces ? Dès les années 1980, des chercheurs ont proposé un équivalent quantique de la machine de Turing. Au lieu d’opérer sur des bits 0 ou 1, on opère sur ces fameux qubits, des superpositions de bits quantiques. De manière imagée, on joue à chat dans le jardin de Schrödinger. Tout cela est-il bien sérieux et tout cela concerne-t-il la cryptologie ? De façon surprenante, oui. En 1994, un chercheur des laboratoires Bell, les fameux Bell Labs où Shannon avait fait ses premières découvertes, a proposé un algorithme quantique efficace pour factoriser, et ainsi casser le RSA en trouvant les deux facteurs premiers du modulo. Un drame pour la cryptologie.

J’ai été invité aux Bell Labs cette année-là et j’ai entendu un magnifique exposé de l’auteur. Mais cela ne m’a pas empêché de dormir. Il n’y avait pas de machine quantique. De retour à Paris, les physiciens de l’École normale m’ont expliqué le phénomène de décohérence quantique qui allait rendre très difficile la construction d’une telle machine.

Où en sommes-nous vingt-cinq ans plus tard ? D’abord, on a compris que la machine quantique, si on la construisait, allait casser non seulement le RSA, mais aussi la cryptologie à l’aide de courbes elliptiques. Incidemment, cela aurait donc des conséquences sur le Bitcoin. Mais on a aussi compris qu’il faudrait encore du temps pour y arriver, et que l’on n’est pas sûr de pouvoir y arriver un jour. Le record de factorisation quantique par l’algorithme découvert en 1994 date de 2012. Cette année-là, un ordinateur quantique a réussi à factoriser l’entier 21 (3 × 7). Pas encore de quoi faire des insomnies : le calcul est à la portée d’un enfant pour un coût très inférieur.

Il existe bien des records un peu plus impressionnants, mais établis par un algorithme plus simple. Rien n’indique cependant qu’ils passent à l’échelle pour les très grands nombres que manipule le RSA. Avec cet algorithme, on en est en 2018 à des entiers de 22 bits, bien loin des tailles de l’ordre de 1 500 ou 2 000 bits recommandées pour le RSA. Le record a été établi avec une machine expérimentale IBM de 16 qubits et ne constitue pas ce que l’on appelle la suprématie quantique.

La suprématie quantique, c’est la mise en évidence d’une tâche précise qu’une machine quantique réalise mieux qu’un ordinateur classique. En octobre 2019, une équipe de chercheurs réunis autour de Google et de l’université de Californie à Santa Barbara ont publié dans la revue Nature un article qui a revendiqué la suprématie quantique. Le problème choisi ne relève pas de la cryptographie et il est un peu ad hoc, c’est l’échantillonnage d’un générateur d’aléas quantiques. Ceci a été fait avec une machine manipulant 53 qubits : un ordinateur nommé Sycamore. Il était prévu pour 54 qubits, mais le dernier ne marchait pas. Concernant la cryptologie, on voit qu’on est encore bien loin du compte. Il faudrait 4 000 qubits, voire plus, pour commencer à attaquer RSA pour les dimensions aujourd’hui recommandées. Et il faudrait évidemment que ces qubits soient robustes face aux erreurs physiques. D’ailleurs, dans la première page de leur article revendiquant la suprématie quantique, les auteurs écrivent que, pour tenir toutes ses promesses (notamment celles sur la factorisation), la machine quantique nécessite encore des sauts technologiques pour concevoir des qubits logiques tolérants aux erreurs. Il nous reste donc du temps.

Malgré tout, il faut prendre les recherches des physiciens très au sérieux. Dans mon parcours, j’ai pu constater la vitesse avec laquelle les réalisations technologiques concrètes évoluaient. J’étais très satisfait de mon premier modem analogique qui me permettait, il y a quarante ans, de transférer en quelques minutes un mégaoctet de données. Aujourd’hui, on parle en gigaoctets, en téraoctets, voire, pour le trafic Internet global, en exaoctets. La communauté de recherche en cryptographie prend donc les choses très au sérieux. Que se passerait-il en effet si, dans dix ou vingt ans, des machines quantiques pouvant factoriser de plus en plus efficacement existaient ? Il faut être prêt à faire évoluer la technologie des infrastructures de cryptologie, celle des cartes de crédit, celle des smartphones et celle de l’Internet. Pour cela un effort de recherche est indispensable. Heureusement, il a déjà commencé.

Si les clés publiques de première génération (RSA, courbes elliptiques) sont vulnérables à l’ordinateur quantique, il y en a maintenant d’autres qui, en l’état actuel de la science, ne le sont pas, notamment celles de deuxième génération appelée maintenant postquantique, en particulier la cryptologie sur les réseaux euclidiens. Pour être prête, la communauté va mettre en œuvre un processus qui a bien marché par le passé pour l’AES et les fonctions de hachage. Une compétition ouverte est en cours. Au début de l’année 2021, on en est à la finale, avec 7 qualifiés (et 8 en liste complémentaire) sur plus de 80 algorithmes candidats. Ils sont sous les critiques des cryptanalystes, qui recherchent leurs failles éventuelles et qui évaluent leurs avantages, leurs inconvénients et leur efficacité en termes de ressources de calcul et de ressources mémoire. Une fois la compétition terminée, les vainqueurs définiront des normes, et il ne fait pas de doute pour moi que la communauté de recherche en cryptologie saura répondre aux défis de la menace quantique, pour autant qu’elle se concrétise. Cette communauté permettra de préserver la pérennité des infrastructures de sécurité du monde numérique.

Une remarque en conclusion : ainsi que vous l’avez peut-être noté, en dehors des grandes figures du passé et des fondateurs, je n’ai pas cité beaucoup de noms. Je crois en effet que, dans un domaine où les enjeux scientifiques, technologiques et sociétaux sont totalement imbriqués, la force d’une communauté de recherche se mesure surtout au nombre, à la réactivité et à la capacité d’innovation globale de ses membres. En ce sens, je me sens fier et heureux d’être membre de la communauté cryptologique et d’avoir contribué à son avancement.

L’auteur

Père de l’école française de cryptologie, Jacques Stern compte parmi les meilleurs spécialistes mondiaux de cette « science du secret ». Il est aussi le fondateur du département d’informatique de l’École normale supérieure qu’il a dirigé jusqu’en 2007.

Mathématicien d’origine, passé ensuite à la cryptologie, Jacques Stern a à son actif une douzaine de brevets. Il a produit de nombreux algorithmes de chiffrement destinés à sécuriser les échanges sur Internet, dont celui baptisé GPS utilisé pour l’authentification et la signature en ligne. Redoutable briseur de code et maître de la « sécurité prouvée », il a notamment réussi à casser un algorithme réputé inviolable d’IBM qui se voulait être une alternative au code RSA. Il est l’auteur de près de 200 publications.

Président de l’Agence nationale de la recherche de 2007 à 2010, il a été, de 2012 à 2018, membre du collège de l’Autorité de régulation des communications électroniques et des postes (Arcep). Il fait partie des quelques « Fellows » de la prestigieuse (et très fermée) Association internationale pour la recherche en cryptologie. Il est membre de l’Académie des technologies.

Du même auteur

La Science du secret, Paris, Odile Jacob, 1998.

Fondements mathématiques de l’informatique, Paris, Dunod, 2000.

Les Grandes Voix de la Recherche

Dans la même collection

Thibault Damour, Ondes gravitationnelles et trous noirs

Gérard Berry, La pensée informatique

Nicole Le Douarin, Les secrets de la vie

Jean Jouzel, Climats passés, climats futurs

Philippe Descola, Une écologie des relations

Alain Connes, La géométrie et le quantique

Alain Aspect, Einstein et les révolutions quantiques

Maurice Godelier, Fondamentaux de la vie sociale

Jean Weissenbach, Dépolluer la planète

Claude Hagège, Le linguiste et les langues

Retrouvez tous les ouvrages de CNRS Éditions sur notre site www.cnrseditions.fr