Cryptosystème de Merkle-Hellman

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 fondé 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 numérotés de 1 à n, ayant chacun une valeur, existe-t-il un sous-ensemble de ces éléments dont la somme des valeurs est nulle ? En règle générale, ce problème est connu pour être NP-Complet. Cependant, si l'ensemble, dit "sac à dos", est trié tel que chaque élément est plus grand que la somme de tous les nombres le précédant, alors le problème est "facile" et résoluble en un temps polynomial. On dit que le sac est supercroissant.

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

Pour ce cryptosystème, les clés sont des "sacs à dos". La clé publique est un sac à dos dit "dur", la clé privée un sac dit "facile", tel que problème soit solvable en temps polynomial, avec un facteur multiplicatif et un modulo. On utilise ces nombres pour transformer le sac dur en sac facile, opération réalisable en temps polynomial.

Chiffrement[modifier | modifier le code]

Pour chiffrer le message, on utilise un sous-ensemble du sac dur, choisi en le comparant avec un ensemble de bits (le texte en clair) de même longueur que la clé, et tel que chaque terme de la clé publique corresponde à un 1 du texte en clair. Les 0 sont ignorés. Dès lors, on fait la somme de ce sous-ensemble, constituant le texte chiffré.

Déchiffrement[modifier | modifier le code]

L'algorithme de déchiffrement de Merkle-Hellman consiste à résoudre un problème de sac à dos, mais cette fois ci sur un sac supercroissant donc transformable en temps polynomial en la clé publique : le sac facile.

Plus formellement[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 \{a_1,a_2,\cdots,a_n\} et d'un nombre N , N > a_1 + a_2 + \cdots + a_n
  • Choix d'un nombre A<N tel que pgcd(A,N)=1
  • Calcul des b_i \equiv A a_i \pmod{N}

Dès lors, on obtient une clé publique \{b_1,b_2,\cdots,b_n\} et une clé privée (N,A,\{a_1,a_2,\cdots,a_n\})

Chiffrement[modifier | modifier le code]

Considérons un mot w \in \{0,1\}^{*} c'est-à-dire un mot binaire. Si n est sa longueur et celle de la séquence alors,

 c = \sum_{i=1}^{n} w_i b_i

représente le message chiffré.

Déchiffrement[modifier | modifier le code]

Considérons le mot chiffré c. Posons p \equiv A^{-1} c \pmod{N}. On peut alors écrire,

c = \sum_{i=1}^{n} x_i a_i

On a alors pour tout i, x_i = w_i.

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