Le chiffre de Merkle-HellmanLe premier cryptosystème à clef publique, qui fut proposé par Ralph Merkle (photo de gauche) et Martin Hellman en 1978, est basé sur le problème du sac à dos (Knapsack problem en anglais). Il n'est plus utilisé actuellement puisque ce chiffre, ainsi que de nombreuses variantes, a été cassé au début des années 80 par Adi Shamir.
Le problème du sac à dos consiste à empiler des objets dans un sac, de manière à atteindre (si possible) un poids total fixé. Plus formellement, étant donnés des poids entiers P1, ..., Pn et un but T, il s'agit de trouver b1, ..., bn, valant 0 ou 1, tels que
Si la suite des poids Pk est supercroissante (chaque poids est strictement supérieur à la somme de tous les précédents), alors il existe une méthode de résolution simple (algorithme glouton):
|
Algorithme glouton
Pour i = n à 1 faire |
Vérifiez qu'avec la suite de poids supercroissante P1=2, P2=3, P3=6, P4=12 et T=15 on obtient la solution b1=0, b2=1, b3=0, b4=1.
Au contraire, si la suite des poids n'est pas supercroissante, le seul algorithme connu consiste à essayer successivement toutes les solutions (b1, b2, ..., bn) possibles. Si la suite est suffisamment longue, c'est un algorithme impraticable.
C'est un chiffre à clef publique, basé sur la difficulté de résoudre le problème du sac à dos avec une suite de poids non supercroissante. On part de l'observation suivante:
| Le problème du sac à dos est homogène : on ne change pas les solutions en multipliant (ou en divisant) tous les poids Pi et le but T par un même entier p. |
Les multiplications peuvent être effectuées modulo un entier m. Alors, même si la suite de poids initiale est supercroissante, la nouvelle suite ainsi obtenue ne le sera en général pas. En pratique, on choisit m supérieur à la somme des poids initiaux.
Exemple. On part de la suite supercroissante 1, 3, 6. Tous les calculs sont faits modulo 12. En multipliant tous les poids par 7 on obtient la suite non supercroissante 7, 9, 6. Grâce à la propriété d'homogénéité, on voit que la même solution (b1, b2, b3) permet de réaliser le but T avec les poids 1, 3, 6 et le but Tx7 avec les poids 7, 9, 6. Le tableau ci-dessous donne la correspondance entre les buts et les solutions:
| T | Tx7 | b1, b2, b3 |
| 0 | 0 | 0, 0, 0 |
| 1 | 7 | 1, 0, 0 |
| 3 | 9 | 0, 1, 0 |
| 4 | 4 | 1, 1, 0 |
| 6 | 6 | 0, 0, 1 |
| 7 | 1 | 1, 0, 1 |
| 9 | 3 | 0, 1, 1 |
| 10 | 10 | 1, 1, 1 |
Pour chiffrer un bloc de k bits, on calcule simplement le poids T résultant du sac. Pour garantir que le déchiffrement avec la même clef est impossible, on chiffre avec la suite non supercroissante.
Pour déchiffrer, on doit déterminer les poids dont la somme réalise le but T. L'idée consiste à revenir à la suite supercroissante initiale, sans changer la solution. Il suffit pour cela de diviser tous les poids et le but T par p.
La suite non supercroissante constitue la clef publique. La suite supercroissante initiale, avec p et m, forment la clef privée.
La clef privée de Bob est [1, 3, 6], avec p = 7 et m = 12.
Avec la clef publique [7, 9, 6] fournie par Bob, Alice chiffre ainsi la chaîne 101: T = 7x1 + 9x0 + 6x1 = 13. Elle envoie donc le message "13" à Bob.
Pour déchiffrer le message, Bob utilise sa clef privée (notez que 7 est son propre inverse modulo 12), et il applique l'algorithme glouton. Il obtient:
Plus généralement, pour que p soit inversible modulo m, il suffit de le choisir premier avec m.
Il est important de noter qu'un texte chiffré avec la clef privée ne pourra pas être déchiffré avec la clef publique, puisqu'elle n'est pas supercroissante: les deux clefs du chiffre de Merkle-Hellman ne peuvent pas être permutées.
| a | 00000 | g | 00110 | m | 01100 | s | 10010 | y | 11000 | ||||
| b | 00001 | h | 00111 | n | 01101 | t | 10011 | z | 11001 | ||||
| c | 00010 | i | 01000 | o | 01110 | u | 10100 | , | 11010 | ||||
| d | 00011 | j | 01001 | p | 01111 | v | 10101 | . | 11011 | ||||
| e | 00100 | k | 01010 | q | 10000 | w | 10110 | ? | 11100 | ||||
| f | 00101 | l | 01011 | r | 10001 | x | 10111 | 11101 |
La clef privée de Bob est [3, 4, 9, 19, 38, 77], avec p = 27 et m = 155. Il peut maintenant calculer la clef publique avec laquelle Alice chiffrera son message: [3x27 (mod 155), 4x27 (mod 155), 9x27 (mod 155), 19x27 (mod 155), 38x27 (mod 155), 77x27 (mod 155)], ce qui donne [81, 108, 88, 48, 96, 64].
Alice veut transmettre le mot "baby" à Bob. Elle devra donc, en se référant à la table ci-dessus, chiffrer la chaîne 00001 00000 00001 11000. Comme la clef publique de Bob comporte 6 nombres, elle devra ensuite regrouper ces bits par paquets de 6, et au besoin ajouter des bits aléatoires pour obtenir un nombre de bits multiple le 6: 000010 000000 001110 001101
Le premier bloc de 6 bits sera chiffré :
81x0 + 108x0 + 88x0 + 48x0 + 96x1 + 64x0 = 96.
Le deuxième bloc de 6 bits sera chiffré :
81x0 + 108x0 + 88x0 + 48x0 + 96x0 + 64x0 = 0.
Le troisième bloc de 6 bits sera chiffré :
81x0 + 108x0 + 88x1 + 48x1 + 96x1 + 64x0 = 232.
Le quatrième bloc de 6 bits sera chiffré :
81x0 + 108x0 + 88x1 + 48x1 + 96x0 + 64x1 = 200.
Le message chiffré est donc: [96, 0, 232, 200]
Pour déchiffrer, Bob calcule d'abord l'inverse modulo 155 de 27, qui vaut 23. Il utilise ensuite sa clef privée et applique l'algorithme glouton. Il obtient alors:
Le message déchiffré est donc [000010, 000000, 001110, 001101], ce qui est bien le message qu'avait envoyé Alice.
Pour retrouver le mot, Bob n'a plus qu'à regrouper les bits par paquets de 5 et consulter le tableau de conversion.
Il est important que le nombre de bits par paquet soit différent de la longueur de la clef. En effet, si ce n'était pas le cas, on pourrait attaquer le texte chiffré par une analyse des fréquences, car chaque lettre serait chiffrée par le même nombre.
Il est clair que plus la clef est longue, plus le message sera difficile à décrypter. Dans la pratique, on utilise au moins 250 nombres dans la clef et le module m est choisi pour avoir une longueur comprise entre 100 et 200 bits.
 Didier
Müller, 24.1.21 |
  |
Pi alors