Échanger des informations secrètes sur Internet ?
C’est possible grâce au chiffrement.
Prouver son identité numériquement ? Cette fois-ci il s’agit de la signature numérique.
Ce sont les deux problèmes de base de la cryptographie : la science des codes secrets. Dans les deux cas, ce sont des calculs compliqués que seule la machine de la personne qui doit déchiffrer le message ou celle qui doit s’authentifier peut faire à partir d’une « clef ».

Plusieurs articles, y compris certains pour expliquer aux enfants, nous décrivent ces méthodes, dont la méthode RSA. Ici nous allons aller plus loin.

Il est essentiel qu’il n’existe pas de raccourci, que quelqu’un qui ne connaisse pas la clef n’ait pas de meilleure stratégie que de toutes les essayer. Connue sous le nom de « chiffrage RSA », la méthode usuelle de calcul de ces clefs devient fragile : de tels raccourcis existent, et bien qu’ils soient quand même assez longs avec la démultiplication de la puissance des ordinateurs, il devient possible de parcourir de tels raccourcis : il faut alors augmenter la taille des clefs pour compenser et RSA devient de moins en moins efficace. Plus grave encore, on connaît des raccourcis quantiques très courts ! Si l’ordinateur quantique venait à voir le jour, alors on ne pourrait plus compter sur les méthodes de cryptographie usuelle.

C’est là que la géométrie vient à la rescousse : la méthode des « réseaux euclidiens » offre une alternative efficace : on ne connaît pas de bon raccourci, même quantique ! Et cette méthode a un double bonus en terme de popularisation des mathématiques, car elle est conceptuellement simple. On peut même la comprendre en jouant à un jeu vidéo aux allures de Tetris, qui s’appelle « Cryptris ». Découvrons cela.

Contexte : rappel sur les principes de la cryptographie.

Échanger des informations secrètes sur Internet pose un problème très particulier : il faut que deux personnes, qui ne se connaissent peut-être pas, qui ne peuvent communiquer que publiquement devant tout le monde [1] , donc sans s’envoyer aucune information privée, puissent tout de même s’envoyer un message secret qu’elles seules pourront lire. En étant sûres que personne n’ait volé leur identité [2]. Une telle solution existe. C’est le chiffrage à double clef : clef publique/clef privée.

Comme expliqué par exemple sur Wikipédia, pour recevoir un message chiffré, il suffit de diffuser un cadenas ouvert (c’est la clef publique) et de garder secrète la combinaison de ce cadenas. Celui qui veut nous envoyer un message le dépose dans un coffre, ferme le coffre avec le cadenas, il n’a pas besoin de la clef pour cela, et nous le renvoie. Ici, on peut fermer le cadenas ouvert sans passer par la combinaison, comme avec les vieux cadenas à numéro. À sa réception, seul celui qui a la combinaison secrète peut ouvrir le coffre, à supposer le coffre inviolable.

Bien entendu ce n’est pas un « vrai » cadenas, mais un calcul à sens unique. C’est un calcul qui une fois appliqué à un message le rend indéchiffrable. C’est-à-dire qu’il est très difficile de trouver un calcul qui permette de faire le chemin inverse. Par exemple, dans un monde où la division n’existe pas, si je multiplie le message « 12345 » par la clef publique « 5 » le résultat « 61725 » ne ressemble plus du tout au message et je ne peux le retrouver sans tester toutes les solutions, puisque nous sommes dans un monde où on ne peut pas faire la division par « 5 ». Cependant une brèche secrète permet à la personne qui a conçu la fonction à sens unique de décoder facilement le message grâce à un élément d’information qu’elle possède, appelé clef privée. Par exemple, si je remultiplie « 61725 » par « 2 » alors j’obtiens « 123450 » et hop : mon message réapparaît, il suffit d’enlever le 0 qui est à droite sans faire de division. Je peux encore améliorer la méthode. Si dans « 12345 », « 123 » est la partie utile de mon message, tandis que « 45 » est un aléa tiré au hasard. Alors cet ajout permet de complexifier ce qui est chiffré, pour mieux mélanger les chiffres. Nous savons alors qu’il faut simplement enlever les 3 chiffres de droite pour lire le message correct.

Ce même mécanisme peut servir à l’authentification, comme nous l’expliquons aux enfants qui demandent « comment peut-on cacher des secrets sur Internet ? ». Cela permet, par exemple, de vérifier l’identité d’un site qui se connecterait à notre banque pour un achat en ligne.

Voici donc mes ingrédients de notre histoire et les notations de cet article :

Mais tout ceci n’est qu’une histoire, car on sait très facilement faire des divisions [3]. Et il faut donc proposer des mécanismes qui résistent à la pression de l’augmentation de la puissance des calculs. Voilà à quoi s’attellent les cryptographes mathématiciens et informaticiens, dévoués à la science des codes secrets.

Comme nous l’avons dit plus haut, les méthodes standard, bien qu’encore utilisables semblent aujourd’hui fragiles avec l’augmentation de la puissance des calculateurs. Les cryptographes s’intéressent à un autre outil mathématique, les réseaux euclidiens. Cet outil a récemment permis de construire une cryptographie plus sûre et plus puissante.

Le jeu vidéo Cryptris illustre cette nouvelle cryptographie ; et les réseaux euclidiens y sont cachés derrière les règles d’une sorte de Tetris. Dans ce premier article nous n’irons pas encore voir ce qui ce cache derrière ces briques, les fameux réseaux Euclidiens : pour cela rendez-vous dans le second article.

Trouver un mécanisme solide de clef publique et privée.

Dans l’exemple expliqué plus haut nous avions triché, nous avions supposé qu’il n’était pas possible de diviser par 5. Ça peut marcher contre un élève de CP (et encore, ils sauront vous surprendre !), mais il va falloir être un peu plus malin pour faire de la vraie cryptographie.

Étape 1 : Commencer par mettre le message en chiffres.

Avant toute chose, il faut convertir les messages en nombre ou suite de nombres. Prenons un message de deux lettres, m = « OK » , nous allons coder ces caractères, non pas en binaire mais en ternaire selon la table ci-dessous, car notre méthode de chiffrage nous permet d’utiliser non pas un code {0, 1} mais un code {-1, 0, 1} : plutôt que des bits, on utilise des trits. Dans le jeu : une brique bleu-azur vaut -1, une brique bleu-clair +1 et une brique bleu-sombre 0.

Ici, on va grouper les trits par groupes de 4, chaque groupe permet de représenter un caractère parmi 3⁴ = 3*3*3*3 = 81 symboles (lettres ou chiffres) ; de la même façon que les bits d’un ordinateur vont par groupe de 8, pour représenter 2⁸ =2*2*2*2*2*2*2*2 = 256 caractères.

Sur cet exemple, on peut donc lire :

m = [ 0, -1, -1, 1, -1, 0, -1, 1 ] = « OK »

Étape 2 : Puis cacher le message dans du bruit et un autre nombre.

Maintenant, pour cacher ce message m = [0, -1, -1, 1, -1, 0, -1, 1] nous allons le brouiller, grâce à une clef dite publique et en y ajoutant du bruit aléatoire : nous allons appliquer ou « combiner » la clef à notre message plusieurs fois, en la manipulant à chaque fois aléatoirement pour brouiller l’opération qui est faite, on dit qu’on mélange la clef. L’idée est qu’un pirate qui intercepte le message et qui a connaissance de cette clef - puisqu’elle est publique -, soit dans l’incapacité de retrouver l’ensemble des mélanges aléatoires de cette clef qui ont été combinés au message et donc d’être incapable d’effectuer l’opération inverse pour retrouver le message initial.

Mais de quoi est donc faite la clef ? Et que sont ces opérations dont on parle ? La clef est en réalité une suite de nombres du même type que le message. Cela peut être par exemple : p = [-1, 6, 8, 0, -2, -1, 7, 7] , ce qui se traduira dans le jeu par [ 1 brique bleu-clair, 9 briques bleu-clair , 7 briques bleu-azur , etc. ]. On aura ainsi une suite de colonnes de briques plus ou moins grandes et de couleurs différentes selon qu’elles représentent un nombre positif ou négatif. Ajouter du bruit à cette clef publique consiste à la manipuler en permutant les nombres (par rotation des colonnes) ou en inversant les signes de ces nombres (donc la couleur des briques). Le bruit est une valeur a aléatoirement générée par l’ordinateur.

Surtout, ce qui est amusant, c’est que ces opérations correspondent à un jeu de type « Tetris ». Regardons comment cela fonctionne… Sur la figure ci-contre, on voit le message originel m prêt à recevoir « sur la tête » la clef publique p. La clef p s’apprête donc à être combinée au message m.

Regardons comment se relient calculs arithmétiques et opérations graphiques sur un exemple : la clef publique vaut [-1, 6, 8, 0, -2, -1, 7, 7] en comptant le nombre de case et en souvenant qu’une brique bleu clair est +1, une brique bleu azur est -1. Lorsqu’elle va tomber sur le message [0, -1, -1, 1, -1, 0, -1, 1] le résultat de l’addition colonne par colonne sera [-1, 5, 7,…].

Cette combinaison est en réalité une somme [4]. En effet, lorsqu’on fait « tomber » la clef publique sur le message (comme dans Tetris), dans chaque colonne, les briques de même couleur s’empilent et celles de couleur opposée s’annulent. Souvenons-nous : brique bleu-azur c’est -1 et brique bleu-clair +1. Une brique bleu-azur sur une brique bleu-clair ça donne -1 + 1 = 0 (elles s’annulent et on obtient une absence de brique). En revanche une brique bleu-azur sur une autre brique bleu-azur , cela donne -1 -1 = -2 (les briques s’empilent) et il en va de même avec les briques bleu-clair (2 briques bleu-clair s’empilent donnant la valeur +2) ; on a ainsi effectué une somme dans chaque colonne, et obtenu le résultat temporaire t en bas, que l’on note p + m = t c’est en fin de compte :

Ici nous avons appliqué la clef au message une première fois, mais on peut réitérer l’opération en mélangeant cette fois-ci la clef. Ce sont les permutations ou inversions de signes aléatoires dont nous parlions plus haut. Et cela, on peut le répéter autant de fois qu’on le souhaite en brouillant à chaque fois un peu plus le message.

Voici tous les calculs que nous pouvons donc faire avec cette clef en jouant à ce jeu :

• Addition : Faire tomber la clef avec la flèche [↓] on obtient alors p + m comme décrit ci-dessus, et quand on fait tomber la clef plusieurs fois 2 p + m , 3 p + m , …
• Soustraction : Inverser les couleurs de la clef (donc le signe des nombres) avec la flèche [↑] : [ 0, -2, 4, 1, -1, 0, -3, 5 ] devient [ 0, 2, -4, -1, 1, 0, 3, -5 ]. En la faisant ensuite tomber, cela permet d’atteindre -p +m , -2 p + m , …
• Rotation : On peut encore faire tourner les nombres de la clef avec les flèches [←] et [→] : avec [→], [ 0, -2, 4, 1, -1, 0, -3, 5 ] devient [ 5, 0, -2, 4, 1, -1, 0, -3 ] (on décale tout vers la droite, et le dernier revient au début). Cela permet de mélanger les nombres et l’opération correspond à l’opération p * X dans le calcul. Et quand je la fais ensuite tomber, on atteint le résultat (X*p )+m.

Ici, X correspond à la valeur de cette « multiplication », qui n’en est pas une au sens habituel du terme puisqu’elle correspond en fait à une permutation circulaire des colonnes. On en reparlera bientôt, dans l’article compagnon.

En fin de compte donc, si p est la clef publique, chaque combinaison que nous effectuons, revient à tirer au hasard un mélange aléatoire a (a n’est pas vraiment un nombre) et calculer :

c’est-à-dire que nous avons mélangé la clef publique p à l’aide de ce mélange aléatoire a et combiné ce tout avec le message. Comme dit plus haut, a n’est pas un nombre, mais une formule, qui combine des nombres, des rotations X, des multiplications *, et des additions (c’est ce qu’on appelle un polynôme, mais une chose à la fois... ). Le message est alors caché dans le résultat c et il le sera d’autant plus que l’on reproduit ces opérations aléatoirement. Par exemple, si le message m a des régularités, par exemple il y a plus de lettres ’e’ que de lettres ’z’ comme c’est le cas pour les mots de la langue française, ces régularités ne se voient plus dans le mélange. Ici, le mélange est noté comme une multiplication * et la combinaison notée comme une addition +. Ce ne sont pas celles des nombres usuels, mais elles fonctionnent un peu comme ces opérations. Et dans l’article suivant, nous donnerons toutes les explications mathématiques.

Et voilà : nous avons donc pu relier chaque opération de notre calcul de chiffrement avec… une opération d’un jeu à la Tetris ! Nous voilà en train de calculer de manière « graphique ».

Nous avons ici montré comment chiffrer, par le jeu, un message avec une clef publique, c’est-à-dire réaliser ce calcul de multiplications et d’additions. Ce qui est intéressant, c’est que dans le message codé c que l’on voit ici, il est impossible pour un pirate de séparer le message m de son chiffre c, à moins d’énumérer toutes les valeurs du bruit et de tous les mécanismes inverses de p possibles. Or vous l’aurez compris le nombre de combinaisons possibles devient vite énorme, et c’est ce qui est recherché pour contrer la puissance de calcul des ordinateurs pirates !

Mais alors comment le destinataire légitime pourra-t-il distinguer le message du bruit ? Passons maintenant au déchiffrement !

Étape 3 : Créer une porte secrète grâce à la clef privée.

Celui qui a généré la clef publique p a évidemment une clef privée secrète s et c’est là toute l’astuce. En effet, ce dernier a généré la clef publique à partir d’une clef privée que lui seul connaît. En rendant la clef publique publique , il permet à tout le monde de chiffrer des messages, que lui seul pourra déchiffrer avec sa clef privée ! Les pirates quant à eux, perdront quelques cheveux à essayer de le déchiffrer avec la clef publique.

Et là, il y a une astuce. Pour générer p on effectue plusieurs combinaisons de s avec elle-même, ce qui revient dans le jeu à faire tomber la clef privée s sur elle-même plusieurs fois en effectuant à chaque fois un mélange aléatoire (rotation, ← et →, et changement de signe, ↑ ). Cela s’écrirait mathématiquement, pour une valeur g quelconque, p = g * s ou encore

Dans cette formule X * s, X² * s, etc., correspondent aux rotations de la clef s (cad [←] et [→]) nous verrons dans l’article compagnon que ce n’est pas qu’une question de notation : il y a des polynômes derrière tout cela et les valeurs g₀, g₁, g₂ … sont des nombres usuels (par exemple g₀=2, g₁=-1, entiers positifs ou négatifs. Ils correspondent aux opérations d’additions et de soustractions [↑] et [↓]. Au final, cette formule, ce polynôme, permet de décrire n’importe quel mélange utilisant [←], [→], [↑] et [↓]. La correspondance exacte est décrite dans notre second article.

Le point essentiel, l’astuce, la trappe, c’est qu’on ne choisit pas s n’importe comment : s possède une forme assez simple, mathématiquement parlant autant que du point de vue du jeu : schématiquement elle est composée de petites colonnes sauf une qui est grande. C’est cette forme particulière qui permettra au destinataire légitime de décoder facilement le message chiffré, en appliquant un algorithme dit « glouton ». Le but sera d’éliminer les multiples de s dans un message chiffré c = s * ( g * a) +m. Informatiquement on parle d’un algorithme « glouton », car c’est un algorithme qui ne réfléchit pas trop à l’avance, il essaye à chaque étape de « manger » le plus de briques possible. Mathématiquement, pour déchiffrer un message, il s’agira de réduire le chiffre c modulo s, et nous en reparlerons plus tard.

C’est d’ailleurs ce que le joueur de Cryptris fera naturellement en jouant. En effet il sera facile pour ce joueur de réduire les colonnes du message chiffré : il ciblera une par une les colonnes à abattre en les annulant avec la grande colonne de la clef. Et comme les autres colonnes de la clef sont petites, elles n’affecteront que peu les autres colonnes du message. On peut ainsi petit à petit réduire le message, colonne par colonne, pour retrouver le message initial qui ne fait qu’une seule ligne. Vous vous souvenez ? Il n’y a que des 1, des -1 ou des 0.

La clef publique ne présente pas cet avantage. En effet en tant que combinaisons successives de la clef privée, elle a une forme autrement moins pratique : plusieurs grandes colonnes. Ainsi à chaque fois que le pirate cherche à réduire une colonne du message, il en augmente une autre, et n’arrive jamais à réduire le message à une seule ligne.

Cependant, et toujours en tant que combinaisons successives de la clef privée, il est possible avec la clef publique de chiffrer un message que la clef privée pourra ensuite défaire avec cet algorithme « glouton ».

En conséquence, voici le mode d’emploi :

• avec la clef publique je chiffre un message en l’appliquant plusieurs fois au message et en mélangeant à chaque fois,

• si je ne connais pas la suite d’opérations exactes qui a été effectuée avec la clef publique lors du chiffrage (le nombre de combinaisons possibles étant énorme), je suis incapable de déchiffrer le message avec la clef publique puisque sa forme n’est pas pratique,

• étant donné que la clef publique qui a servi à chiffrer le message n’est qu’une combinaison de la clef privée, je peux avec cette dernière déchiffrer le message facilement en appliquant l’algorithme « glouton », puisque sa forme s’y prête bien : la clef privée secrète a été construite de façon à être pratique.

On a bien compris ce qui se passe dans le jeu et pourquoi la clef privée fonctionne bien pour déchiffrer contrairement à la clef publique qui ne peut servir qu’à crypter.

Mais dans le jeu, p n’a pas une « forme pratique », contrairement à s. C’est-à-dire qu’avec s, il sera facile de nettoyer le mélange du vrai message. Précisément il va s’agir d’éliminer les multiples de s. Voyons cela.

Pour chiffrer, on dispose d’un message m, et de la clef p. On fabrique alors un chiffre c en ajoutant à m un mélange de p : c = (a * p) + m.

Et, bien que l’envoyeur ne connaisse pas s, celui qui détient la clef privée secrète sait que cela se ré-écrit :

Le chiffre c est donc égal au message plus un multiple de s. Et comme s a une forme pratique, il se trouve que l’on peut facilement éliminer les multiples de s. En fait, on a fait exprès de construire s avec une forme pratique, pour être capable de déchiffrer.

Par contre, celui qui ne connaît pas la clef privée s mais uniquement la clef publique p est obligé de rechercher un multiple de p, ce qui est bien plus difficile. En effet, la clef publique p contient plusieurs grandes colonnes, du coup l’algorithme ne fonctionnera pas : en voulant réduire l’une des colonnes on va en faire grandir d’autres.

Voici un écran de jeu. Léo -à gauche- joue contre le logiciel espion -à droite-. À gauche, Léo joue avec la clef privée, ce qui vous donne un énorme avantage face à l’ordinateur, qui joue à droite, avec la clef publique. On voit bien la clé privée avec une seule grande colonne et la clé publique avec plusieurs colonnes de tailles similaires, ce qui rend l’élimination plus difficile. Les clés sont représentées par les colonnes au milieu des parties gauches et droites. En bas les messages chiffrés en cours de déchiffrage. Au milieu les boutons permettent de manipuler la clé et les flèches correspondent aux opérations décrites dans le texte. Nous sommes à 1:30 minute de jeu et … le suspense reste entier !

C’est comme si, pour la clef privée, chaque composante était bien indépendante, perpendiculaire aux autres directions, donc que se déplacer dans une direction ne bouscule pas trop les autres. À l’inverse, pour la clef publique, les directions sont de travers, donc se déplacer dans une direction nous décale aussi dans les autres, et il faut sans cesse recommencer à réduire les colonnes, c’est-à-dire à tenter de retirer le terme a * p dans le mélange c = a * p + m.

En fait, cette histoire de directions bien perpendiculaires ou non n’est pas qu’une métaphore. C’est exactement ce qui se passe si on regarde notre problème géométriquement (voir Cryptris 2/2).

Mais alors, un attaquant ne pourrait-il pas retrouver les facteurs s et g en connaissant p ? Et bien, oui c’est possible mais terriblement long, c’est un calcul interminable ; non seulement c’est difficile lorsque s et g sont des nombres entiers mais rappelez-vous ici s et g ne sont pas vraiment des nombres (en fait ce sont des polynômes) : c’est encore plus dur à résoudre... Autant essayer tous les multiples de p...

Du coup, l’attaquant, qui ne dispose que de la clef publique, va devoir faire beaucoup, beaucoup plus de calculs que celui qui a la clef privée, et en augmentant la taille des clefs cet écart de temps de calcul est exponentiel, si bien que cela devient complètement impossible quand les clefs sont assez grandes.

À gauche le temps de jeu du joueur de Cryptris avec la clef privée. À droite le temps de jeu de l’ordinateur avec la clef publique.

Conclusion.

Voilà, c’est notre meilleure façon de vous expliquer une des méthodes de chiffrement les plus sophistiquées que nous connaissons et qui résisterait même à un algorithme sachant faire des calculs de la puissance des ordinateurs quantiques. Et cette nouvelle technique cachée derrière ce jeu proche de Tetris, la cryptographie à base de réseaux, permet des choses très surprenantes. Par exemple, dans le cas du vote électronique, on peut calculer quel vote a été choisi sur les données chiffrées, sans même avoir besoin de les déchiffrer, donc en préservant l’anonymat du votant … Étonnant non ?

Bien entendu nous n’avons pas tout dit ! Et pour en savoir plus, l’article compagnon va permettre aux plus matheux de découvrir les dessous de cette méthode ludique.

Au-delà de cet exemple pour apprendre, il faudrait un Cryptris avec des centaines de colonnes pour que cela soit vraiment incassable. Et puis on utilise d’autres ruses de mathématiciens pour fabriquer des vrais crypto-systèmes, comme de dire que 12290 et 1 c’est la même chose « modulo 12289 ». Mais toutes les idées sont là !

Que nous reste-t-il à faire ? Mais à jouer pour de vrai pardi ! C’est ICI !

Mais puis-je utiliser ce jeu pour coder de vrais messages ? Oui il suffit de cliquer ici !

En bref :

Cryptris est un jeu proposé par Inria et développé par Digital Cuisine avec le support de Cap’maths.

Le but de ce jeu est de montrer l’intérêt de la cryptographie dite asymétrique. Au travers d’une série de puzzles, le joueur de Cryptris déchiffre un message à l’aide d’une clef privée, tandis que l’ordinateur essaie de déchiffrer le même message à l’aide d’une clef publique.

La difficulté pour le joueur de Cryptris augmente de façon linéaire, alors que l’ordinateur aura de plus en plus de mal. La cryptographie protège efficacement vos données, servez-vous-en !