Les desiderata de Kerckhoffs

Au-delà des premiers rapprochements avec les mathématiques, c’est la naissance du télégraphe qui transforme radicalement la portée du secret.

Après une démonstration d’une transmission Paris-Lille en moins de six heures, la Convention adopte dès 1793 le télégraphe optique des frères Chappe. Cette ligne sera suivie par d’autres, pour former un large réseau couvrant toute la France métropolitaine, puis l’Algérie et la Tunisie. En 1844, le territoire français comporte 534 tours pour plus de 5000 km de liaisons. Il est réservé aux communications gouvernementales jusqu’en 1851, date où il est mis à la disposition du public.

Le télégraphe électrique se développe à partir de 1832 en Angleterre avec son invention par plusieurs acteurs, dont Pavel Shilling (1786-1837). En 1838, Charles Wheastone (1802-1875) installe la première ligne en Angleterre entre Londres et Birmingham. La France voit l’installation de sa première ligne en 1845 entre Paris et Rouen, initiant le déclin du télégraphe Chappe. Ce nouveau vecteur change considérablement la nature des échanges.

Là où Babbage travaille sur des échanges individuels de messages [2], Auguste Kerckhoffs (1835-1901) s’intéresse aux conséquences des échanges par télégraphe sur la cryptographie militaire. Enseignant de langues modernes à Paris, en particulier de l’allemand, il envisage d’emblée la façon de sécuriser l’ensemble des messages qui transitent sur un réseau ouvert à toutes les interceptions possibles, en l’identifiant comme « système cryptographique ». Il énonce les « desiderata de la cryptographie militaire », aujourd’hui reformulées mathématiquement et enseignées sous le nom de « lois de Kerckhoffs », en particulier (Kerckhoffs, 1883) :

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 ;
(...)
Il faut qu’il soit applicable à la correspondance télégraphique.

Il conclut :

Je tiens, [….] à insister sur ce point, que la valeur d’un système de cryptographie destiné aux besoins de la guerre est en raison inverse du secret qu’exige son maniement ou sa composition. Il dépendra donc de l’Administration d’assurer l’avenir de la cryptographie militaire, en n’accordant ses suffrages qu’à l’invention qui s’appuiera sur le principe [….selon lequel] un chiffre n’est bon qu’autant qu’il reste indéchiffrable pour le maître lui-même qui l’a inventé : Ars ipsi secreta magistro [3] (Kerckhoffs, 1883, p. 12).

Adapter le secret des communications à l’usage collectif du télégraphe implique une organisation nouvelle des pratiques cryptographiques. Laisser passer les messages entre toutes les mains bouscule la conception du secret attachée à la hiérarchie militaire. Le procédé, devenu public, doit être enseigné à tous dans les écoles militaires. Désormais, le secret ne peut porter que sur la clé.

Système cryptographique et mathématiques

La notion de « système cryptographique » devient très vite centrale. En 1888, l’officier de marine Gaétan de Viaris (1847 – 1901), marquis polytechnicien d’origine italienne, publie quatre articles sur la cryptographie dans la rubrique « Variétés » du journal d’ingénieurs Le Génie Civil. Reprenant les desiderata de Kerckhoffs, il s’attache à la compatibilité entre les procédés cryptographiques et l’efficacité de leur transmission télégraphique. Il généralise l’approche algébrique de Babbage en écrivant les quatre formes possibles d’équations cryptographiques liées au chiffrement de type Vigenère : 

c, χ, γ, qui désignaient respectivement les lettres du texte clair, du cryptogramme, de la clef, désigneront également les valeurs numériques de ces lettres.
De l’équation cryptographique – [….] nous pouvons écrire les 4 équations :

(1) c + γ = χ

(2) 26 + c – γ = χ

(3) γ – c = χ

(4) 26 – (c + γ) = χ

…. , on reconnaîtra que l’équation (1) c + γ = χ représente le système Vigenère, et l’équation (3) c + χ = γ le système Beaufort. Les équations (2) et (4) ne diffèrent de (1) et (3) que par la substitution aux lettres γ de la clef, de leur valeur complémentaire 26 – γ.
(…) L’intérêt de ces tableaux est purement théorique, nous avons seulement voulu montrer que l’équation c + γ + χ = λ est en quelque sorte la synthèse des équations primitives d’une application aussi simple, elle est plus générale, plus élastique. Elle introduit dans l’équation c, γ, χ un nouvel élément λ qui par le fait est une nouvelle inconnue. Étant donnés deux éléments fixes : un texte de dépêche, texte obligatoire, une clef convenue d’avance, non modifiable, nous pouvons obtenir autant de textes chiffrés que λ peut prendre de valeurs différentes. De plus, si on envisage la construction d’un appareil cryptographique réversible, chiffrant et déchiffrant, on pourra choisir pour principe de l’appareil cette équation, à cause de sa parfaite symétrie (Viaris, 1888, p. 38).

La machine à chiffrer dont il donne alors le plan, dotée d’un système d’impression sur un ruban de papier, s’inscrit dans la recherche de procédés mécaniques de chiffrement associée au développement industriel.

Plan de la machine à chiffrer de De Viaris.
Le Génie civil, du 1^er septembre 1888, Tome XIII, N° 18, p.279.

Ces tentatives de mécanisation et de mathématisation des procédés cryptographiques se produisent par à-coups. En 1929, Lester S. Hill (1890-1961), alors professeur assistant au Hunter College de New York, publie la première utilisation systématique de l’algèbre en cryptographie dans une revue de mathématiques. L’article s’ouvre sur une référence explicite aux congruences de Gauss :

Soit a₀, a₁, ... , a₂₅ n’importe quelle permutation des lettres de l’alphabet anglais ; associons la lettre a_i à l’entier i. Nous définissons les opérations d’addition et de multiplication modulaire (modulo 26) sur cet alphabet comme suit : a_i + a_j = a_r, a_i a_j = a_t, où r est le reste obtenu en divisant l’entier i + j par l’entier 26 et t est le reste obtenu en divisant ij par 26 (Hill, 1929, p. 306).

Le système de chiffrement qu’il propose appartient à la famille des chiffrements polygrammiques : il chiffre simultanément plusieurs lettres du message clair par un calcul matriciel et produit autant de lettres dans le cryptogramme. Dans son article, Hill présente des exemples en dimension 3 et 4.

Voici un exemple illustratif en dimension 2 (Hill, 1929, p. 307) :

Un codage de lettres :

Les lettres sont groupées par paires qui sont considérées comme composantes des vecteurs de dimensions 2. Une matrice de chiffrement transforme alors ces vecteurs en d’autres vecteurs qui sont ensuite retranscrits en lettres. Les opérations sont réalisées modulo 26.
Ainsi, pour le message en clair Mississippi et la matrice de chiffrement : $\left(\matrix{2&3\cr23&17}\right)$,
les deux premières lettres M I sont codées par le vecteur (2,21), que la matrice de chiffrement transforme en (67,403), soit (15,13) après réduction modulo 26, ce qui donne les lettres g t.

La même méthode appliquée aux bigrammes successifs du clair conduit au cryptogramme gtiuthbcxpdq.

Pour que ce système fonctionne, il faut bien sûr que la matrice de chiffrement soit inversible. Ici, son déterminant vaut $-35$ qui est bien premier avec 2 et 13, et donc inversible dans l’anneau des entiers modulo 26. La matrice inverse modulo 26 est donc égale à $\left(\matrix{1&9\cr 17&20}\right)$, qu’il suffit d’appliquer pour déchiffrer le cryptogramme.

Bien que son objet reste le texte télégraphique écrit dans l’alphabet latin, Lester Hill va jusqu’à proposer d’autres structures algébriques pour conduire ces calculs :

(…) si on emploie des corps finis, les possibilités du cryptologue se trouvent considérablement étendues ; (…) Mais le nombre d’éléments d’un corps fini est nécessairement, soit un nombre premier, soit une puissance d’un nombre premier. Si notre alphabet doit être converti en un corps fini, le mieux qui puisse être fait est d’omettre une lettre, disons le j pour obtenir le corps à 25 éléments, ou d’adjoindre un symbole additionnel pour obtenir le corps à 27 éléments (Hill, 1929, p. 307).

La mise en œuvre du système de Hill est très lourde pour les opérateurs, et l’absence de moyens mécaniques conduit à de fréquentes erreurs. Hill a pourtant breveté un appareil pouvant chiffrer des blocs de 6 lettres. Formé d’une série de roues dentées reliées par une chaîne, il a été utilisé secrètement par le gouvernement des États-Unis pour chiffrer les trigrammes des indicatifs radio (Kahn, 1996, p. 408).

Schéma en coupe latérale de la machine de Lester Hill

Schéma en coupe longitudinale de la machine de Lester Hill

Les travaux de Hill ont un impact considérable. Sa reformulation des systèmes de chiffrement antérieurs en termes mathématiques explicite leur structure et permet d’en révéler les faiblesses, suggérant de nouvelles techniques de décryptement. Les mathématiciens y portent un grand intérêt, en particulier Adrian Albert (1905-1972), alors directeur de la division communication à l’IDA (Institute for Defense Analysis). C’est lui qui nomme « chiffrement de Hill » son système polygrammique. Il montre que les systèmes cryptographiques compliqués sont souvent des compositions de systèmes simples. Pour lui, les travaux de Hill, dont il célèbre l’élégance et la puissance, font basculer la cryptologie du côté des mathématiques :

Nous verrons que la cryptologie est bien plus qu’une matière qui admet une formulation mathématique, et il ne sera pas exagéré d’affirmer que la cryptologie abstraite est identique aux mathématiques abstraites [4].

Du côté des ingénieurs

Lorsque Gilbert Vernam (1890-1960) produit le système qui porte son nom, il n’est ni linguiste, ni mathématicien, mais ingénieur en télécommunications chez AT&T (American Telephone & Telegraph) à Manhattan depuis 1915. Il travaille à la sécurité des téléscripteurs pour le secret des affaires (secrecy for sale).

Un téléscripteur automatise les opérations de transcription du télégraphe au moyen d’un clavier de machine à écrire et d’un dispositif d’impression. Le texte est mémorisé et transporté sur un ruban perforé. Les caractères sont codés à l’aide du code d’Émile Baudot (1845-1903), modifié par Donald Murray (1866-1945) en 1901. Ces téléscripteurs sont largement utilisés jusqu’en 1980 par les organismes de presse.

Alphabet sur un ruban perforé selon le code Baudot

Chaque caractère de l’alphabet y est codé par cinq unités binaires, le passage du courant électrique ou son absence inscrivant ou non un trou sur le ruban, ce que Vernam symbolise par un + ou un –. Un codage spécial symbolise le passage du mode chiffre au mode lettre. Ainsi le code Baudot [5] peut représenter jusqu’à 60 caractères.

\[ \texttt{A + + – – – B + – – + + C – + + + – D + – – + –}\\ \texttt{E + – – – – F + – + + – G – + – + + H – – + – +}\\ \texttt{I – + + – – J + + – + – K + + + + – L – + – – +}\\ \texttt{M – – + + + N – – + + – O – – – + + P – + + – +}\\ \texttt{Q + + + – + R – + – + – S + – + – – T – – – – +}\\ \texttt{U + + + – – V – + + + + W + + – – + X + – + + +}\\ \texttt{Y + – + – + Z + – – – + 3 – – – + – 4 – + – – –}\\ \texttt{8 + + + + + (+)+ + – + + 9 – – + – – / – – – – –}\\ \]

La transmission des rubans perforés en clair pose de nouveaux problèmes de sécurité.

L’invention de Vernam, brevetée en 1917, joue un rôle important dans le développement du téléscripteur lui-même :

Cette invention se réfère aux systèmes de transmission par signaux, en particulier télégraphiques. Son objet est d’assurer la sécurité des transmissions de messages, et par suite, de fournir un système où les messages peuvent être transmis et reçus en clair, ou codée de manière connue, mais où les impulsions du signal sont si altérées avant leur transmission sur la ligne qu’elles sont inintelligibles à quiconque les intercepte (Vernam, 1919, p. 1, l. 8-17).

Un second ruban perforé de même longueur que le message initial, et dont les marques sont produites au hasard, sert de clé. Il est de même longueur que celui du message, et ses marques sont produites au hasard : ce n’est donc plus un mot de la langue, mais pas encore un objet mathématique. La machine combine électromécaniquement, sans aucune intervention humaine, chaque marque du ruban du message avec la marque correspondante du ruban de la clé.

Ce qui est revendiqué est (…) [la] méthode de chiffrement du signal qui consiste en la combinaison de l’effet de la condition électrique qui représente le caractère du message avec l’effet de celle qui représente le caractère chiffré, pour produire une impulsion électrique qui représente un autre caractère, et le changement du caractère chiffrant de temps en temps (Vernam, 1919, p. 5, l. 6-12).

Vernam est un ingénieur, aux prises avec une question mécanique : l’automatisation du chiffrement. Contrairement aux présentations anachroniques qui traduisent son procédé en termes d’addition binaire, de connecteur logique « ou exclusif » ou d’algorithme de calcul, son brevet le décrit en termes strictement techniques :

(…) Si les deux bobinages du relai sont connectés à la batterie (…) le relai restera inactif, car les effets magnétiques des deux bobinages se neutraliseront l’un l’autre (Vernam, 1919, p. 4, l. 28-33).

Encore ne le décrit-il que sur un exemple :

(…) Supposons que le premier caractère du message soit un A. Le A est codé par les signaux « ++––– » ou « – » représente une impulsion ouverte ou espace, et « + » représente une impulsion fermée ou marque..... Le code de la lettre B est « +––++ ». L’envoi du A …. signifie que les contacts 25 et 26 seront fermés, alors que les contacts 27, 28 et 29 seront ouverts..... La présence de la lettre B dans le code transmis signifie que les contacts 36, 39 et 40 ….. seront en contact avec la ligne 32 qui est connectée à la batterie, et les contacts 37 et 38 … seront en contact avec la ligne 33 qui est mise à la masse (Vernam, 1919, p. 3, l. 4-39).

Avec ce mécanisme, l’opération de chiffrement est identique à l’opération de déchiffrement : avec un ruban de clé identique, combiner la clé au cryptogramme redonne le clair. Les deux opérations étant effectuées par la machine, l’intervention humaine est éliminée du circuit de communication, et les risques d’erreurs diminuées d’autant.

Ce système de chiffrement est adopté par AT&T dès 1917, et dans l’US Navy par le biais de la Western Electric Company, entreprise fabricante d’AT&T. En 1918, le Major Joseph O. Mauborgne (1881-1971), du Signal Armed Corp, établit que la seule clé sûre est une clé endless and senseless, c’est-à-dire aléatoire, comparable en longueur au message lui-même (Kahn, 1996, p. 398). Il faudra attendre la théorie de l’information de Shannon pour établir la preuve de cette assertion [6]. Mais l’énormité du nombre de rubans de clés à transmettre fait obstacle à un usage universel de ce système très sûr et très performant. Il est rapidement réservé aux communications nécessitant un haut degré de confidentialité, par exemple pour les communications entre le président Roosevelt et le premier ministre britannique Churchill pendant la Seconde Guerre mondiale, et pour le téléphone rouge pendant la guerre froide.

Secret Signaling System. Inventor G.S. Vernam.
Brevet 1.210.719 du 22 juillet 1919. United States Patent Office.

Mathématisation du système cryptographique

La convergence entre la mécanisation et la mathématisation de la cryptologie a lieu au cours de la Seconde Guerre mondiale, essentiellement avec les travaux de l’ingénieur et mathématicien Claude Elwood Shannon (1916 – 2001), plus connu pour l’impact considérable de sa théorie de l’information sur les technologies numériques d’aujourd’hui. Ses travaux dans chacun des deux domaines sont profondément marqués par sa double formation, et par le contexte de la Seconde Guerre mondiale.
Shannon entre au MIT (Massachussetts Institute of Technology) à Boston dès 1936 comme assistant dans l’équipe de Vannevar Bush (1890-1974). Cette équipe a conçu et construit en 1927 un analyseur différentiel. Shannon doit assurer la maintenance de cette imposante machine qui permet d’obtenir graphiquement les solutions numériques approchées des équations différentielles de la physique contemporaine. Il travaille à en optimiser le fonctionnement en simplifiant l’organisation logique de ses circuits, qui connectent des intégrateurs analogiques à des mécanismes d’opérations, avec de nombreuses boucles de rétroaction. Dans son mémoire de master, « A symbolic Analysis of Relay and Switching Circuits » (1937), Shannon établit une « parfaite analogie » entre les relations des circuits à relais et commutateurs et le calcul propositionnel de la logique de Boole qu’il a étudiée à l’Université du Michigan. Ce mémoire offre pour la première fois un langage commun aux mathématiciens et ingénieurs travaillant sur ce type de machine, le langage des opérations binaires en 0 et 1. Il est immédiatement exploité par les Bell Telephone Laboratories, où Shannon travaille de 1941 à 1956. Il approfondit ses recherches en mathématiques, à la fois dans sa thèse sur la génétique théorique, et dans « Mathematical Theory of the Differential Analyzer » (1941), qui joue un rôle essentiel dans la maîtrise des grands calculateurs analogiques.

Shannon, « A symbolic Analysis of Relay and Switching Circuits ».

Dès 1940, Shannon entre à l’OSRD (Office of Scientific Research and Development), dirigé par Bush et qui coordonne les recherches entre l’université, l’industrie et l’armée. Il travaille à l’élaboration d’une arme automatique anti-aérienne [7], le M-9, et d’un système de traitement numérique de la parole en cryptologie, le projet X. Il a ainsi l’occasion de comparer signal analogique et signe numérique de chiffrement. Ces recherches parallèles le conduisent à identifier, à partir d’analogies opératoires issues de la théorie des probabilités, l’incertitude issue du bruit dans la transmission d’un signal, et l’incertitude liée à l’ignorance par l’adversaire de la clé de chiffrement. Dans ses deux publications fondamentales, « Communication Theory of Secrecy Systems Circuits » (1949), rédigée en 1946, et « Mathematical Theory of Communication » (1948), Shannon traite selon le même schéma mathématique système crypté et canal de communication bruité, distinguant la source, le transmetteur, le canal, le récepteur et le destinataire.

C. E. Shannon, « A Mathematical Theory of Communication », p. 380.

C. E. Shannon, « Communication Theory of Secret Systems », Déclassifié et publié en 1949.

Les prédécesseurs de Shannon, comme R.V.L. Hartley (1888-1970), Harry Nyquist (1889-1970) ou Alan Turing (1912-1954), avaient déjà introduit les logarithmes pour appréhender le caractère additif de la notion d’information [8]. Shannon s’appuie en outre sur une démarche expérimentale pour construire une définition probabiliste de la « quantité d’information » — the amount of information :

Supposons que nous ayons un ensemble d’événements possibles dont les probabilités d’occurrence sont p₁, p₂, …. , p_n. Ces probabilités sont connues, mais c’est tout ce que nous connaissons sur l’événement qui va survenir. Peut-on trouver une mesure du nombre de « choix » concernés par la sélection de l’événement, ou de l’incertitude que nous avons sur son issue ?
S’il existe une telle mesure, disons H(p₁, p₂, …. , p_n) il est raisonnable d’exiger les propriétés suivantes :

1. H doit être continue en les p_i.

2. Si tous les p_i sont égaux, p_i = 1 / n, alors H doit
être une fonction croissante de n.

Si un choix est décomposé en deux choix successifs, le H original doit être la somme pondérée des valeurs individuelles de H.

(…).

Théorème 2 : Le seul H qui satisfait les trois hypothèses ci-dessus est de la forme $H=\sum_{i=1}^n p_j\log_2(p_i)$,

où K est une constante positive (Shannon, 1948, p. 390).

Shannon pose alors k = 1 pour identifier cette définition à l’entropie d’un système [9], antérieurement définie en mécanique statistique. Cette définition mathématique mesure les choix que représente un message parmi tous les messages possibles, les p_i représentant les probabilités d’occurrence de chacun d’entre eux. Elle est donc maximale lorsque la situation est la plus incertaine, à savoir dans le cas de l’équiprobabilité. Elle concerne aussi bien le cryptanalyste cherchant à retrouver le message clair à partir du cryptogramme, que l’ingénieur face au bruit perturbant la qualité de la transmission et que Shannon considère pour la première fois comme une variable aléatoire.

Le niveau d’abstraction de ces deux articles est tout à fait remarquable. Shannon intègre les derniers développements mathématiques en théorie des ensembles, théorie des fonctions, théorie de la mesure et théorie des probabilités. Il se soumet surtout à l’injonction de ses autorités de tutelle de ne rien révéler qui puisse renseigner sur les applications possibles de son travail.

Un système secret est défini abstraitement comme un ensemble d’opérations ou de transformations T_i d’un espace – l’ensemble des messages possibles – dans un autre – l’ensemble des cryptogrammes possibles. Le cryptogramme E est l’image d’un message M par une telle transformation T caractérisée par la clé i – devenue clairement aléatoire – de telle sorte que :

Shannon prend soin de préciser que ces transformations doivent avoir un inverse unique, afin que le message clair puisse être retrouvé à partir du cryptogramme par cette transformation inverse :

Il définit alors deux opérations de combinaison, qui lui permettent de définir l’ensemble des systèmes de chiffrement comme une algèbre associative linéaire, et d’analyser la composition de systèmes simples en systèmes complexes. Les différents modes de chiffrement connus, de César à Vernam, sont alors réinterprétés dans cette formulation.

À chaque clé et à chaque message sont associées des probabilités a priori qui, provenant du caractère stochastique du langage naturel, sont connues du cryptologue. Si par exemple, les messages possibles sont les suites de lettres de longueur N dans une langue, les probabilités a priori ne sont autres que les fréquences des lettres de cette langue. « L’ennemi » ayant intercepté le cryptogramme peut alors calculer les probabilités a posteriori des caractères du message en clair connaissant ce cryptogramme et des clés susceptibles de l’avoir produit. Toute l’étude de Shannon porte sur les relations entre ces probabilités a priori et a posteriori, et le problème général de la cryptanalyse n’est autre, que le calcul de ces probabilités a posteriori. Cette analyse débouche sur une classification théorique des systèmes secrets, fondée sur leurs propriétés mathématiques structurelles et probabilistes. Shannon distingue notamment les systèmes purs, où toutes les clés conduisent au même ensemble de probabilités a posteriori, et les systèmes parfaits, où les probabilités a posteriori sont égales aux probabilités a priori et pour lesquels intercepter un message ne donne donc aucune information au cryptanalyste (Shannon, 1948).

La conception stochastique du langage qui fonde l’approche de Shannon dans ces deux articles débouche également sur de nouveaux concepts. Elle sous-tend notamment les concepts de confusion et de diffusion qui permettent d’évaluer la qualité des fonctions de chiffrement [10]. Chaque message apparaît comme une suite de lettres dont chacune est choisie dans un alphabet avec une probabilité donnée. Dans le cas le plus fréquent, celui du langage naturel, chacune de ces probabilités dépend des choix précédents, ce qui permet de caractériser l’ensemble des suites de lettres comme un processus de Markov discret, qu’il suppose ergodique, c’est-à-dire statistiquement homogène.

Chez Shannon, la mesure de la quantité d’information transmise lors d’une communication est donc en relation directe avec la distribution de probabilité des symboles dans ce processus. Cela le conduit au concept de redondance, qui lui permet de théoriser le travail du cryptanalyste et de s’attaquer au bruit dans les systèmes de communications :

Comme dans la théorie des communications, le langage est considéré comme étant représenté par un processus stochastique qui produit une suite discrète de symboles, selon un certain système de probabilités. Associé à un langage, figure un certain paramètre D, que nous appelons la redondance du langage. Le paramètre D mesure en quelque sorte combien la longueur d’un texte du langage peut être réduite sans perdre d’information. Par exemple, dans les mots anglais, la lettre u suit toujours la lettre q, le u peut être supprimé sans aucune perte. Des réductions considérables sont possibles en Anglais, en raison de la structure statistique de la langue, de la fréquence élevée de certaines lettres et de certains mots, etc. La redondance est d’une importance centrale dans l’étude des systèmes de confidentialité (Shannon, 1948, p. 656-657).

La redondance mesure le fait que le nombre de symboles transmis est supérieur à ce qui est strictement nécessaire à la compréhension du message. Elle permet de corriger les erreurs de transmission, et par exemple de remplacer le mot « endépendance » par « indépendance » à la réception ou au décryptement d’un message. Dans la langue naturelle, la syntaxe est une source de redondance [11]. C’est la redondance qui permet au cryptanalyste d’achever son travail à partir d’informations suffisantes pour deviner le reste des mots. Un texte peu redondant nécessite un cryptogramme plus long. Les codes correcteurs d’erreurs ajoutent de la redondance aux symboles transmis pour corriger automatiquement des erreurs. Dans la majorité des cas, c’est uniquement la redondance qui assure l’unicité de la solution. Shannon établit la quantité requise de cryptogramme pour assurer cette unicité, qu’il appelle la distance d’unicité.

La mesure de la quantité d’information semble induire l’abandon de toute référence à la signification des messages échangés. Le mode de rédaction de Shannon témoigne pourtant de l’attention constante qu’il porte à la signification des probabilités qu’il introduit. Les énoncés mathématiques de ses théorèmes sont systématiquement repris dans le langage de l’ingénieur. Et il doute de la pertinence du terme « ennemi », d’origine militaire. De fait, la question du sens est loin d’avoir disparu du travail de Shannon, mais elle est posée du point de vue de l’ingénieur :

Le problème fondamental de la communication est celui de la reproduction, en un point, soit exactement soit approximativement, d’un message choisi en un autre point. Souvent, les messages ont une signification, en ce qu’ils se réfèrent ou sont corrélés selon un système qui comprend certaines entités physiques ou conceptuelles. Ces aspects sémantiques de la communication ne sont pas pertinents pour le problème d’ingénierie. L’important est que le message réel est choisi dans un ensemble de messages possibles. Le système doit être conçu pour fonctionner pour chaque choix possible, pas seulement celui qui sera effectivement fait car il n’est pas connu au moment de la conception (Shannon, 1948, p. 379).

De fait, la formule qui définit la quantité d’information traduit bien le changement de point de vue qu’engage la conceptualisation mathématique de la notion de système. Elle ne concerne plus le contenu des messages individuels à l’intérieur du système, mais l’ensemble de tous les messages et de toutes les clés possibles, cherchant à expliciter les conditions qui vont lui permettre de maîtriser le système de communications dans son ensemble, vu de l’extérieur. Shannon qualifie de « vrais systèmes secrets » les systèmes cryptographiques définis par Kerckhoffs, ceux qui, par opposition aux « systèmes privés », sont destinés à être utilisés collectivement et publiquement (Shannon, 1948, p. 656). Il pose clairement, d’un point de vue technique, la question du lieu de l’énonciation, une question qui sera reprise d’un point de vue philosophique dans les débats sur la cybernétique.

Mécanisation de la cryptanalyse

Au même moment, en Grande-Bretagne, le mathématicien Alan Turing (1912-54) participe activement au décryptement des messages allemands, où il développe une approche logico-mécanique de la cryptanalyse. Il a déjà théorisé la mécanisation des procédures en 1936, lorsqu’il a élaboré le concept de ce qui s’appelle aujourd’hui la « machine de Turing » [12].

À son retour de Princeton en 1939, il est entré, avec d’autres mathématiciens, au service de la GC&CS (Governement Codes and Cyphers School) alors installée secrètement à Bletchley Park, au nord de Londres. Ce centre assure la capture, la collecte et l’analyse du matériel et des messages en provenance des prises de guerre et des stations radio [13]. Les communications tactiques allemandes sont alors chiffrées sur différents modèles de la machine Enigma [14], dont le degré de sophistication ne cesse d’augmenter depuis leur adoption par l’armée allemande [15] en 1926.

Machine Enigma à 3 rotors avec tableau de connexions sur la face avant.

Inventée dans les années 1920, la machine Enigma est une machine électro-mécanique qui donne un nombre colossal de chiffrements possibles. Elle dispose d’une série de 3 à 5 cylindres rotatifs, appelés rotors, bordés de 26 contacts reliés d’une face à l’autre par un câblage interne propre à chaque rotor. Le 1er rotor tourne d’un cran à chaque lettre frappée sur le clavier, le 2^ème d’un cran après chaque rotation complète du 1^er, et le 3^ème d’un cran après chaque rotation complète du 2^ème. Cet assemblage de rotors produit une substitution alphabétique.

Un réflecteur, avec des contacts sur une seule face et son propre câblage interne, compose ces substitutions avec leurs réciproques, rendant le déchiffrement identique au chiffrement. Le choix, la disposition et la position initiale des rotors constituent la clé. À l’avant de l’appareil, un tableau de connexions permute jusqu’à dix paires de lettres. Chaque frappe d’une lettre au clavier allume une ampoule qui indique la lettre chiffrée. Le nombre de substitutions est ainsi devenu considérable, atteignant un nombre voisin de 1,5 x 10²⁰ pour un tableau de connexions de dix fiches et trois rotors en ordre quelconque [16].

Schéma du circuit de chiffrement d’une lettre à travers rotors, réflecteur et tableau de connexions.

En coordonnant le travail des services secrets, des mathématiciens et des ingénieurs au cours des années 1930, le Biuro Szyfrow polonais est déjà parvenu à décrypter les messages de l’Enigma. Les trois mathématiciens Maian Rejewski Henrik Zygalski et Jersy Rojecki ont inauguré l’utilisation de la théorie des permutations en cryptanalyse. L’application de cette théorie, combinée avec des maladresses opératoires dans la mise en œuvre de la machine leur permet, non seulement de reconstituer le câblage interne des rotors de la machine militaire, différente de la version commerciale, mais aussi de reconstituer les clés du jour quotidiennement en moins de deux heures.

Mais face à une nouvelle sophistication de la machine, et à l’invasion imminente de la Pologne, les équipements et les résultats sont communiqués aux services français et surtout britanniques. L’équipe de Turing hérite de cet « inestimable cadeau » dès juillet 1939, et réussit le décryptement de l’Enigma navale, fondamental pour la bataille de l’Atlantique.

Du fait de l’accroissement du nombre de possibilités, de nouvelles méthodes sont requises, associées à des informations complémentaires. Outre la capture de documents et de machines, W. Gordon Welchman (1906-1985) conduit un travail systématique d’analyse des données, qui permet de répertorier des mots, ou des énoncés probables, appelés « cribs ». Partant d’un « crib » supposé, et du principe d’exclusivité, selon lequel une lettre ne peut être chiffrée par elle-même, Turing et Welchman scrutent les incohérences logiques dans l’enchaînement des lettres effectives et supposées entre le clair et le cryptogramme. Ils implantent cette recherche sur de nouvelles machines appelées Bombes de Turing (Turing, « Bombe and Sipher (1940) ») [17].

La première, Agnus Dei ou Aggie, qualifiée de « déesse de bronze » est prête en août 1940, et 200 fonctionneront à la fin de la guerre. À partir de mi-1941, elles permettent de décrypter au jour le jour les messages de la marine allemande dont le nombre s’accroît jusqu’à 2800 par jour en 1943.

Le « zéro » et le « un »

Conjuguée à l’algébrisation de la logique et au travail de Shannon, la notion d’algorithme s’installe au cœur de la pratique des ordinateurs, d’abord sous forme câblée, puis sous forme de programme intégré. L’enjeu du secret change à nouveau de dimension. Si Horst Feistel (1915-90) écrit en 1973 que les ordinateurs, du fait de leur fonctionnement en réseau, « constituent, ou vont constituer, une menace pour la liberté individuelle », il ne s’agit pas de la liberté « des amoureux et des voleurs », mais de la sécurité des échanges internationaux et des libertés du commerce, qui ne sont plus alors l’affaire des seuls militaires et diplomates, mais une « affaire publique » (Feistel, 1973, p. 15).

Sous la pression d’une demande civile croissante de normalisation, émanant en particulier du monde bancaire, le NBS (National Bureau of Standards), agence du département du commerce aux États-Unis, promeut la publication d’algorithmes cryptographiques.
Feistel est un des premiers chercheurs non gouvernementaux à travailler sur la théorisation des modes de chiffrement. Il a fait des études de physique au MIT et travaille successivement à la mise au point du dispositif IFF (Identification Friends and Foes) pour l’AFCRS (Air Force Cambridge Research Center), puis à la conception du chiffrement au Thomas Watson Research Center de la firme IBM (International Business Machines). C’est dans ce contexte qu’il conçoit de nouvelles architectures, notamment celle du DES (Data Encryption Standard), premier algorithme public de chiffrement symétrique, homologué au terme d’une compétition remportée par IBM à la suite d’un appel d’offres lancé en 1977 pour produire un système cryptographique utilisable par les entreprises.

Le travail de Feistel mobilise pleinement le codage en écriture binaire et la notion d’algorithme. Son mode de chiffrement par blocs reprend l’idée de fractionner le message, et réalise une combinaison de chiffrements successifs, qui alternent substitutions et permutations. Les substitutions assurent la confusion des probabilités associées aux lettres initiales du message en bouleversent le nombre et la répartition des 0 et des 1. Quant aux permutations, elles engendrent la diffusion de ces probabilités en mélangeant les symboles.

Ces transformations sont effectuées électroniquement et se répètent sur plusieurs couches à travers lesquelles passe le message. Le système LUCIFER, un des premiers algorithmes de Feistel, travaille sur des blocs de 128 symboles binaires. Il utilise une clé de même longueur. À la sortie, les symboles sont devenus des fonctions très sophistiquées, et surtout non linéaires, de tous les symboles d’entrée.

Le message transmis est complété par plusieurs éléments : un mot de passe pour garantir son authenticité, un code correcteur pour juguler les éventuels brouillages de transmission, et un autre mot de passe pour restreindre l’échange des messages à un groupe prédéterminé de destinataires. Le chiffrement par blocs mélange judicieusement les chiffres du message initial à ces ajouts, de telle sorte qu’un adversaire ne puisse les distinguer. Ainsi le chiffrement de Feistel conjugue-t-il la force du système de chiffrement à une bonne résistance à la corruption – fortuite ou intentionnelle – des messages.

La publication du DES en 1977 marque un nouveau tournant : c’est le premier algorithme de chiffrement rendu public. Cette publicité n’est d’ailleurs pas sans risque : elle ne correspond à un choix raisonnable que si l’algorithme sur lequel repose le mode de chiffrement est sûr. Or, l’intervention de la NSA (National Security Agency) dans la conception ultime du DES a conduit ses utilisateurs à soupçonner l’existence de trappes ou « portes dérobées » (Back doors) qui lui auraient permis de décrypter les échanges. Le DES a cependant été le système de chiffrement à clé secrète le plus utilisé pendant une vingtaine d’années. Mais l’augmentation considérable de la puissance des ordinateurs a rendu possible, dès 1997, la recherche de la clé par calcul exhaustif. Pour y pallier, la NSA a standardisé un triple DES, puis le système AES en 2000, à la suite d’un appel d’offres cette fois international.

Vers la cryptographie à clé publique

Rendre public l’algorithme cryptographique ne résout pas tous les problèmes issus de la mise en réseau des ordinateurs. Les communications devenant électroniques, la multiplication des échanges produit un tel changement d’échelle que le transport et la distribution des clés entre protagonistes « d’un bout à l’autre de la planète » (Diffie & Helmann, 1972) devient un problème insurmontable. La signature de contrats et le règlement des transactions imposent non seulement d’assurer la confidentialité des messages, mais d’en garantir l’authenticité. En 1976, Whitfield Diffle [18] (né en 1944), diplômé du MIT, et Martin E. Hellman (né en 1945), professeur à l’université de Stanford, inaugurent la cryptographie à clé publique et annoncent « l’aube d’une révolution en cryptographie ».

Reprenant la conception de Shannon et de Feistel du système cryptographique comme famille de transformations inversibles, ils proposent des solutions nouvelles faisant intervenir deux clés, l’une publique et l’autre secrète :

Dans un cryptosystème à clé publique, le chiffrement et le déchiffrement sont gouvernés par deux clés distinctes, E et D, telles que le calcul de D à partir de E soit calculatoirement irréalisable (nécessitant par exemple 10¹⁰⁰ instructions). La clé de chiffrement E peut donc être publiquement divulguée sans compromettre la clé de déchiffrement D. … Si l’oreille indiscrète d’une tierce partie capte cet échange, il doit lui être calculatoirement irréalisable de calculer la clé à partir des informations captées (Diffie & Helmann, 1972).

Qualifier une tâche de « calculatoirement irréalisable » signifie que « son coût en temps de calcul et en espace mémoire est fini mais trop grand pour être envisagé ». Ce faisant, l’expression mathématique des conditions de sécurisation des échanges électroniques permet de distinguer le niveau de sécurité des crytposystèmes en fonction des types d’attaque auquel il résiste. Elle permet surtout de définir de nouveaux concepts, fondés sur la théorie des algorithmes et de la complexité : authentification du message et de l’utilisateur, signature numérique, portes dérobées.

Ces concepts s’appuient sur le chiffrement par une fonction à sens unique, pour laquelle il est calculatoirement impossible d’obtenir l’antécédent d’un élément [19]. Cette inversion est cependant accessible au détenteur d’une information supplémentaire, connue de lui seul, appelée porte dérobée, qui rend la fonction inverse accessible. Dans un système de chiffrement à clé publique, la clé secrète exploite cette porte dérobée, mais un concepteur mal intentionné peut détourner la méthode pour produire un chiffrement à porte dérobée, qui lui permette « de casser le système après l’avoir vendu à un client, et cependant, de maintenir sa réputation en tant que concepteur de systèmes sûrs ».

Il a néanmoins fallu deux années de nouvelles recherches pour réaliser les ambitions de Diffie et Hellman, c’est-à-dire qui pour trouver des fonctions à sens unique pertinentes. Le RSA, du nom de ses auteurs Ronald Rivest (né en 1947), Adi Shamir (né en 1952) et Leonard Adleman (né en 1945) s’appuie sur la difficulté de factoriser les grands entiers.

La cryptologie investit alors des problèmes mathématiques connus pour être difficiles à résoudre, relevant de l’algèbre et de la théorie des nombres. La rencontre de la cryptologie et des mathématiques est de plus en plus manifeste aujourd’hui. Elle franchit un nouveau pas avec l’utilisation de la géométrie algébrique : les courbes elliptiques et les appariements de points permettent la réalisation de nouvelles fonctions cryptographiques comme la cryptographie à clé publique choisie, permettant de choisir l’identité du destinataire comme clé de chiffrement.

École théorie cryptographique et preuves de sécurité

Juger de la valeur d’un nouveau système a toujours été une question centrale pour les cryptographes. Depuis que Diffie et Hellman l’ont reformulée en termes mathématiques, la sécurité des systèmes cryptographiques, dite sécurité prouvée, est censée être garantie par des théorèmes mathématiques. Le principe d’une telle preuve est de réduire la réussite d’une attaque cryptographique à un problème mathématique difficile. De fait, il s’agit d’une garantie conditionnelle, du type « ce protocole n’est à l’abri d’une attaque de type X que si le problème mathématique Y est calculatoirement difficile ». Tant que le problème mathématique n’a pas de solution accessible en pratique, l’attaque du système est donc garantie infructueuse.

Le problème majeur de ce type de preuve est que l’existence de problèmes intrinsèquement difficiles n’est pas avérée. Bien sûr, la multiplication des grands nombres premiers apparaît aujourd’hui comme une fonction à sens unique, car la multiplication a une complexité polynomiale, alors que les meilleurs algorithmes connus pour factoriser le produit ont une complexité strictement supérieure. Mais nul ne sait si demain un algorithme efficace ne pourra être trouvé. À ce jour, ni l’existence, ni l’inexistence d’un tel algorithme n’ont été démontrées.
Depuis l’apparition des clés publiques, une communauté de chercheurs en cryptographie s’appuie sur l’analyse mathématique des algorithmes pour établir la crytpographie sur des bases théoriques. Ils tentent d’établir l’activité cryptographique comme science pour assurer la confiance des utilisateurs.

Mais le caractère conditionnel des preuves de sécurité interroge la possibilité de réduire la cryptographie à ces fondements théoriques. Pour Neal Koblitz par exemple (La relation agitée entre Mathématiques et Cryptographie), ces preuves, qu’il préfère qualifier d’arguments, sont utilisées pour impressionner ceux qui sont étrangers au domaine et qui comprennent peu leur véritable signification, en particulier les utilisateurs. Entre cryptologues et mathématiciens, chaque groupe investit le statut de l’autre pour cautionner son propre développement, tant sur le plan symbolique que sur le plan financier.

Conclusion

La rencontre entre cryptologie et mathématiques passe par une réflexion sur les pratiques et suit l’évolution des mathématiques elles-mêmes. Elle se manifeste par une analyse de type classificatoire, sur les modes de chiffrement, sur leurs pratiques instrumentales, aussi bien que dans les tentatives de décryptement.

Depuis l’introduction du télégraphe, les nouveaux modes d’échanges d’informations ont été tout aussi déterminants pour faire basculer la cryptologie, de l’étude des messages chiffrés à celle des systèmes cryptographiques, et transformer l’assignation du secret. Si le recours à la théorie des nombres et aux structures algébriques inspire plusieurs ébauches de méthodes de chiffrement et de décryptement, la mathématisation de la cryptologie ne s’impose véritablement qu’à partir du moment où la mécanisation du chiffrement rend matériellement impossible tout décryptement manuel. Les échanges informatiques sont aujourd’hui impensables sans le recours à cette cryptologie mathématisée, qui cherche à en maximiser les garanties de confidentialité et d’authenticité. Les méthodes cryptographiques sont aujourd’hui publiques, et le secret réduit à la clé, voire à une partie de la clé, mais la difficulté mathématique de sa découverte en assure la sécurité.

Aux yeux de nombreux cryptologues praticiens, cette rencontre ne suffit pas à faire de la cryptologie une science. Son enseignement universitaire ne fait que traduire la transformation de ses conditions de production et d’exercice, et ses implications socio-politiques se situent bien au-delà de la seule démonstration d’un théorème. Initialement considérée comme un art, la cryptologie est sans aucun doute imprégnée d’une méthodologie scientifique, mais elle s’exerce en permanence face à un adversaire, dont les possibilités d’attaques ne se réduisent pas aux seules mathématiques, et dont la présence induit le recours permanent à des conjectures et hypothèses subjectives sur le mode de protocole à choisir selon le contexte d’utilisation. Pour être investi de confiance, un système cryptographique se doit de résister non seulement aux attaques du jour, mais à ce qu’elles pourraient être sans que les concepteurs en aient une idée précise.

La seule référence aux mathématiques conduit d’autant plus à masquer les aspects sociétaux de l’exercice de la cryptologie, que la représentation publique de ces deux domaines du savoir se trouve coupée de ses significations. La cryptographie vise à dissimuler le sens d’un message, et les méthodes calculatoires de la cryptanalyse la dispensent désormais d’y avoir recours. Et il est systématiquement affirmé que la validité des mathématiques ne repose que sur le seul agencement interne de leur édifice théorique. Les significations des mathématiques comme de la cryptologie sont pourtant multiples, dès lors que se trouve restituée la multiplicité de leurs interventions, qui légitime leur importance sociale.

N’est-il pas dès lors permis d’interroger le mode de communication qu’installe le recours aux communications cryptées, où l’information n’est plus censée circuler universellement, mais dans des canaux sélectionnés selon les groupes sociaux, avec une possible surveillance des autorités conceptrices ?

Bibliographie

↑^{a et b} Diffie W. et Helmann M, « Les nouvelles orientations de la cryptographie », IEEE Transactions on Information Theory, vol. 22, n° 6, p. 644-654, in (Durand-Richard & Guillot, 2014, p. 173-202).

↑ ^{a, b et c} Durand-Richard, M.-J. et Guillot, Ph. (éd.), Cryptologie et mathématiques, une mutation des enjeux, Paris, L’Harmattan, 2014.

↑ Feistel, H., « Cryptography and Computer Privacy », Scientific American, 1973, vol. 128, n° 5, p. 15-23.

↑^{a, b et c} Hill, L., « Cryptography in an Algebraic Alphabet », The American Mathematical Monthly, Vol 36, n° 6, Juin-Juillet 1929, p. 306-312.

↑^{a, b et c} Kahn D., The codebreakers, the Story of Secret Writing, New York, McMillan Publications, 1996.

↑^{a et b} Kerckhoffs, A., « La cryptographie militaire », Journal des sciences militaires, vol. IX, janv. 1883, p. 5-38 ; vol. X, fév. 1883, p. 161-191.

↑Koblitz N. « La relation agitée entre Mathématiques et Cryptographie », in (Durand-Richard & Guillot, 2014, p. 285-303).

↑^{a, b et c} Shannon, C. E., Sloane N. J. A (éd.) et Wyner A. D. (éd.), Collected Papers of C. E. Shannon, New York, IEEE Press, 1993.

↑ Shannon, C. E., « A Symbolical Analysis of Relay and Switching Circuits », Transactions of the American Institute of Electrical Engineers, 1938, n° 57, p. 713-723, in Collected Papers, p. 471-495.

↑^{a et b} Shannon, C. E., « Communication Theory of Secrecy Systems », The Bell System Technical Journal, 1946-49, vol. 28, p. 656-711 ; in Collected Papers, p. 656-711.

↑^{a, b et c} Shannon, C. E., « A Mathematical Theory of Communication », The Bell System Technical Journal, july-october 1948, vol. 27, p. 379-423 et 623-656 ; in Collected Papers, p. 5-82.

↑ Turing A., M., « Bombe and Sipher (1940) », in Turing A. M. et Copeland, B. J. (éd.), The Essential Turing, Smeinal Writings in Computing, Logic, Philosophy, Artifical Intelligence and Artifical Life, plus the Secrets of Enigma, Oxford, the Oxford University Press, 2004, pp. 313-335.

↑^{a, b, c et d} Vernam, G., Secret Signaling System, United States Patent Office, patented July 22, 1919.

↑ Viaris, G. de, « Cryptographie », Le Génie Civil, 1888, tome XXIII, p. 24-27, p. 38-39, p. 55-56, p. 72-75, p. 84-88, p. 104-107.