L’avion se posa sur l’aéroport du Péloponnèse dans un crissement de pneus qui trahissait la moiteur de l’air ambient. Mon contact s’appelait Nikos, et il était beau comme un grec, ce qui n’a rien de surprenant quand on pense que c’était un grec. D’ailleurs, juste après avoir dégusté quelques vodka-martinis au bar de l’hôtel, nous eûmes tous les deux une folle nuit d’amour où je découvris que la réputation des grecs n’est en rien usurpée... Sur l’oreiller Nikos m’avoua que la première expérience de cryptographie [3] est d’origine hellène, et consiste à enrouler un ruban vierge (analogue à celui d’une machine de Turing, un autre cryptographe célèbre) sur un bâton appelé scytale, avant d’écrire le message en clair. Ainsi, le ruban de papier prend naturellement une forme d’hélice et lorsqu’on déroule ce ruban, le message devient incompréhensible par permutation des lettres ... jusqu’à ce qu’on enroule le ruban sur une autre scytale !

Algébriquement, l’opération de codage consiste à transposer une matrice (après avoir écrit en matrice un message initialement en ligne). Et de même, le décodage consiste à transposer la matrice à nouveau.

Voici une scytale en ligne (à 7 crans) :

Cryptage par scytale

Codage

Décodage

Après avoir quitté Nikos sur une vodka-martini d’adieu, j’envoyai ce bref rapport au Capitaine Kuntz :

La scytale ne fait pas de « chiffrage » à proprement parler, puisqu’elle laisse les lettres telles quelles. Elle ne fait que les permuter. Cependant, le codage et le décodage sont basés sur une transposition de matrice, et le remplissage de cette matrice se fait avec l’arithmétique modulo 7 (par exemple). La scytale est donc une application de l’arithmétique et des matrices.

Ce à quoi le Capitaine me répondit :

C’est pas au programme. Enquête à prolonger.

En recherche d’un « vrai » chiffrage, je quittai alors la Grèce pour l’Italie, ma prochaine mission se situant quelque part entre le fleuve Rubicon et la ville éternelle.

Lorsque l’avion eût fini d’atterrir sur le sol de la ville éternelle, je repérai immédiatement mon contact grâce à sa beauté italienne : Elle s’appelait Carla mais me demanda très vite, avec force roulement des « r », de l’appeler Carlita. En effet j’eus très vite l’occasion de me rendre compte, dans le lit de l’hôtel, à quel point Carlita était très affectueuse... Après lui avoir offert une nuit d’amour inoubliable, je la questionnai tout en sirotant ma vodka-martini du petit-déjeuner, à propos d’un paramilitaire italien répondant au nom de Caius Julius (nom de code : Cesar). Un individu dangereux et armé (avec une grosse armée même) dont le fils adoptif s’appelait Brutus, tout un programme...

Or ce Cesar utilisait un chiffre consistant à réaliser une permutation circulaire, non sur les lettres elles-mêmes (comme dans l’onglet précédent) mais sur l’alphabet : Le célèbre chiffre de Cesar.

Voici donc un chiffreur-déchiffreur de Cesar en ligne, basé sur un décalage de 7 lettres :

Chiffrage Cesar

Codage

Décodage

Le chiffre de Cesar résiste peu au décryptage, l’algorithme d’al Kindi permettant assez facilement de le « casser ». Cela est dû à ce que quelle que soit la lettre qui code le « e », elle sera plus fréquente que les autres dans le message codé. Ce qui permet de trouver le code de Cesar utilisé par analyse fréquentielle.

Je rédigeai un rapport plus bref que le précédent (j’avais deux-trois choses à faire avec Carla en privé) sur le chiffre de Cesar :

Le chiffre de Cesar réalise une permutation circulaire sur les lettres de l’alphabet, ce qui modulo le nombre de lettres de l’alphabet, revient à additionner une constante au chiffre associé à cette lettre. C’est donc un vrai « chiffre ».

Ce à quoi le Capitaine Kuntz me répondit à nouveau :

Pas au programme. Enquête à prolonger

La mission suivante se déroulait en France avec un espion d’envergure internationale : Vigenère, dont Carla, qui était une de ses nombreuses ex, m’avait dit de me méfier.

Sitôt arrivé à l’hôtel dans Barbès, au milieu des odeurs de Ras-El-Hanout, je perçus une présence dans ma chambre : Un homme derrière la porte, deux dans la salle de bains, un sous le lit et un sur le balcon. Ce fut une occasion d’exercer sur eux mes techniques de close-combat qui se rouillaient un peu (avec Carlita j’avais pratiqué une autre forme de « close »...). Je leur fis le « coup de genou dans la courbe elliptique » que m’avait enseigné Maître Goro Shimura dans mes années de formation.

Mon contact, Blaise de Vigenère, avait pas mal de missions à son actif, en particulier celle à Rome (où il avait eu une liaison de deux heures avec Carlita) où il s’initia à la cryptographie, et suggéra une amélioration du chiffre de Cesar, consistant à changer de permutation à chaque lettre à coder. Pour s’y retrouver, il faut une « clé de chiffrage », en général un mot, égal à « Vigenere » ci-dessous.

Voici un crypteur-décrypteur utilisant le chiffre de Vigenère avec comme mot-clé « Vigenere » :

Chiffrage Vigenere

Codage

Décodage

Le chiffre de Vigenère a connu un franc succès, une de ses variantes, Enigma (machine) servant de moyen de communication dans la Kriegsmarine de la seconde guerre mondiale. Le mathématicien Alan Turing ayant eu pour rôle essentiel pendant la guerre, de décrypter Enigma. Ce que son équipe parvint à faire, écourtant ainsi la guerre, et épargnant à la Londres voisine des bombardements supplémentaires.

Mais le chiffre de Vigenère n’est pas la seule façon d’améliorer le chiffre de Cesar (en combinant plusieurs chiffres de Cesar). Il y a aussi le choix d’une permutation plus complexe que la simple « rotation de lettres » de Cesar. Devenue soudainement bavarde après quelques vodka-martini, Carla se mit à évoquer une autre piste française, avec l’agent Bézout.

Pendant que Carla cuisinait son contact pour lui tirer les Vigenère du nez, je dégustais tranquillement ma vodka-martini au bar lorsque je vis arriver Phine (mon agent double préféré). Joséphine avait un fort beau harnais que je reconnus immédiatement dans le miroir situé derrière la barmaid, et commanda sa fine habituelle pour essayer de me cuisiner moi. Mais j’avais déjà bu trop de vodka-martini pour être en état de lui révéler quoique ce soit. Ce fut finalement elle qui entretint la conversation, qui finit par porter sur ses mensurations hors du commun : « soixante-dix quarante cinq soixante dix » me sussura-t-elle avec son accent antillais (en effet Joséphine était très fine). Je finis par délaisser les chiffres de Phine pour le chiffre affine...

Le chiffre de Cesar est un cas particulier de chiffre affine, où le coefficient directeur de la fonction affine est égal à 1. Avec un coefficient directeur égal à a, l’inverse de la fonction affine ax+b modulo N est c(x-b) où ac=1 modulo N. On peut trouver un tel c soit avec le théorème de Bachet-Bézout, soit en parcourant dans une boucle les valeurs de c successives jusqu’à ce que ac=1+kN.

Voici donc un crypteur-décrypteur en ligne utilisant un chiffre affine :

Chiffrage affine

Codage

Décodage

J’envoyai un bref rapport au Capitaine Kuntz :

Les chiffrages de Vigenère et affine sont au programme !

Ce à quoi il répondit :

Et Hill ?

La mission suivante se déroulerait donc aux USA. Je quittai alors Phine, non sans regrets, mais avec un bon vodka-martini...

Arrivé à La Guardia, je retrouvai comme convenu mon contact dans son taxi jaune. En effet sa couverture était un taxi. Je devais dire « hey, taxi, do you tax much ? » et il devait me répondre « for you it is free ». Doté d’un fort accent indien, Ravi avait l’air d’un ravisseur ravi. Après avoir commis une bonne centaine d’infractions, il me mena à l’office des brevets où figure le brevet numéro 1 845 947 de Lester S. Hill (1929) pour une machine à cryptographier, dont le principe est de faire un chiffre affine sur un espace de dimension supérieure à 1 (ici, le plan, avec des matrices carrées 2*2).

Le chiffre de Hill consiste alors à découper le message en blocs de 2 lettres (en ajoutant un espace final au besoin) et multiplier modulo N le vecteur formé par ces deux lettres (ou plutôt leur représentation numérique) par une matrice, qu’il faut inverser modulo N pour pouvoir déchiffrer.

Voici donc un simulateur en ligne de crypteur-décrypteur de Hill :

Chiffrage de Hill

Codage

Décodage

L’algorithme d’al-Kindi permet aussi de « casser » le code, en faisant des statistiques sur les doublets de lettres. Mais il n’y a pas de limite à la dimension des matrices utilisées...

Un autre brevet est plus d’actualité que celui de Hill [5] : Le brevet 4 405 829 de 1977, intitulé « RSA ». L’étape suivante était donc Washington et le Pentagone. Ravi me mena à Newark dans des crissements de pneus impressionnants (je me demandai comment il pouvait lui rester des pneus à force).

Arrivé à l’aéroport Dulles, je sympathisai avec une autochtone prénommée Rihanna, qui n’appréciait guère les vodkas-martinis, mais me fit découvrir les recoins secrets de Washington, puis ses recoins secrets à elle, avant de me faire tomber dans une trap function : J’aurais dû me méfier d’elle...

La légende dit que Martin Hellman et Whitfield Diffie, désireux que leurs recherches mathématiques ne puissent servir à la guerre ni au commerce, aient choisi l’arithmétique parce que là au moins, les recherches resteront purement théoriques. Sur ce point, ils ont été légèrement déçus...

Le cryptage Rivest Shamir Adleman porte le nom de Ronald Rivest, Adi Shamir et Leonard Adleman [6]

Voici donc un crypteur-décrypteur utilisant le code RSA :

Chiffrage RSA

Codage

Décodage

Ce qui est particulièrement intéressant avec RSA, c’est le concept de clé publique : Pour crypter un message, il suffit de connaître le module (95 ci-dessus, appelé clé RSA dans les deux onglets suivants) et l’exposant de codage (5 ci-dessus). Pour en déduire l’exposant de décodage (29 ci-dessus), il faut factoriser le module. Or si cette factorisation est assez rapide à mener sur 95 qui a un petit facteur premier, elle est beaucoup plus longue à mener sur le produit de deux grands nombres premiers aléatoires : Le décryptage sans l’exposant de décodage est un problème théoriquement possible à résoudre, mais en pratique « difficile » ; ce qui permet donc de publier la clé de cryptage, autorisant tout le monde à crypter mais empêchant de décrypter...

Pour éviter que tout cela tombe dans des oreilles indésirables, je décidai de crypter le rapport détaillé en trois exemplaires et règlementaire que je devais envoyer au Capitaine Kuntz. Pour cela, j’allumai le Mac du cybercafé de l’hôtel, et je démarrai le logiciel openSSL (sous bash par commodité). Je commençai par lui demander de générer une clé tout seul comme un grand :

Ce qui me produit un fichier contenant la clef RSA engendrée, écrite au format base64, et dont voici le contenu :

Le test de primalité d’openSSL me permit alors de vérifier que l’exposant e=65537 est premier :

Pour coder un message, il suffit alors d’utiliser la commande enc (comme « encode ») d’openSSL, par exemple avec un message tapé au clavier et un tuyau branché sur bash :

Et pour décoder un message, la même chose mais avec l’option -d (comme « decode ») :

Finalement je me méfiai d’openSSL et lui préférai GPG.

Je pus alors coder un message écrit dans le fichier original.txt, en entrant

En effet, il me fallut montrer patte blanche pour utiliser ma clé à moi :

GPG créa alors un fichier appelé original.txt.gpg. Je lui préférai sortie.gpg mais ce fichier était si bien encodé qu’il était illisible. Mais il était décryptable avec

Il me fallut à nouveau montrer patte blanche en écrivant « Vigenere » qui était ma phrase clé à moi :

Ceci fait, le fichier sortie.txt fut créé et contenait effectivement le message en clair :

Au cas où un utilisateur de DrGeoII souhaite communiquer une figure géométrique secrète, il peut utiliser les méthodes de cryptographies de DrGeoII (en réalité, de Pharo Smalltalk, le langage dans lequel est implémenté DrGeoII). Dans le cas où cet utilisateur choisirait RSA, il aurait à sa disposition

1. L’artillerie de l’agent trouble random, qui peut engendrer de grands entiers (et de grands ennuis parfois) ;
2. Le test de primalité de Miller-Rabin : Par exemple pour tester la primalité d’un nombre de Mersenne on peut faire ((2 raisedTo: 31) - 1) isProbablyPrime. et imprimer le résultat.
3. Le calcul d’un inverse modulo un entier, en utilisant l’algorithme d’Euclide étendu.

Voici comment DrGeoII engendre la clé publique à partir de la clé privée :