Cryptosystème de Merkle-Hellman

En cryptologie, Merkle-Hellman (MH) est un des premiers cryptosystèmes asymétriques, défini par Ralph Merkle et Martin Hellman en 1978[1]. Bien que l'idée soit élégante, et bien plus simple que RSA, il a été démontré comme vulnérable par Adi Shamir[2],[3].

Description

Merkle-Hellman est un cryptosystème asymétrique. Cependant, contrairement à RSA, il est à sens unique, c'est-à-dire que la clé publique est utilisée uniquement pour le chiffrement, et la clé privée uniquement pour le déchiffrement. Il ne peut donc pas être utilisé pour un protocole d'authentification.

Il est basé sur le problème de la somme de sous-ensembles (un cas spécial du problème du sac à dos): étant donnés n entiers et un entier p, existe-t-il un sous-ensemble de ces éléments dont la somme des valeurs est p ? Ce problème est NP-Complet[3]. Une instance composé de n entiers s'appelle un sac. On dit qu'un sac est supercroissant lorsque chaque élément est plus grand que la somme des éléments qui sont plus petits que lui. Le problème restreint aux instances supercroissantes est décidable en temps polynomial avec un algorithme glouton[3].

Génération de clefs

Pour ce cryptosystème, les clés sont des sacs :

• La clé privée contient entre autres (voir la section formalisation pour plus de détails) un sac supercroissant dit "facile" solvable en temps polynomial ;

• La clé publique est un sac à dos dit "dur" calculée à partir de la clé privée.

Chiffrement

Pour chiffrer le message, on utilise la clé publique. Le mot à chiffrer peut être vu comme un certificat de l'instance du sac "dur". Le mot chiffré est la valeur obtenue à l'aide de ce certificat. Le mot à chiffrer est aussi un certificat pour l'instance du sac "facile" mais seul le possesseur de la clé privée peut l'obtenir facilement.

Déchiffrement

L'algorithme de déchiffrement de Merkle-Hellman consiste à résoudre l'instance du sac "facile".

Formalisation

Génération des clés

On procède en 3 étapes[3]:

• Choix d'une séquence super-croissante ${\displaystyle \{a_{1},a_{2},\cdots ,a_{n}\}}$ et d'un nombre ${\displaystyle N,N>a_{1}+a_{2}+\cdots +a_{n}}$
• Choix d'un nombre ${\displaystyle A<N}$ tel que ${\displaystyle pgcd(A,N)=1}$
• Calcul des ${\displaystyle b_{i}\equiv Aa_{i}{\pmod {N}}}$

Dès lors, on obtient une clé publique ${\displaystyle \{b_{1},b_{2},\cdots ,b_{n}\}}$ (un sac "dur") et une clé privée ${\displaystyle (N,A,\{a_{1},a_{2},\cdots ,a_{n}\})}$ (un sac "facile" et deux nombres ${\displaystyle N}$ et ${\displaystyle A}$).

Chiffrement

La clé publique permet de chiffrer des messages de longueur ${\displaystyle n}$. Considérons un mot fini ${\displaystyle w\in \{0,1\}^{n}}$ de longueur ${\displaystyle n}$. Alors[3]:

${\displaystyle c=\sum _{i=1}^{n}w_{i}b_{i}}$

est le message chiffré par la clé publique ${\displaystyle \{b_{1},b_{2},\cdots ,b_{n}\}}$.

Déchiffrement

Considérons le mot chiffré ${\displaystyle c}$. Posons ${\displaystyle p\equiv A^{-1}c{\pmod {N}}}$[note 1]. On peut alors écrire, l'instance du problème du sac à dos[3]:

${\displaystyle p=\sum _{i=1}^{n}x_{i}a_{i}}$

qui a pour solution ${\displaystyle i,x_{i}=w_{i}}$. Le détenteur de la clef privée ${\displaystyle (N,A,\{a_{1},a_{2},\cdots ,a_{n}\})}$ peut calculer calculer ${\displaystyle p}$ et résoudre en temps polynomial l'instance du sac à dos pour retrouver le message original ${\displaystyle (w_{1},\dots ,w_{n})\in \{0,1\}^{n}}$.

Exemple

Tout d'abord, on génère la clé privée ${\displaystyle (N,A,\{a_{1},a_{2},\cdots ,a_{n}\})}$. D'abord, on génère une séquence super-croissante :

(a1, etc. a8) = {2, 7, 11, 21, 42, 89, 180, 354}

On calcule la somme :

${\displaystyle \sum _{i=1}^{8}a_{i}=706}$

puis on choisit un nombre ${\displaystyle N}$ plus grand que cette somme :

N = 881

Puis on choisit un nombre ${\displaystyle A<N}$ avec ${\displaystyle pgcd(A,N)=1}$ :

A = 588

La clé privée est générée : c'est ${\displaystyle (N,A,\{a_{1},a_{2},\cdots ,a_{n}\})}$.

À présent on calcule la clé publique ${\displaystyle \{b_{1},b_{2},\cdots ,b_{n}\}}$ avec ${\displaystyle b_{i}\equiv Aa_{i}{\pmod {N}}}$ :

b = {295, 592, 301, 14, 28, 353, 120, 236}

car

(2 * 588) mod 881 = 295
(7 * 588) mod 881 = 592
(11 * 588) mod 881 = 301
(21 * 588) mod 881 = 14
(42 * 588) mod 881 = 28
(89 * 588) mod 881 = 353
(180 * 588) mod 881 = 120
(354 * 588) mod 881 = 236

Alice veut chiffrer le message "a". Elle traduit le message "a" en binaire (en utilisant ASCII ou UTF-8) :

w = 01100001

Elle calcule le message chiffré ${\displaystyle c=\sum _{i=1}^{n}w_{i}b_{i}}$ :

w = 01100001
b = 0 * 295
  + 1 * 592
  + 1 * 301
  + 0 * 14
  + 0 * 28
  + 0 * 353
  + 0 * 120
  + 1 * 236
         = 1129 

Elle envoie alors 1129 à Bob. Vous pouvez essayer l'exemple ici.

Pour déchiffrer le message chiffré 1129, Bob calcule ${\displaystyle p\equiv A^{-1}c{\pmod {N}}}$ :

p = 1129 * 442 mod 881 = 372

Maintenant, Bob résout l'instance ${\displaystyle p=\sum _{i=1}^{n}x_{i}a_{i}}$ avec un algorithme glouton. Il décompose p = 372 en sélectionnant le ${\displaystyle a_{i}}$ le plus grand qui inférieur ou égal à 372. Puis il recommence jusqu'à obtenir 0 :

372 - 354 = 18
18 - 11 = 7
7 - 7 = 0
                         rappel : (a1, etc. a8) = {2, 7, 11, 21, 42, 89, 180, 354}

Les éléments sélectionnées de notre sac privé ${\displaystyle \{a_{1},a_{2},\cdots ,a_{n}\}}$, c'est-à-dire ${\displaystyle a_{2},a_{3},a_{8}}$ donne le message initial :

w = 01100001

qui correspond au message "a".

Voir aussi

• Problème du sac à dos
• Problème NP-complet
• Chiffrement RSA

Notes et références

Notes

1. ${\displaystyle A^{-1}}$ peut être calculé facilement à l'aide de l'algorithme d'Euclide étendu.

Références

1. Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525–530.
2. Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279–288. http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF
3. Pascal Boyer, Petit compagnon des nombres et de leurs applications, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), VI. Cryptographie, chap. 6 (« La méthode du sac à dos »), p. 538-539.