Description des algorithmes évoqués dans le programme : Chiffrages de Cesar, affine, de Vigenère, de Hill, RSA
Cette mission s’avérait plus ambitieuse que les précédentes : Le Capitaine Kuntz m’avait mis sur la piste d’un réseau dont l’origine remonte à l’antiquité, et dont les tentacules sont nombreuses et insoupçonnables : La cryptographie. Je m’empressai alors de poser la vodka-martini que j’avais l’habitude de déguster à l’ombre d’un parasol, et de quitter ma plage tropicale préférée (et ma couverture) pour me lancer dans cette enquête.
Le Capitaine Kuntz était l’un de ces espions comme on n’en fait plus, un « vieux de la vieille » [1] (à ceci près que la vieille préférait les jeunes éphèbes ; mais la vieille était très bonne simulatrice, depuis sa période KGB). Depuis une pénible mission à Madagascar dont il avait ramené des problèmes de santé à répétition, il avait abandonné l’action où il avait pourtant excellé (voire open officé). Le genre d’homme dont il est difficile de deviner l’âge, et qui est capable de foudroyer un homme (et surtout une femme) d’un seul regard ; le genre d’homme dont on n’aimerait pas être l’ennemi...
Je commençai donc par faire un tour du côté des services techniques, pour mon histoire de Q habituelle ; mais comme Q (James Bond) n’était pas là, je tombai sur son remplaçant du moment, que nous appellerons RMS pour garantir son anonymat. Il ne cessa de me parler d’un outil Unix pour tout crypter et tout décrypter. Il me laissa un conseil pour finir :
Faites tout ce que vous pouvez avec de l’arithmétique modulo n.
Me voilà bien : Si la méthode pour décrypter un message est elle-même cryptée, comment faire ? Et puis d’abord c’est qui ces agents ? Arithmétique c’est un nom de cerveau ça, mais modulo ça sent le nettoyeur, pas très rassurant...
Je partis alors pour des missions dans divers pays pour y trouver ce que mes prédécesseurs avaient fait dans ce domaine.
Détail technique : Chaque onglet ci-dessous présente un algorithme de chiffrage différent, et permet de le tester en ligne avec des cadres texte interactifs. Pour crypter ou décrypter l’un des messages donnés en exemple, leur ajouter des espaces ou déplacer le curseur à l’aide des flèches du clavier. Et si on est hardi, on peut supprimer les exemples et crypter son propre texte ! La plupart des algorithmes présentés gèrent mal les accents et autres caractères spéciaux (même le retour à la ligne est un caractère spécial, et même le Control+C qu’on fait pour copier le message). Il est donc conseillé de rajouter quelques espaces à la fin d’un texte pour le crypter correctement.
Les fichiers html complets (avec gestion des évènements clavier) sont téléchargeables en bas de l’article.
Sparte
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.
Rome
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.
Vigenère
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.
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...
Hill
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).
RSA
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...
openssl
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 :
-----BEGIN RSA PRIVATE KEY-----
MC0CAQACBQCBd0q9AgMBAAECBCFx8dUCAwDsewIDAIwnAgMAwQ0CAkxrAgMA0Ec=
-----END RSA PRIVATE KEY-----
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 ») :
gpg
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
gpg --encrypt-files -r 'James Bond' original.txt
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
gpg --decrypt-files -r 'James Bond' sortie.txt
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 :
DrGeoII
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
- L’artillerie de l’agent trouble random, qui peut engendrer de grands entiers (et de grands ennuis parfois) ;
- 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. - 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 :
Bibliographie et webographie
- Un TP en Seconde sur le sujet.
- L’art du secret (dossiers Pour la Science n°36), juillet 2002
- article de D.J. Mercier dans repères inter-IREM n°46, janvier 2002
- sur les dictionnaires en Python : Le sagebook
- une application des dictionnaires Python aux graphes est évoquée dans ce livre pages 159 à 167
- Toujours sur les dictionnaires, ce wikibook
- un site sur la cryptographie axé sur l’historique.
- Le logiciel Xcas est fourni avec des exemples de codes de Cesar, affine et RSA. Les algorithmes sont décrits dans l’aide en ligne. On peut d’ailleurs faire de la cryptographie « en vrai » avec le logiciel kruptor écrit pour Xcas... Au demeurant, ce logiciel est assorti d’un cours très complet.
- Le logiciel PARI/GP permet aussi de faire du RSA.
- Idem pour le langage de programmation Java.