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 b₁, 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 r₀,r₁... et de rotations notées X:

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 !

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.

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

où 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 :

Rien de bien neuf jusqu’ici, mais que se passe-t-il si l’on multiplie un polynôme par 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 ⁴ =1, alors on va obtenir une vraie rotation des coefficients ! Pour être un peu plus formel, cela consiste à faire des calculs « modulo X ⁴ -1 » :

puisque 5 X⁴ = 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 ⁴ -1 » - diviser par X c’est pareil que de multiplier par X³. 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.

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.