Les nouvelles technologies pour l’enseignement des mathématiques
Intégration des TICE dans l’enseignement des mathématiques

MathémaTICE, première revue en ligne destinée à promouvoir les TICE à travers l’enseignement des mathématiques.

Cryptographie et arithmétique
Quelques pistes pour l’enseignement de la « spé maths » en TS

Description des algorithmes évoqués dans le programme : Chiffrages de Cesar, affine, de Vigenère, de Hill, RSA

Article mis en ligne le 14 avril 2012
dernière modification le 4 septembre 2021

par Alain Busser

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...

crypto ou stegano ?

  • La stéganographie consiste à cacher le message tant et si bien que son existence est imperceptible (exemple typique : L’encre sympathique).
  • La cryptographie par contre, ne cache pas le message codé (contrairement à ce que laisse penser l’étymologie du mot [2]) mais rend difficile le décodage, ce qui fait que théoriquement, l’intercepteur du message, bien que conscient de son existence, ne peut le décoder. Théoriquement...

Je partis alors pour des missions dans divers pays pour y trouver ce que mes prédécesseurs avaient fait dans ce domaine.

Des chiffres et des lettres

L’arithmétique fournit des bijections sur des ensembles d’entiers (en général, modulo un entier N supérieur ou égal au nombre de lettres de l’alphabet). Pour en déduire une permutation (ou bijection) des lettres, il faut une bijection entre les chiffres et les lettres. D’où le nom de chiffrage donné à différents algorithmes de cryptographie.

En JavaScript, pour passer d’une lettre à un nombre, on peut faire

  1. texte.charCodeAt(n)

qui transforme un caractère (de rang n) en nombre (son code ASCII ou Unicode), et pour l’opération inverse :

  1. String.fromCharCode(nombre)

Les caractères de numéro inférieur à 32 ne s’affichant pas bien, on va soustraire 32 à chaque numéro obtenu, puis rajouter 32 à chaque numéro codé. Donc finalement, on fera

  1. texte.charCodeAt(n)-32
  2. String.fromCharCode(nombre+32)

Télécharger

Ainsi, les nombres utiles pour coder seront compris entre 0 (l’espace, dont l’unicode est 32) et 94 (le tilde, dont l’unicode est 126). Cet espace comprend les majuscules, minuscules, chiffres et signes de ponctuation. Mais pas les accents et cédille, qui seront donc mal codés par les algorithmes ci-dessous.


Pour ajouter une lettre à la fin d’un mot, on utilise concat :

mot=mot.concat(lettre)

Pour transformer un mot en tableau de lettres, on utilise split :

  1. tableau=mot.split("")

Ce qui permet d’extraire une lettre du tableau (tirage sans remise) avec pop :

  1. lettre=tableau.pop()

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.

Réalisation en JavaScript

Cryptage

L’objet de départ est une chaîne de caractères appelée mess1 (parce que c’est le message numéro 1 de cette histoire ; il y en aura trois autres). Pour être certain qu’il aura suffisamment de lettres valides, on en ajoute 7 (des espaces) avec

  1. mess1.concat("       ")

Ensuite on le transforme en un tableau unidimensionnel en découpant (« split ») ses lettres ; au passage on met le tableau à l’envers parce que l’instruction « pop » va lire les lettres en commençant par la fin :

  1. mess1=mess1.split("").reverse();

Reste maintenant à remplir la matrice à partir de ce tableau unidimensionnel. Cette matrice de 7 lignes s’appellera tableau1 et pour expliquer à JavaScript que ses lignes sont elles-mêmes des tableaux, on peut initialiser ce tableau avec des tableaux vides : Les sept sceaux :

  1. var tableau1=[[],[],[],[],[],[],[]];

Ensuite on remplit cette matrice, ligne par ligne (l’index de la ligne est i), en vidant au fur et à mesure le tableau unidimensionnel mess1 :

  1.         for(var i=0;i<7;i++){
  2.                 for(var j=0;j<Math.floor(longueur1/7);j++){
  3.                         tableau1[i][j]=mess1.pop();
  4.                 }
  5.         }

Télécharger

On se retrouve alors avec une matrice tableau1 à transposer ; ce qu’on fait en la lisant colonne par colonne :

  1.         for(var j=0;j<Math.ceil(longueur1/7);j++){
  2.                 for(var i=0;i<7;i++){
  3.                         lettre=tableau1[i][j];
  4.                         if(lettre){
  5.                                 mess2=mess2.concat(lettre);
  6.                         }
  7.                 }
  8.         }

Télécharger

La chaîne de caractère mess2 (qui avait été créé vide juste avant) contient alors le message codé !

Finalement, l’algorithme de codage s’écrit ainsi :

  1. function chiffrageScytale(){
  2.         mess1.concat("       ");
  3.         var longueur1=mess1.length;//le nombre de lettres
  4.         mess1=mess1.split("").reverse();//conversion en tableau
  5.         var tableau1=[[],[],[],[],[],[],[]];//les 7 lignes, vides
  6.         for(var i=0;i<7;i++){//remplissage du tableau ligne par ligne
  7.                 for(var j=0;j<Math.floor(longueur1/7);j++){
  8.                         tableau1[i][j]=mess1.pop();
  9.                 }
  10.         }
  11.         var mess2=''
  12.         for(var j=0;j<Math.ceil(longueur1/7);j++){
  13.                 for(var i=0;i<7;i++){
  14.                         lettre=tableau1[i][j];
  15.                         if(lettre){
  16.                                 mess2=mess2.concat(lettre);
  17.                         }
  18.                 }
  19.         }
  20. }

Télécharger


Décryptage

Une fois correctement codé, le message mess3 contient les bonnes lettres mais permutées, et il est nécessaire de lire ses lettres dans l’ordre suivant : 0-6-13-20-...etc-1-7-14-21...etc-2-8-15-22...

Pour cela, on peut créer une matrice tableau3 dans laquelle l’élément (i,j) contient la lettre numéro i+7*j ; il ne reste plus qu’à retransposer cette matrice pour avoir le message décodé mess4 :

  1. function dechiffrageScytale(){
  2.         var longueur2=mess3.length;
  3.         mess3.concat("       ");
  4.         var tableau3=[[],[],[],[],[],[],[]];
  5.         for(var i=0;i<7;i++){
  6.                 for(var j=0;j<Math.ceil(longueur2/7);j++){
  7.                         tableau3[i][j]=mess3.charAt(j*7+i);
  8.                 }
  9.         }
  10.         var mess4=''
  11.         for(var i=0;i<7;i++){
  12.                 for(var j=0;j<Math.ceil(longueur2/7);j++){
  13.                         mess4=mess4.concat(tableau3[i][j]);
  14.                 }
  15.         }
  16. }

Télécharger


Voici une scytale en ligne (à 7 crans) :

Cryptage par scytale

Codage

Entrer un message à chiffrer:


Le message chiffré est :

Décodage

Entrer un message à déchiffrer:

Le message déchiffré est :


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.

Avec un décalage de 7 lettres

Pour le chiffrage (de mess1 vers mess2), on commence par créer une variable numérique longueur1 égale au nombre de lettres du message à coder. Puis on crée un tableau appelé tableau1 dans lequel on place les nombres correspondant aux lettres du message, l’une après l’autre. Enfin on crée un autre tableau appelé tableau2 dans lequel on place les nombres de tableau1 décalés de 7 rangs modulo 95. Enfin on crée une variable mess2 de type texte, où on écrit l’une après l’autre les lettres figurant dans le tableau tableau2 :

  1. function chiffrageCesar(){//126-32=94:N=95
  2.         var longueur1=mess1.length;
  3.         var tableau1=new Array();
  4.         for(var n=0;n<longueur1;n++){
  5.                 tableau1[n]=mess1.charCodeAt(n)-32;
  6.         }
  7.         var tableau2=new Array();
  8.         for(var n=0;n<longueur1;n++){
  9.                 tableau2[n]=(tableau1[n]+7)%95;
  10.         }
  11.         var mess2=''
  12.         for(var n=0;n<longueur1;n++){
  13.                 mess2=mess2.concat(String.fromCharCode(tableau2[n]+32));
  14.         }
  15. }

Télécharger

Le décryptage (de mess3 vers mess4) fonctionne pareil, sauf qu’au lieu d’additionner 7, on soustrait 7 :

  1. function dechiffrageCesar(){
  2.         var longueur2=mess3.length;
  3.         var tableau3=new Array();
  4.         for(var n=0;n<longueur2;n++){
  5.                 tableau3[n]=mess3.charCodeAt(n)-32;
  6.         }
  7.         var tableau4=new Array();
  8.         for(var n=0;n<longueur2;n++){
  9.                 tableau4[n]=(tableau3[n]-7)%95;
  10.         }
  11.         var mess4=''
  12.         for(var n=0;n<longueur2;n++){
  13.                 mess4=mess4.concat(String.fromCharCode(tableau4[n]+32));
  14.         }
  15. }

Télécharger


En bash, il y a une commande appelée tr (Unix) qui réalise un chiffre de Cesar, à condition de lui dire les lettres obtenues (tr veut dire « transpose »). Pour le décalage de 7 lettres ici présent, les lettres de A à Z (écrites ’A-Z’) deviennent les lettres de H à Z suivies par les lettres de A à G, écrites ’H-ZA-G’. Pour effectuer le cryptage, il faut que bash puisse envoyer à tr le message à crypter, et que une fois transposé, tr puisse envoyer le résultat à bash pour que celui-ci puisse l’« échoer ». Il faut donc câbler un tube (shell) entre bash et tr, tout simplement en écrivant le caractère « pipe » (AltGr et 6 en même temps) entre la partie bash et la partie tr :

  1. echo "ALEA JACTA EST" | tr 'A-Z' 'H-ZA-G'

Le décodage se fait en reconnaissant un autre code de Cesar, qui transforme A en R :

  1. echo "HSLH QHJAH LZA" |tr 'A-Z' 'T-ZA-S'

On peut associer la rotation des majuscules avec une rotation analogue des minuscules :

  1. #! /bin/bash
  2.  
  3. echo "message pour chiffrer SVP" | tr 'A-Za-z' 'H-ZA-Gh-za-g'

Télécharger


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

Chiffrage Cesar

Codage

Entrer un message à chiffrer:

Le message chiffré est :

Décodage

Entrer un message à déchiffrer:

Le message déchiffré est :


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.

En JavaScript

Comme la première lettre de la clé (« V ») a pour code 86-32=64, on va donc appliquer à la première lettre du message un chiffre de Cesar de décalage 64 (modulo 95). Ce qu’on peut faire en additionnant 64 au code de la première lettre. On fait pareil avec les autres lettres, mais comme le mot-clé n’a que 8 lettres, on utilise

  1. motcle.charCodeAt(n%8)

comme paramètre de décalage ; ce qui revient à recopier le mot-clé jusqu’à ce que le résultat soit aussi long que le message à coder. Remarque : Chaque caractère étant codé sur 7 bits, un mot de 8 lettres comme « Vigenere » est une « clé de 56 bits ». À comparer avec les 256 bits considérés comme peu sûrs dans SHA-1...

La modification ci-dessus est la seule apportée au chiffre de Cesar, qui se crypte ainsi (de mess1 vers mess2) :

  1. function chiffrageVigenere(){
  2.         var motcle="Vigenere"
  3.         var longueur1=mess1.length;
  4.         var tableau1=new Array();
  5.         for(var n=0;n<longueur1;n++){
  6.                 tableau1[n]=mess1.charCodeAt(n)-32;
  7.         }
  8.         var tableau2=new Array();
  9.         for(var n=0;n<longueur1;n++){
  10.                 tableau2[n]=(tableau1[n]+motcle.charCodeAt(n%8))%95;
  11.         }
  12.         var mess2=''
  13.         for(var n=0;n<longueur1;n++){
  14.                 mess2=mess2.concat(String.fromCharCode(tableau2[n]+32));
  15.         }
  16. }

Télécharger

Pour décrypter (de mess3 vers mess4) il faut connaître aussi le mot-clé :

  1. function dechiffrageVigenere(){
  2.         var motcle="Vigenere"
  3.         var longueur2=mess3.length;
  4.         var tableau3=new Array();
  5.         for(var n=0;n<longueur2;n++){
  6.                 tableau3[n]=mess3.charCodeAt(n)-32;
  7.         }
  8.         var tableau4=new Array();
  9.         for(var n=0;n<longueur2;n++){
  10.                 tableau4[n]=(tableau3[n]+2*95-motcle.charCodeAt(n%8))%95;
  11.         }
  12.         var mess4=''
  13.         for(var n=0;n<longueur2;n++){
  14.                 mess4=mess4.concat(String.fromCharCode(tableau4[n]+32));
  15.         }
  16. }

Télécharger


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

Chiffrage Vigenere

Codage

Entrer un message à chiffrer:

Le message chiffré est :

Décodage

Entrer un message à déchiffrer:

Le message déchiffré est :


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)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.

scriptage du cryptage

On choisit une fonction affine au hasard (avec un coefficient directeur inversible modulo 95 tout de même) ; par exemple $x \mapsto 13x+2$ (modulo 95). Pour le décryptage, on a besoin de connaître la fonction inverse, qui est $x \mapsto 22x+51$ (modulo 95) [4]. La seule différence par rapport au chiffre de Cesar est donc l’expression de ces fonctions affines au lieu du simple décalage. Pour crypter (de mess1 vers mess2) :

  1. function chiffrageAffine(){
  2.         var longueur1=mess1.length;
  3.         var tableau1=new Array();
  4.         for(var n=0;n<longueur1;n++){
  5.                 tableau1[n]=mess1.charCodeAt(n)-32;
  6.         }
  7.         var tableau2=new Array();
  8.         for(var n=0;n<longueur1;n++){
  9.                 tableau2[n]=(13*tableau1[n]+2)%95;
  10.         }
  11.         var mess2=''
  12.         for(var n=0;n<longueur1;n++){
  13.                 mess2=mess2.concat(String.fromCharCode(tableau2[n]+32));
  14.         }
  15. }

Télécharger

et pour décrypter (de mess3 vers mess4) :

  1. function dechiffrageAffine(){
  2.         var longueur2=mess3.length;
  3.         var tableau3=new Array();
  4.         for(var n=0;n<longueur2;n++){
  5.                 tableau3[n]=mess3.charCodeAt(n)-32;
  6.         }
  7.         var tableau4=new Array();
  8.         for(var n=0;n<longueur2;n++){
  9.                 tableau4[n]=(22*tableau3[n]+51)%95;
  10.         }
  11.         var mess4=''
  12.         for(var n=0;n<longueur2;n++){
  13.                 mess4=mess4.concat(String.fromCharCode(tableau4[n]+32));
  14.         }
  15. }

Télécharger


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

Chiffrage affine

Codage

Entrer un message à chiffrer:

Le message chiffré est :

Décodage

Entrer un message à déchiffrer:

Le message déchiffré est :


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.

The fuel on the Hill

Toujours modulo 95, on choisit une matrice au hasard en espérant qu’elle soit inversible modulo 95. Par exemple :

15 7
3 8

dont le déterminant est 99, soit 4 (modulo 95) : Bingo, ce déterminant est premier avec 95, et la matrice est inversible. Reste à l’inverser pour décrypter. Avec quelque chose comme

  1. for(d=1;d<95;d++){
  2.     if((4*d)%95==1){
  3.         alert(d);
  4.     }
  5. }

Télécharger

on trouve que l’inverse du déterminant est 24 (en effet 24*4=96=95+1). D’où l’inverse de la matrice :

2 22
23 75

Pour couper un message en doublet de lettres, il est nécessaire qu’il y ait un nombre pair de lettres. Dans ce cas on calcule le nombre de lettres modulo 2 et si le résultat vaut 1, on rajoute une espace en fin de message (caractère numéro 32 en ASCII). Sinon, la différence n’est pas importante par rapport au chiffrage affine en dimension 1 : Le cryptage (de mess1 vers mess2) :

  1. function chiffrageHill(){
  2.         var longueur1=mess1.length;
  3.         var tableau1=new Array();
  4.         for(var n=0;n<longueur1;n++){
  5.                 tableau1[n]=mess1.charCodeAt(n)-32;
  6.         }
  7.         if (longueur1%2==1){tableau1[longueur1]=32; longueur1++;}
  8.         var tableau2=new Array();
  9.         for(var n=0;n<longueur1;n+=2){
  10.                 tableau2[n]=(15*tableau1[n]+7*tableau1[n+1])%95;
  11.                 tableau2[n+1]=(3*tableau1[n]+8*tableau1[n+1])%95;
  12.         }
  13.         var mess2=''
  14.         for(var n=0;n<longueur1;n++){
  15.                 mess2=mess2.concat(String.fromCharCode(tableau2[n]+32));
  16.         }
  17. }

Télécharger

Et le décryptage (de mess3 vers mess4) :

  1. function dechiffrageHill(){
  2.         var longueur2=mess3.length;
  3.         var tableau3=new Array();
  4.         for(var n=0;n<longueur2;n++){
  5.                 tableau3[n]=mess3.charCodeAt(n)-32;
  6.         }
  7.         if (longueur2%2==1){tableau3[longueur2]=0; longueur2++;}
  8.         var tableau4=new Array();
  9.         for(var n=0;n<longueur2;n+=2){
  10.                 tableau4[n]=(2*tableau3[n]+22*tableau3[n+1])%95;
  11.                 tableau4[n+1]=(23*tableau3[n]+75*tableau3[n+1])%95;
  12.         }
  13.         var mess4=''
  14.         for(var n=0;n<longueur2;n++){
  15.                 mess4=mess4.concat(String.fromCharCode(tableau4[n]+32));
  16.         }
  17. }

Télécharger


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

Chiffrage de Hill

Codage

Entrer un message à chiffrer:

Le message chiffré est :

Décodage

Entrer un message à déchiffrer:

Le message déchiffré est :


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]

RSA c’est ça !

  1. On part de la remarque que 95 est le produit de 5 et 19 ;
  2. Donc il y a (5-1)(19-1)=72 éléments inversibles modulo 95 ;
  3. Tout exposant premier avec 72 peut servir à faire le codage : On choisit 5 ;
  4. Par essais successifs, ou par le théorème de Bézout, on trouve que modulo 72, l’inverse de 5 est 29
  5. Pour coder un nombre, on l’élève à la puissance 5 modulo 95 ;
  6. Pour décoder un nombre, on l’élève à la puissance 29 modulo 95.

En JavaScript, le calcul de puissances cinquième et vingt-neuvième pose des problèmes de dépassement de capacité ce qui rend leur réduction modulo 95 imprévisible. On est donc obligé de réinventer ces fonctions, en réduisant modulo 95 le plus souvent possible pour ne pas avoir de trop grands nombres. On peut en profiter pour faire une exponentiation rapide :

  1. function puiss5(n){
  2.         var x=n;
  3.         x=(x*x)%95;
  4.         x=(x*x)%95;
  5.         x=(x*n)%95;
  6.         return x;
  7. }
  8.  
  9.  
  10.  
  11. function puiss29(n){
  12.         var c=(n*n)%95;
  13.         var q=(c*c)%95;
  14.         var h=(q*q)%95;
  15.         var s=(h*h)%95;
  16.         var x=(h*s)%95;
  17.         x=(x*q)%95;
  18.         x=(x*n)%95
  19.         return x;
  20. }

Télécharger

Ceci fait, il suffit d’appliquer ces fonctions à la place du cryptage affine :

Pour le cryptage (de mess1 vers mess2) :

  1. function chiffrageRSA(){
  2.         var longueur1=mess1.length;
  3.         var tableau1=new Array();
  4.         for(var n=0;n<longueur1;n++){
  5.                 tableau1[n]=mess1.charCodeAt(n)-32;
  6.         }
  7.         var tableau2=new Array();
  8.         for(var n=0;n<longueur1;n++){
  9.                 tableau2[n]=puiss5(tableau1[n]);
  10.         }
  11.         var mess2=''
  12.         for(var n=0;n<longueur1;n++){
  13.                 mess2=mess2.concat(String.fromCharCode(tableau2[n]+32));
  14.         }
  15. }

Télécharger

Pour le décryptage (de mess3 vers mess4) :

  1. function dechiffrageRSA(){
  2.         var longueur2=mess3.length;
  3.         var tableau3=new Array();
  4.         for(var n=0;n<longueur2;n++){
  5.                 tableau3[n]=mess3.charCodeAt(n)-32;
  6.         }
  7.         var tableau4=new Array();
  8.         for(var n=0;n<longueur2;n++){
  9.                 tableau4[n]=puiss29(tableau3[n])%95;
  10.         }
  11.         var mess4=''
  12.         for(var n=0;n<longueur2;n++){
  13.                 mess4=mess4.concat(String.fromCharCode(tableau4[n]+32));
  14.         }
  15. }

Télécharger

Démonstration

  • Par construction, $5 \times 29=145$ est congru à 1 modulo 72 ;
  • D’après le petit théorème de Fermat, si x n’est pas divisible par 5, $x^4$ est congru à 1 modulo 5 (puisque 5 est premier) ;
    • Donc $x^{72}\equiv1^{18}\equiv1$ modulo 5
    • Donc $x^{144}\equiv 1$ modulo 5 ;
    • Donc $x^{145}\equiv x$ modulo 5.
  • Et si x est multiple de 5, $x^{145}\equiv 0^ {145}\equiv 0 \equiv x$ ; dans tous les cas, $x^{145}\equiv x$ modulo 5 ;
  • De même, $x^{145}\equiv x$ modulo 19.
  • Ainsi, $x^{145}- x$ est divisible à la fois par 5 et 19 ; mais comme 5 et 19 sont premiers, d’après le lemme de Gauss, $x^{145}- x$ est donc divisible par leur produit 95 :
  • Modulo 95, $x^{145}\equiv x$ soit ${(x^5)}^{29}\equiv x$ :

La puissance vingt-neuvième est bien la bijection réciproque de la puissance cinquième.


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

Chiffrage RSA

Codage

Entrer un message à chiffrer:

Le message chiffré est :

Décodage

Entrer un message à déchiffrer:

Le message déchiffré est :

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 ») :

openSSL et les premiers

rand est capable de fabriquer un nombre premier aléatoire :

Mais encodé en binaire avec des chiffres ajoutés, il n’est pas nécessairement premier si on le convertit directement en écriture décimale :

Il n’est pas du tout premier, puisqu’en écrivant ceci en bash

  1. factor 4726053557035811721

on a cela :

4726053557035811721 : 3 3 7 220126871 340788577

5 facteurs dont 3 franchement petits, on est loin du nombre premier !

C’est néanmoins de tels entiers premiers aléatoires qui sont multipliés entre eux pour engendrer une clé RSA avec genrsa.

gpg

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

J’obtins d’abord une clé

GPG permet d’obtenir une clé (qui peut être certifiée ou non, caduque ou non) de codage publique, par une sorte de dialogue avec l’utilisateur. On tape

  1. gpg --gen-key

Je choisis alors le type 1 (RSA) :

Puis je choisis la longueur la plus petite possible : 1024 bits :

Je demandai alors que la clé ne soit valable qu’une journée (« cette clé s’autodétruira dans 24 heures » !) :

GPG me demanda alors mon nom, mon adresse mail et une phrase clé que je fournis au clavier :

Comme phrase clé, je choisis « Vigenere ».

Puis il me demanda de m’exciter sur mes clavier et souris, ce que je fis frénétiquement :

Puis la clé fut créée par GPG :

Ce que je pus vérifier en listant les clés :

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

  1. 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

  1. 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

  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 :


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.