Cryptris 2/2. Les dessous géométriques de Cryptris : la cryptographie sur les réseaux euclidiens.

Piste rouge 15 juin 2014  - Rédigé par  Léo Ducas-Binda Voir les commentaires

Échanger des informations secrètes sur Internet. Prouver son identité numériquement. La cryptographie permet cela. Et Cryptris est un jeu vidéo qui propose d’explorer les mécanismes de la cryptographie de manière ludique ; déchiffrer un message revient à jouer à une sorte de Tetris.

Les mathématiques derrière Cryptris ont été introduites en cryptographie assez récemment et cette cryptographie nouvelle (bien que peu connue et peu appliquée par rapport à RSA) est très prometteuse ! L’objet mathématique central de cette cryptographie nouvelle est appelé « réseau euclidien » ; et comme c’est un objet de nature géométrique il n’est pas si difficile à appréhender.

Dans le premier article, nous avions expliqué que les règles du jeu Cryptris cachaient des opérations mathématiques, + et *, mais au lieu d’agir sur des nombres usuels ces opérations agissaient sur des « vecteurs » et des « polynômes ». De ces opérations émerge l’objet géométrique « réseau euclidien ». Avec lui viennent des problèmes si durs à résoudre que casser le cryptosystème en devient presque impossible.

Dans l’article compagnon, nous avons parlé de mélanges notés comme une multiplication * et de combinaisons (un bloc tombant sur un autre) notées comme une addition +. Ce ne sont évidemment pas celles des nombres usuels. Voyons ici les dessous de ces opérateurs.

L’addition : Une promenade au milieu des réseaux euclidiens.

Pour expliquer ce que nous entendons mathématiquement par « mélange » avec une valeur aléatoire, par « combinaison » entre le message et la clef publique, par « démêlage » avec la clef privée… nous allons commencer par donner une vision géométrique. Le vrai calcul implique des convolutions et additions de polynômes à coefficients entiers dans un anneau polynomial cyclotomique et… ouf ! En fait, il est possible de raconter les choses autrement. Qui plus est en images car il y a de la géométrie derrière tout cela.

Rappelons la règle du jeu : les briques de même couleur s’empilent, et celles de couleurs opposées s’annulent. Ainsi, dans le premier article, nous avions associé les briques bleu-clair à +1 et les briques bleu-azur à -1 ; de sorte qu’une pièce tombant sur une autre correspond à une addition colonne par colonne de nombres relatifs (positifs ou négatifs).

Prenons un Cryptris à deux colonnes, avec la clef s = [5, -1]. On peut voir chacun des deux nombres, 5 et -1, comme une coordonnée, et on obtient un vecteur du plan b1, tracé en bleu ci-dessus. Quelles opérations pouvons-nous faire à partir de ce code ?

  • faire tourner les coordonnées donc obtenir X*s = [-1, 5] tracé en vert ci-dessus (en dimension 2, faire tourner les coordonnées revient à les échanger). On notera cela comme une multiplication par X.
  • changer tous les signes en même temps, par exemple pour obtenir -s = [-5, 1].
  • et puis ajouter ou soustraire plein de fois ce vecteur à lui-même ou un des vecteurs transformés.

Si on fait toutes les combinaisons (un nombre infini de combinaisons possibles) et que l’on dessine tous ces points sur le plan euclidien, on obtient alors la structure régulière suivante. C’est ce que l’on appelle un « réseau euclidien ». Pour les plus calés en algèbre il s’agit formellement d’« un sous-groupe discret d’un espace euclidien ».

Tous les points de ce réseau qui s’étend à l’infini sont donc tous les codes de la forme r * s. On dit donc que ce sont des multiples de la clef privée s. Mais il faut se rappeler (voir Cryptris 1/2) que r n’est pas vraiment un nombre, c’est une combinaison de nombres r0,r1... et de rotations notées X :

r = r0 + r1 * X + r1 * X2 ...

Et la clef publique ? Eh bien c’est une autre base de ce même réseau. Elle a une autre forme, qui est « mauvaise ». On verra plus tard en quoi elle est mauvaise. Pour l’instant observons les deux bases ; en bleu celle de la clef privée s (la bonne base) et en rouge celle de la clef publique p (la mauvaise base).

Comment chiffrer un message en utilisant la clef publique ? Eh bien, on commence par voir le message m comme un petit vecteur grâce au code ternaire vu dans le premier article. Le message m est donc un petit vecteur, avec de petites coordonnées (des -1, des 0 et des +1). Géométriquement, il est dans le carré rose comme illustré ci-dessous. Pour chiffrer ce message m on va lui ajouter un point du réseau choisi au hasard à l’aide de la mauvaise base p ; ma clef publique. On choisit ainsi un r aléatoire pour construire le point orange r * p dans le réseau. Enfin on ajoute le message m à ce vecteur ce qui nous mène au point mauve m + r * p ; cela sera notre message chiffré :

Maintenant qu’on sait chiffrer avec la clef publique, il faut trouver comment déchiffrer avec la clef privée s. On veut se servir de la bonne base s pour séparer le message m du point du réseau qui le cache a * p. Pour cela on se sert d’une base pour découper l’espace en boîtes : on dessine un pavage de l’espace avec des parallélépipèdes. On dit que la clef privée s est une « bonne base » car elle correspond à un repère presque orthogonal du réseau : les carreaux du pavage sont presque carrés. On peut déterminer facilement (grâce à l’algorithme de Babai, voir plus bas) dans quelle boite du réseau nous sommes, et donc retirer le bruit du message. En effet, sur l’image suivante, à gauche, on voit que le message chiffré (en violet) a pour centre le point orange : c’est la même valeur r * p que lors du chiffrement.

L’essentiel pour que le crypto-système fonctionne, c’est que p et s engendrent le même réseau, c’est-à-dire que l’ensemble des combinaisons a * p soit le même ensemble que les combinaisons b * s [1]. Ainsi, on peut défaire avec s tout ce qui a été fait avec p : on peut déchiffrer en connaissant la clef privée s.

Par contre, si on utilise la clef publique p pour déchiffrer, elle correspond à un mauvais repère du réseau, représenté en rouge ci-dessus, à droite. Il est mauvais car les carreaux sont très longs et fins, et cette fois-ci, si l’on prend le centre du carreau, eh bien, on ne retrouve plus valeur de r * p mais une autre valeur t * p que lors du chiffrement : on se trompe en essayant de déchiffrer. CQFD ! Tout le monde, connaissant p peut chiffrer, mais seul celui qui connaît s peut déchiffrer correctement !

Mais pourquoi les boîtes associées à s sont-elles presque carrées et pas celles de p ?

C’est parce que nous avons choisi s ainsi ! Souvenez-vous (Cryptris 1/2), vu sous forme de briques, s avait une grande colonne (disons la première) alors que les autres sont petites. Géométriquement cela veut dire que s est un vecteur presque horizontal (sa coordonnée x est grande et sa coordonnée y est petite). Sa rotation x*s, elle, sera presque verticale. Par contre p est un mélange aléatoire de s, ce qui va casser ces belles facilités géométriques.

Ne pourrait-on pas utiliser un algorithme d’orthogonalisation comme celui de Gram-Schmidt pour rendre les boîtes carrées ?

Malheureusement (ou heureusement pour faire de la cryptographie !), non. Comme dans les espaces vectoriels, on peut dans un réseau faire des additions de deux vecteurs, ou multiplier un vecteur par un nombre entier. Par contre, dans les réseaux on ne peux pas faire de division (sinon on sort du réseau et le résultat ne serait plus une base de ce réseau, mais d’un autre réseau) ; et l’algorithme de Gram-Schmidt ou tout autre algorithme d’orthogonalisation nécessite de faire des divisions.

La clef secrète : une boussole pour retrouver son chemin.

Une petite seconde, c’est bien joli de dessiner tous ces pavages, mais comment fait-on pour en retrouver le centre ? En effet, en dimension 2 il suffit de dessiner un peu et on s’en sort, mais pour un jeu avec plus de colonnes, comment faire ? C’est László Babai, un mathématicien, qui a inventé la meilleure solution. Son algorithme requiert des calculs un peu compliqués [2] (pour les plus calés d’entre vous : orthogonalisation de Gram-Schmidt, et inversion de système triangulaire). Nous utilisons une version très simplifiée, particulièrement adaptée à Cryptris, c’est l’algorithme « glouton » dont on parlait déjà ici.

L’algorithme « glouton » s’énonce très simplement lorsque la clef a une forme pratique, c’est-à-dire que l’une de ses colonnes est beaucoup plus grande que toutes les autres. On utilise cette grande colonne de la clef secrète s, pour réduire la plus haute colonne du message chiffré et on recommence jusqu’à ce que le message soit petit. Un exemple avec une clef privée s = [-5,1]

C’est en fait la stratégie qu’adopte généralement le joueur du jeu Cryptris.

Pourquoi cela finit toujours par marcher ?

Ainsi, à chaque étape on fait beaucoup décroître une colonne, mais on augmente en général les autres d’un tout petit peu seulement. Comme on en enlève plus qu’on en rajoute à chaque étape, on finira bien par avoir enlevé tout ce qu’il est possible d’enlever. Géométriquement, chaque étape nous rapproche de l’orgine O, jusqu’à ce qu’on ait retrouvé le message m.

Par contre, avec une mauvaise base, comme la clef publique p, à chaque fois que l’on essaie de faire décroître une colonne, on augmente beaucoup les autres : on ne se rapproche pas forcément de l’origine. Donc on ne s’en sort pas. Et même en utilisant le vrai algorithme de Babai, comme illustré plus haut avec les pavages rouges, on ne finira pas très loin du vrai message, mais on ne le trouvera pas.

Géométriquement, la différence entre la bonne et la mauvaise base, c’est que le carré rose (l’ensemble des messages possibles) est entièrement à l’intérieur du parallélépipède de Babai pour une bonne base. Par contre il débordera si la base est mauvaise.

Rotation et multiplication de polynômes.

Nous avons presque fait le tour de ce crypto-système. Il reste un seul mystère : pourquoi utilise-t-on le symbole de multiplication lorsqu’on fait un mélange comme p = g * s ?

En effet ce ne sont pas des nombres, mais des polynômes. Vous savez, un polynôme c’est une espèce de formule comme

p = 5 X3 -4 X2 + 5 X + 4

X n’a pas de valeur précise : c’est une « variable muette ». Chaque coefficient va correspondre à une colonne de Cryptris, ici les colonnes sont 5, -4, 5, 4 (c’est-à-dire 5 bleu clair, 4 bleu azur, 5 bleu clair, et 4 bleu clair). Si on ajoute deux polynômes, il est facile de voir que cela correspond à une somme coefficient par coefficient. Ainsi on peut multiplier un polynôme par un nombre par exemple :

3 * p = 15 X3 -12 X2 + 15 X + 12

Rien de bien neuf jusqu’ici, mais que se passe-t-il si l’on multiplie un polynôme par X ?

X * p = 5 X4 -4 X3 + 5 X2 + 4 X

Cette fois-ci, on a décalé tous les coefficients d’un cran vers la gauche ! Exactement comme lorsqu’on multiplie un nombre par 10, cela décale tous ses chiffres vers la gauche ! Il ne manque plus qu’une petite ruse de mathématicien : vu que X n’a pas vraiment de valeur on peut ajouter des contraintes sur X. Ici, si on ajoute l’équation X 4 =1, alors on va obtenir une vraie rotation des coefficients ! Pour être un peu plus formel, cela consiste à faire des calculs « modulo X 4 -1 » :

X * p = -4 X3 + 5 X2 + 4 X + 5 mod X 4 -1

puisque 5 X4 = 5.

Et pour tourner à droite ? Eh bien on va faire une division par X ! Et si on ne veut pas diviser, il suffit de se rendre compte que tourner une fois à droite, c’est pareil que de tourner trois fois à gauche... Autrement dit - « modulo X 4 -1 » - diviser par X c’est pareil que de multiplier par X3. Comment cela ? Une division serait une multiplication ? Oui, d’accord, tout ceci est un peu troublant à première vue, mais rappelez-vous, notre exemple enfantin du début de l’article précédent : diviser par 5 c’est presque comme multiplier par 2.

Un exemple de calcul de paire de clef privée / clef publique

Revoyons le mélange de clef, c’est-à-dire la méthode qui consiste à fabriquer une clef publique à partir de la clef privée. Partons de la clef publique (on remarquera qu’elle n’a qu’un seul grand coefficient) :

s = 6 X3 - X2 + 1 mod X 4 -1

On va faire comme mélange la suite de commande [↓] [←][←] [↓][↓] [→] [↑] [↓]. En résumé, si s représente la clef initiale, t la clef temporaire manipulée en haut, et h la clef manipulée en bas, on a :

  • [↓] fait tomber la clef privée sur la clef privée ( p devient p+t )
  • [←] [→] font tourner la clef privée ([←] t devient X * t mod X4 -1 et dans l’autre sens [→], t devient X3 * t’ mod X4 -1 )
  • [↑] inverse les couleurs ( t devient -t ).

Au début on a h = 0 et t = f.

[↓] h := 0 + t = s
[←][←] t := X * X * s = X2 * s
[↓][↓] p := p + t + t = s + 2 X2 * s = (2X2 + 1) * s
[→] t := X3 * t = X5 * s = X * s
[↑] t := - t = -X * s
[↓] p := p + t = (2 X2 + 1) * s - X * s = (2 X2 - X + 1) * s

Les plus courageux d’entre vous pourront vérifier que le résultat p = (2 X2 - X + 1) * s vaut :

p = 7 X3 + X2 + 11 X - 7 mod X4 -1

Alors, Cryptris ? Vraiment incassable ?

Cryptris est inspiré par des techniques récentes en cryptographie, techniques fondées sur les réseaux euclidiens. Les réseaux euclidiens sont connus pour fournir des problèmes très durs à résoudre comme le problème du plus court vecteur. Certains de ces problèmes sont tellement durs que si on savait les résoudre on pourrait résoudre tout un tas d’autres problèmes ; on dit que ce sont des problèmes NP-complets.

La cryptographie à base de réseau, la vraie, est aussi dure à casser que des variantes de ces problèmes de réseau. Bien qu’elle ne soit pas parfaitement NP-complète c’est la meilleure cryptographie dans le sens où l’on comprend à peu près pourquoi elle est difficile à casser. Certains experts prédisent qu’elle finira par remplacer la cryptographie traditionnelle dans un futur proche.

Mais Cryptris alors ? Cryptris est une « approximation » de ces techniques ; il y a dans Cryptris les idées clefs pour construire un vrai cryptosystème, mais il manque de nombreux détails pour devenir véritablement incassable. Ne serait-ce que simplement la taille des clefs (la dimension de réseaux). Dans Cryptris, nous jouons avec des réseaux de dimension 8 à 16 ; les cryptographes travaillent avec au moins 256 dimensions ! Cependant, même en grande dimension, Cryptris reste imparfait...

Conclusion.

Voilà, complètement expliquée maintenant, cette classe de méthodes de chiffrage parmi les plus sophistiquées que nous connaissons et qui résisteraient même aux algorithmes quantiques que nous connaissons à ce jour. La cryptographie à base de réseaux permet des choses insensées comme calculer sur des données sans avoir à les déchiffrer, c’est ce qu’on appelle le chiffrement Homomorphe !

Eh ! Mais où es-tu chère lectrice ou cher lecteur ? Ah je vois … tu es parti-e jouer. Rendez-vous dans le jeu alors :).


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

Post-scriptum :

Les auteurs souhaitent remercier Nicolas Juillet, Jill-Jênn Vie et Chillali Abdelhakim pour leur travail de relecture et leurs remarques judicieuses.

Notes

[1Dans Cryptris ce n’est pas tout à fait vrai ; le réseau engendré par p est un sous-ensemble du réseau engendré par s. Ce n’est pas idéal d’un point de vue cryptographique, mais cela nous simplifie bien la vie !

[2Une version simplifiée de son algorithme est expliquée dans ces diapositives, section 2.

Partager cet article

Pour citer cet article :

Léo Ducas-Binda — «Cryptris 2/2. Les dessous géométriques de Cryptris : la cryptographie sur les réseaux euclidiens.» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

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