Un exemple de cryptographie asymétrique : Merkle-Hellman
Hey hey !
Comme promis dans les précédents articles de la série sur la sécurisation de ses communications électroniques, aujourd’hui on va faire un peu de maths. Et voir à quoi ressemble un algorithme de chiffrement/signature « pour de vrai » ! On se lance ? 🙂
Je ne vous fais donc pas de rappel sur ce qu’est la cryptographie asymétrique et vous renvoie à la partie 1 ci-dessus.
Pour se mettre en jambes (et vous donner envie ?), on va causer du cryptosystème de Merkle-Hellman. Ça ne nous rajeunit pas, et on remonte à 1978 : Ralph Merkle et son pote Martin Hellman mettent au point l’algorithme qui portera leurs noms. C’est aussi en 1978, pour mémoire, qu’a été élaboré l’algorithme RSA (breveté par le MIT en 1983).
Alors oui, Merkle-Hellman a déjà été « cassé », mais je l’ai choisi pour vous donner un premier aperçu, parce qu’il est plutôt simple (comparé à RSA par exemple, bien plus performant, mais demandant des notions mathématiques plus poussées pour le comprendre — or, mon but est de présenter le mécanisme au plus grand nombre !).
Le « problème du sac à dos »
Rien à voir avec Dora et son sac (quoique… elle pourrait se poser la question !), il s’agit en vérité d’un problème connu de tous ceux qui ont mis le bout de leur nez (par ailleurs humide en ces temps frais) dans un quelconque libre/cours d’algorithmique. On appelle ça de l’ « optimisation combinatoire » (hou les vilains mots).
Le problème n’est pas si méchant que ça à comprendre. Vous prenez un sac à dos vide, et un tas d’objets ayant chacun une masse (en kilogrammes) et une valeur monétaire (en euros, allez). Vous avez à résoudre ce problème : mon sac supporte 15kg, quels objets y placer pour avoir le maximum de valeur dans le sac sans pour autant dépasser la masse maximale ? Formulé comme ça c’est simple, mais allez résoudre la chose.
Des extensions du problème du sac à dos ont donné naissance à plusieurs algorithmes de cryptographie asymétrique. Bon, ils ont tous été cassés, jusqu’à maintenant…
On ne sait pas vraiment donner d’algorithme de résolution du problème du sac à dos (souvent élément d’un problème plus complexe). Dans certains cas, dont celui qui nous intéresse, c’est cependant possible. Prenons donc une suite « super-croissante », qui a entre autres particularités le fait que chacun de ses éléments est supérieur à la somme des précédents. Exemple des plus simples : nos pièces de monnaie. On a donc : 1ct, 2cts, 5cts, 10cts, 20cts, 50cts, 1€ et 2€.
C’est une suite super-croissante : quelle que soit la pièce que vous choisissez, si vous additionnez celles qui sont plus petites, ça fait toujours moins que celle que vous avez choisie. Allez, on prend la 50cts. On additionne les pièces inférieures : 1+2+5+10+20=38cts. 38, c’est bien plus petit que 50. Et même si vous prenez un billet de 5€ (bande de riches 😀 ), la somme des pièces ne ferait que 3,88€. C’est valable aussi. 😉
Et donc, avec cette suite super-croissante, le problème du sac à dos est assez simple à résoudre. Tant qu’il n’y a pas trop d’éléments non plus… Appliquons ça à la cryptographie, maintenant !
Cryptosystème de Merkle-Hellman
Génération des clés publique/privée
1. Commençons par le début : il nous faut une suite super-croissante. On va prendre :
$latex k=\{1,2,4,8,16,32,64,128\}&s=2$
2. Il nous faut en plus de cela un entier p au pif, tant qu’il est supérieur à la somme des éléments de la suite k, c’est-à-dire :
$latex p>\sum^{n}_{i=1} k_i&s=2$
On va prendre p=291 . Me demandez pas pourquoi ! 
3. Il nous faut encore un autre entier a aléatoire, mais pas totalement au hasard non plus : il faut que a et p soient premiers entre eux (rappel : des nombres premiers entre eux n’ont que 1 comme diviseur commun… on les appelle aussi « copremiers »). Pourquoi ? Pour permettre l’unicité du chiffrement qui sera réalisé ensuite (application injective : en gros, pour qu’à une valeur d’entrée corresponde une seule et unique valeur de sortie, et que cette valeur de sortie n’admette pour antécédent que la valeur d’entrée originale). Prenons a=85 .
4. Calculons maintenant la clé publique : elle correspond à une suite b qui comprend autant d’éléments que k, et chacun de ses composants est calculé comme suit :
$latex b_i=k_i \cdot a \pmod p&s=2$
Pour faire simple : on prend chacun des éléments de la suite k du début, on le multiplie par a modulo p, et ça donne l’élément correspondant de la suite b.
Avec un p’tit coup de calculatrice, on trouve :
$latex b=\{ 85,170,49,98,196,101,202,113\}&s=2$
On obtient alors la clé publique (b) et la clé privée (le triplet k, p, a).
Chiffrement d’un message
Prenons un mot au hasard : ‘max’, qui nous donne donc 3 mots binaires de 8 bits (un mot par lettre), à savoir 01101101 01100001 01111000.
Chaque mot comporte 8 bits. Appelons le mot entier m, et les 8 chiffres (des 0 ou des 1) qui le composent sont dans l’ordre :
$latex m=(m_1,\dots , m_n)&s=2$
Le mot chiffré devient alors :
$latex c=\sum_{i=1}^{n} b_im_i&s=2$
Et une fois qu’on applique ça, on se retrouve avec notre résultat chiffré. Mathématiquement, ça revient à multiplier deux matrices :
- une première, qui contient notre clé publique ;
- une seconde, qui contient nos mots binaires (notez qu’elle doit être transposée pour pouvoir faire l’opération).
$latex \begin{pmatrix} 85 & 170 & 49 & 98 & 196 & 101 & 202 & 113 \end{pmatrix} \cdot \begin{pmatrix} 0 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 0 \end{pmatrix}$
Histoire de faire vite et bien, et par méga flemme de sortir une feuille et un crayon, on va balancer tout ça dans Maxima (un logiciel de calcul formel), et la réponse arrive de suite :
C’est assez transparent, mais on sait jamais :
- en %i1 : je lui donne la matrice m (3 lignes, 8 colonnes) qui contient nos mots binaires (un mot par ligne) ;
- en %i2 : j’entre la clé publique (matrice à 1 ligne et 8 colonnes) ;
- en %i3 : je demande la multiplication des deux matrices, en transposant la matrice m (si vous connaissez un peu les matrices, vous savez que sinon je ne peux pas faire la multiplication en question ; rien que pour vous embêter j’ai demandé à maxima de pas la transposer, il a vomi un « MULTIPLYMATRICES: attempt to multiply nonconformable matrices. » bien assez explicite 😀 )
Notre mot ‘max’ chiffré est donc : 629 332 513 . Notez qu’on pourrait aussi passer à une écriture en modulo 291.
Déchiffrement d’un message
Ben oui, parce que chiffrer c’est bien, pouvoir relire, c’est mieux 😉
Pour déchiffrer le message, on part de a suite c telle que :
$latex c=\{ 629, 332, 513 \}&s=2$
et on doit retrouver notre m de départ. Pour cela, on a :
$latex c=\sum_{i=1}^{n}b_im_i&s=2$
En faisant le lien avec la partie où on a généré les clés, on remarque que :
$latex a^{-1}b_i \equiv a^{-1}ak_i \equiv k_i \pmod p&s=2$
Pour déchiffrer le message, il faut donc déjà calculer a-1 avec notre a=85 et p=291. On cherche en soi l’inverse de 85 modulo 291. Un coup de baguette magique plus tard (en réalité, un coup d’exponentiation rapide), on a notre a-1=202 .
En calculant a-1c on obtient :
$latex a^{-1}c \equiv \begin{pmatrix} 182 & 134 & 30 \end{pmatrix} \pmod 291&s=2$
Finalement :
- 182 = 128 + 32 + 16 + 4 + 2 –> (01101101) –> m
- 134 = 128 + 4 + 2 –> (01100001) –> a
- 30 = 16 + 8 + 4 + 2 –> (01111000) –> x
Et on constate, oh grande magie, qu’on a bien retrouvé le ‘max’ de départ ! 🙂
Pour finir…
Déjà, ça m’a (vraiment) bien plu de vous écrire ce petit article. Le sujet m’intéresse, la cryptographie est une facette obscure pour « monsieur-madame tout l’monde » alors que dans les faits elle est utilisée de plus en plus souvent, et vulgariser les connaissances acquises un peu partout m’a paru important pour essayer de vous intéresser vous aussi à cette problématique.
C’était un exemple assez rapide, qui ne demandait pas trop de notions mathématiques (et même sans tout comprendre, je pense que le manuel d’un logiciel comme Maxima suffit à reproduire les étapes avec d’autres valeurs, d’autres suites et clés…).
Il y a probablement des améliorations à apporter, et cela peut amener des questions : je suis comme toujours prêt à y répondre, et à améliorer ce qui peut l’être.
Et bien sûr, j’espère vous avoir intéressés un peu, et vous avoir permis d’entrevoir une petite partie des rouages des algorithmes utilisés. Ils ont tous leurs propres méthodes de calcul et pré-requis, mais au fond, Merkle-Hellman vous a permis de voir toute l’importance de garder votre clé privée… privée. C’est elle qui permet de générer la clé publique, et de déchiffrer ce que vous pond la clé publique en question. Tout est lié !
Teasing : le prochain article sur ce thème parlera des fonctions de hachage pour la signature électronique, le contrôle d’intégrité…
