Cryptosystème de Merkle-Hellman

Cryptosystème de Merkle-Hellman

Merkle-Hellman (MH) est un des premiers cryptosystème asymétrique, 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].

Sommaire

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

Pour ce cryptosystème, les clés sont des "sac à 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 nombre pour transformer le sac dur en sac facile, opération réalisable en temps polynomial.

Chiffrement

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

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

Génération des clés

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

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

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,xi = wi.

Voir aussi

Notes et 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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Cryptosystème de Merkle-Hellman de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Cryptosysteme de Merkle-Hellman — Cryptosystème de Merkle Hellman Merkle Hellman (MH) est un des premiers cryptosystème asymétrique, 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… …   Wikipédia en Français

  • Cryptosystème De Merkle-Hellman — Merkle Hellman (MH) est un des premiers cryptosystème asymétrique, 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] Sommaire …   Wikipédia en Français

  • Cryptosystème de merkle-hellman — Merkle Hellman (MH) est un des premiers cryptosystème asymétrique, 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] Sommaire …   Wikipédia en Français

  • Cryptosysteme — Cryptosystème Un cryptosystème est un terme utilisé en cryptographie pour désigner un ensemble composé d algorithmes cryptographiques et de tous les textes en clairs, textes chiffrés et clés possibles (définition de Bruce Schneier). Cette… …   Wikipédia en Français

  • Cryptosystème — Un cryptosystème est un terme utilisé en cryptographie pour désigner un ensemble composé d algorithmes cryptographiques et de tous les textes en clairs, textes chiffrés et clés possibles (définition de Bruce Schneier). Cette dénomination est… …   Wikipédia en Français

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Problème du sac à dos — Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? En algorithmique, le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un… …   Wikipédia en Français

  • Chiffrement asymétrique — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

  • Chiffrement à clé publique — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

  • Clef privée — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”