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.

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.

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