Cryptris 1/2. Comprendre une des techniques les plus sophistiquées de cryptographie en... jouant à Tetris.

Piste rouge 15 juin 2014  - Ecrit par  Anthony Teston, Léo Ducas-Binda, Mathieu Jouhet, Thierry Viéville Voir les commentaires (3)

Échanger des informations secrètes sur Internet ? C’est possible. Mais il y a toujours un risque qu’elles soient interceptées. C’est là que les mathématiques viennent à la rescousse. Et la méthode des « réseaux euclidiens » promet d’être encore plus efficace que les méthodes standard. De plus, il se trouve qu’on peut la comprendre en jouant à un jeu vidéo aux allures de Tetris, qui s’appelle « Cryptris ».

É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 :

Symbole pour le représenter Dans notre exemple
Le message à chiffrer m comme « message » « 123 »
Un aléa à ajouter pour cacher le message a comme « aléa » « 45 »
Une clef publique pour chiffrer le message p comme « publique » « 5 »
Une clef secrète pour le déchiffrer s comme « secret » « 2 »
Le code envoyé après le chiffrage c comme code « 61725 »

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 34 = 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 28 =2*2*2*2*2*2*2*2 = 256 caractères.

Caractère à coder Code ternaire Caractère à coder Code ternaire
0 0 0 0 G 1 -1 1 1
0 1 0 0 0 H -1 -1 1 1
1 -1 0 0 0 I 0 0 -1 1
2 0 1 0 0 J 1 0 -1 1
3 1 1 0 0 K -1 0 -1 1
4 -1 1 0 0 L 0 1 -1 1
5 0 -1 0 0 M 1 1 -1 1
6 1 -1 0 0 N -1 1 -1 1
7 -1 -1 0 0 O 0 -1 -1 1
8 0 0 1 0 P 1 -1 -1 1
9 1 0 1 0 Q -1 -1 -1 1
Etc …

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 :

p + m = t
[-1, 6, 8, 0, -2, -1, 7, 7] + [ 0, -1, -1, 1, -1, 0, -1, 1 ] = [-1, 5, 7, 1, -3, -1, 6, 8].

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 = (a * p) + m,

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

p = g0 * s + g1 * X * s + g2 * X2 * s + … .

Dans cette formule X * s, X2 * 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 g0, g1, g2 … sont des nombres usuels (par exemple g0=2, g1=-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 :

c = (a * p) + m
= (a *g * s) + m

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 !

Post-scriptum :

Les auteurs sont particulièrement reconnaissants envers Nicolas Juillet, FlavienK, Emmanuel Beffara, Massy Soedirman et Jill Jênn-Vie pour leur précieux travail de relecture minutieuse qui a permis d’améliorer le texte initial ; un grand merci pour ses encouragements à Chillali Abdelhakim.

Article édité par Didier Auroux

Notes

[1Sur Internet, on peut considérer que nous sommes sur une « place publique », puisque les paquets de données circulent de machine en machine. De ce fait, il y a toujours la possibilité de les examiner, donc de tenter de les espionner. Pire : les adresses de départ et d’arrivée des paquets de données, indispensables pour acheminer le paquet et la probable réponse, ne peuvent être que données en clair. Ce qu’il faut réaliser c’est que c’est l’architecture même de ce réseau des réseaux qui conduit à être dans un espace global où la circulation des paquets est forcément visible.

[2C’est la plus sournoise des attaques, dites de l’homme du milieu, que de tenter de faire croire à quelqu’un que nous sommes une personne proche, ou pour un site Web de ressembler à s’y méprendre à un site de confiance. Ainsi un site comme « twetter.com » a-t-il pu piéger beaucoup d’utilisateurs du vrai site « twitter.com » en se rendant « jumeau » du site de départ.

[3On peut se débrouiller pour casser ce simple système sans divisions.

[4C’est une somme de vecteurs en fait dans un espace dont la dimension est la taille du message, donc bien plus que le plan de dimension 2. Ce message est aussi un polynôme comme ce sera expliqué dans l’article suivant.

Partager cet article

Pour citer cet article :

Anthony Teston, Léo Ducas-Binda, Mathieu Jouhet, Thierry Viéville — «Cryptris 1/2. Comprendre une des techniques les plus sophistiquées de cryptographie en... jouant à Tetris.» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

  • Cryptris 1/2. Comprendre une des techniques les plus sophistiquées de cryptographie en... jouant à Tetris.

    le 7 juillet 2014 à 19:39, par bayéma

    il y a le problème mathématique, et il y a le problème social du secret. quels secrets avons-nous à cacher ? l’apparente infinité des secrets « valables » se rangent dans trois catégories seulement : les secrets financiers, les secrets militaires et les secrets sexuels. on peut plus ou moins ergoter sur le degré. donc, l’histoire nous enseigne que le secret est toujours dévoilé à un moment ou à un autre. l’intérêt est donc que ce ne soit pas dévoilé de « notre vivant » ! mais pour cela il faut considérer que tout ne se vend pas ou que tout ne s’achète pas ; et c’est la où le bâts blesse : un possesseur de clé privée peut la vendre à un bon acheteur si celui-ci calcule bien le coût de la clé, càd combien elle rapporte une fois utilisée. il y a le problème mathématique, et il y a le problème...
    josef bayéma, plasticien, guadeloupe.

    Répondre à ce message
  • Cryptris 1/2. Comprendre une des techniques les plus sophistiquées de cryptographie en... jouant à Tetris.

    le 8 juillet 2014 à 20:15, par Léo Ducas-Binda

    Merci Josef pour votre commentaire, qui va au delà des questions mathématiques.

    La cryptographie soulève en effet des questions d’ordre sociétal. Si quelqu’un souhaite vendre ses secrets, la cryptographie n’y pourra rien. La cryptographie garantie seulement que cette cette décision n’appartiennent qu’a lui : je peux bien faire ce que je veux de mes secrets, mais ne peux ni decrypter, ni donc vendre les secrets d’autruis.

    Ainsi, il faut voir la cryptographie comme un outils de préservation de la vie privée. Il y a des secrets « sensibles » que peuvent vouloir protéger des organisations ou des gouvernements, mais on peut aussi utiliser la cryptographie pour lutter contre « la surveillance de masse ». Et c’est plutôt la que le bat blesse : les organisations sont tout a fait capable de proteger leur secrets, par contre, nous, les individus, les internautes ne sommes pas armés pour protéger notre vie privée.

    Mais qu’avons nous a cacher, nous individus ? Le bon sens voudrait que s’il on a rien a cacher, alors on a rien a craindre... Cet argument est en fait très dangereux comme discuté par exemple ici :

    http://pixellibre.net/2013/08/traduction-vous-navez-peut-etre-rien-a-cacher-mais-vous-avez-quelque-chose-a-craindre/

    C’est ainsi qu’il me semble essentielle que les technologie cryptographique deviennent plus accessibles a tous, autant l’information sur sa bonne utilisation, que les logiciels permettant de s’en servir.

    Répondre à ce message
    • Cryptris 1/2. Comprendre une des techniques les plus sophistiquées de cryptographie en... jouant à Tetris.

      le 9 juillet 2014 à 03:06, par bayéma

      merci léo de votre réponse.

      1°- la mathématique cryptographique : le développement même de la science montre que ces techniques (que vous nous avez si bien expliquées que j’ai tout compris. j’ai lu I et II), seront nécessairement dépassées, par vous-mêmes d’ailleurs ou par d’autres, ce n’est qu’une question d’argent, de temps et d’intérêt théorique, et donc la compétition entre mathématicien.ne.s est d’ores et déjà lancée. il n’est d’ailleurs même pas sûr que ne se nicherait pas actuellement, dans d’autres domaines de la science, des éléments théoriques qui n’attendent que leur visibilité. je pense que c’est un phénomène naturel de l’évolution.
      ce qui m’a intéressé dans votre article (I et II), c’est l’idée qu’il y aurait, épistémologiquement, une rupture entre l’« ancienne » cryptographie et celle des réseaux euclidiens. et c’est là où j’aimerais que vous nous appreniez plus de choses.
      2°- la socialité et la cryptographie : je suis allé sur le site pixellibre et je compte y retourner pour participer aux discussions car, en tant que plasticien, forcément individualiste, ces questions m’intéressent. je ne vais pas m’étendre là-dessus aujourd’hui mais j’avancerais deux idées fondamentales : a) ce ne sont pas les gouvernements qui sont responsables de quoi que ce soit, mais les peuples qui les soutiennent. quand les roumains ont décidé de se débarrasser des ceaucescu, ça n’a pas demandé 2 semaines ! quand les portugais ont cessé d’être fascistes, le salazarisme a disparu très vite ! dans un quelconque petit village français, ce n’est pas le gouvernement qui vous surveille mais vos voisin.e.s. etc. abolir la surveillance, c’est tout simplement changer les peuples ! vaste programme ! b) l’histoire montre qu’elle fait apparaître les monstres pas n’importe comment et pas pour toujours.
      3°- la vie privée : il faut, comme en mathématique, ne pas sombrer dans la confusion. ou bien on parle de surveillance de masse ou bien on parle de vie privée ; ce n’est pas la même chose : en tant qu’être socialisé je suis TOUJOURS sous surveillance : toucher mon salaire, vouloir guérir, voyager, etc. TOUT LE MONDE y est habitué (avec plus ou moins d’irritation, certes). quant à la vie privée, nous sommes trop nombreu.se.s sur terre, c’est quasi l’infini pour le fou qui voudrait s’y amuser.
      le fait pratique c’est que tout le monde doit vivre, les cryptographes comme tout le monde.
      alors pas besoin de se prendre la tête et amusons-nous en faisant des mathématiques, comme quand on était gamin.e et qu’on s’envoyait...des messages secrets !
      josef bayéma.

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM