WikiMath

---

Le problème du sac à dos

Présentation

Le problème du sac à dos fournit un autre exemple de fonction à sens unique. Ce problème est encore connu sous le nom de knapsack problem.

On dispose d'un sac à dos de volume $V$, et on désire occuper tout ce volume en utilisant des objets $o_i$ de volume $a_i$.

Cependant, la somme des $a_i$ dépasse $V$, et on ne rangera donc pas tous les objets...

Vers une formalisation du problème

On introduit, pour chaque objet $o_i$, le nombre $\varepsilon_i$, égal à 1 ou 0 selon que l'objet $o_i$ sera ou non rangé dans le sac.

Le choix des $o_i$ doit donc être tel que $\sum_i \varepsilon_i a_i \leqslant V$

Formalisation du problème du sac à dos

Soit $n$ un entier positif fixé. Tout entier $x$ compris entre 0 et $2^n-1$ s'écrit, en base 2, d'une unique façon : $x = \overline{\varepsilon_{n-1} ... \varepsilon_1 \varepsilon_0}_2, \textrm{ et on a } x =\sum_{k=0}^{n-1} \varepsilon_k 2^k$

Soit maintenant $a_0, a_1, ..., a_{n-1}$ des entiers strictement positifs fixés. Considérons l'application : $\displaystyle{x =\sum_{k=0}^{n-1} \varepsilon_k 2^k \in \mathbb{Z}_{2^n-1} \longmapsto f(x) = \sum_{k=0}^{n-1} \varepsilon_k a_k \in \mathbb{N}^*}$

Fonction à sens unique

Pour $x$ fixé, le calcul de $f(x)$ est très facile.

En revanche, pour $y \leqslant \sum_{k=0}^{n-1} a_k$ fixé, il est très difficile de trouver $\varepsilon_0, \varepsilon_1, ..., \varepsilon_{n-1} \in \{0,1\}$ tel que $y = \sum_k \varepsilon_k a_k $.

En effet, on ne connaît pas d'algorithme pour cela, si ce n'est une recherche exhaustive. Or, il y a $2^n$ choix possibles.

À la recherche d'une fonction inverse

Application à la cryptographie

On pourrait être tenté d'utiliser la fonction $f$ précédente pour coder les messages préalablement découpés en blocs de $n$ bits. Cependant, le destinataire serait totalement démuni pour déchiffrer le message.

Les fonctions supercroissantes

Il existe toutefois un cas où $f$ est facilement inversible : quand la suite $a_i$ est supercroissante, i.e. $\displaystyle{\forall k = 1, ..., n-1, a_k > \sum_{i=0}^{k-1} a_i}$

On obtient alors facilement les $\varepsilon_k$ en commençant par $\varepsilon_{n-1}$, qui vaut 0 ou 1, selon que le cryptogramme $c$ est inférieur strictement, ou supérieur à $a_{n-1}$, et ainsi de suite.

L'ennui est qu'alors le message est facile à déchiffrer pour tout le monde !

Une technique de chiffrement

Voici une technique de chiffrement, proposée en 1978 par Merkle et Hellman.

Une suite supercroissante $(a_0, ..., a_{n-1})$ étant choisie, Alice la remplace par une suite $(b_0, ..., b_{n-1})$, qui ne l'est plus, de la façon suivante...

Travail préliminaire d'Alice

1. Alice choisit un entier $\displaystyle{l > \sum_{k=0}^{n-1} a_k}$, puis un entier $u$ premier à $l$.
2. Alice cherche ensuite un entier $v$ tel que $uv \equiv 1 %l$, et pose $b_k = u a_k %l$, pour $k=0, ..., n-1$.
3. Alice rend alors publique la clé de chiffrement $(b_0, ..., b_{n-1})$, et garde secrets les entiers $l, u, v$.

Chiffrement de Bob

1. Bob souhaite envoyer le message $m$ à Alice.
2. Il transforme son message $\displaystyle{m = \sum_{k=0}^{n-1} \varepsilon_k 2^k}$ à l'aide de la clé publique $(b_0, ..., b_{n-1})$.
3. Bob envoie donc le cryptogramme $\displaystyle{m = \sum_{k=0}^{n-1} \varepsilon_k b_k}$

Déchiffrement d'Alice

1. Alice transforme $c$ en $c'$ par $c' \equiv vc %l$
2. Elle retrouve $m$ comme si $c'$ était chiffré à l'aide de la suite supercroissante $(a_0, ..., a_{n-1})$.

Remarques terminales

Il y a en fait deux clés :

• une clé publique pour le chiffrement, à savoir $(b_0, ..., b_{n-1})$.
• Une clé secrète pour le déchiffrement, à savoir $(l,v)$.

En 1982, Shamir a obtenu un algorithme qui résout dans ce cas le problème du sac à dos en un temps polynomial.

Travaux pratiques

Mettre en oeuvre le cryptage par la méthode inspirée du problème du sac à dos.