Cryptosystème de Merkle-Hellman

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant la cryptologie
Cet article est une ébauche concernant la cryptologie.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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].

Description[modifier | modifier le code]

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. 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.

Génération de clefs[modifier | modifier le code]

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.
  • la clé privée un sac supercroissant dit "facile" solvable en temps polynomial

Chiffrement[modifier | modifier le code]

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[modifier | modifier le code]

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

Formalisation[modifier | modifier le code]

Génération des clés[modifier | modifier le code]

On procède en 3 étapes :

  • Choix d'une séquence super-croissante et d'un nombre
  • Choix d'un nombre tel que
  • Calcul des

Dès lors, on obtient une clé publique (un sac "dur") et une clé privée (un sac "facile" et deux nombres et ).

Chiffrement[modifier | modifier le code]

La clé publique permet de chiffrer des messages de longueur . Considérons un mot fini de longueur . Alors

est le message chiffré par la clé publique .

Déchiffrement[modifier | modifier le code]

Considérons le mot chiffré . Posons . On peut alors écrire, l'instance du problème du sac à dos

qui a pour solution . Le détenteur de la clef privée peut calculer calculer et résoudre en temps polynomial l'instance du sac à dos pour retrouver le message original .


Exemple[modifier | modifier le code]

Tout d'abord, on génère la clé privée . D'abord, on génère une séquence super-croissante :

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

On calcule la somme :

puis on choisit un nombre plus grand que cette somme :

N = 881

Puis on choisit un nombre avec  :

A = 588

La clé privée est générée : c'est .

A présent on calcule la clé publique avec  :

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é  :

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  :

p = 1129 * 442 mod 881 = 372

Maintenant, Bob résout l'instance avec un algorithme glouton. Il décompose p = 372 en sélectionnant le 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, ... a8) = {2, 7, 11, 21, 42, 89, 180, 354}

Les éléments sélectionnées de notre sac privé , c'est à dire donne le message initial :

w = 01100001

qui correspond au message "a".

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  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