# 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. 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$^,$.

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

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:
* 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 Aa_{i}{\pmod {N}}$
Dès lors, on obtient une clé publique $\{b_{1},b_{2},\cdots ,b_{n}\}$ (un sac "dur") et une clé privée $(N,A,\{a_{1},a_{2},\cdots ,a_{n}\})$ (un sac "facile" et deux nombres $N$ et $A$).

### Chiffrement

La clé publique permet de chiffrer des messages de longueur $n$. Considérons un mot fini $w\in \{0,1\}^{n}$ de longueur $n$. Alors:
$c=\sum _{i=1}^{n}w_{i}b_{i}$
est le message chiffré par la clé publique $\{b_{1},b_{2},\cdots ,b_{n}\}$.

### Déchiffrement

Considérons le mot chiffré $c$. Posons $p\equiv A^{-1}c{\pmod {N}}$. On peut alors écrire, l'instance du problème du sac à dos:
$p=\sum _{i=1}^{n}x_{i}a_{i}$
qui a pour solution $i,x_{i}=w_{i}$. Le détenteur de la clef privée $(N,A,\{a_{1},a_{2},\cdots ,a_{n}\})$ peut calculer calculer $p$ et résoudre en temps polynomial l'instance du sac à dos pour retrouver le message original $(w_{1},\dots ,w_{n})\in \{0,1\}^{n}$.

## Exemple

Tout d'abord, on génère la clé privée $(N,A,\{a_{1},a_{2},\cdots ,a_{n}\})$. D'abord, on génère une séquence super-croissante :
On calcule la somme :
    $\sum _{i=1}^{8}a_{i}=706$
puis on choisit un nombre $N$ plus grand que cette somme :
Puis on choisit un nombre $A<N$ avec $pgcd(A,N)=1$ :
La clé privée est générée : c'est $(N,A,\{a_{1},a_{2},\cdots ,a_{n}\})$.
À présent on calcule la clé publique $\{b_{1},b_{2},\cdots ,b_{n}\}$ avec $b_{i}\equiv Aa_{i}{\pmod {N}}$ :
car
Alice veut chiffrer le message "a". Elle traduit le message "a" en binaire (en utilisant ASCII ou UTF-8) :
Elle calcule le message chiffré $c=\sum _{i=1}^{n}w_{i}b_{i}$ :
Elle envoie alors 1129 à Bob. Vous pouvez essayer l'exemple ici.
Pour déchiffrer le message chiffré 1129, Bob calcule $p\equiv A^{-1}c{\pmod {N}}$ :
Maintenant, Bob résout l'instance $p=\sum _{i=1}^{n}x_{i}a_{i}$ avec un algorithme glouton. Il décompose p = 372 en sélectionnant le $a_{i}$ le plus grand qui inférieur ou égal à 372. Puis il recommence jusqu'à obtenir 0 :
Les éléments sélectionnées de notre sac privé $\{a_{1},a_{2},\cdots ,a_{n}\}$, c'est-à-dire $a_{2},a_{3},a_{8}$ donne le message initial :
qui correspond au message "a".