Le problème du sac à dos A votre droite, un sac à dos vide. A votre gauche, m objets, de poids respectifs a1,...,am. Quels objets doit-on mettre dans le sac à dos pour obtenir un poids total égal à k?
Il s'agit là d'un problème très difficile, à la fois en pratique (il est insoluble, même avec un ordinateur, pour de grandes valeurs de m), et en théorie (il fait partie des problèmes NP-complets). Il est très difficile, sauf dans le cas particulier où la suite (an) est supercroissante, c'est-à-dire si pour tout entier i :
Dans ce cas, on commence par comparer les valeurs de k et de am :
si k<am, il ne faut bien sûr pas prendre am.
sinon, il faut prendre obligatoirement am : si on ne le prenait pas, même en prenant tous les autres poids a1,...,am-1, on aurait un poids total inférieur strict à m, et a fortiori à k. Il suffit ensuite de résoudre le problème du sac à dos pour les poids a1,...,am-1, avec le poids total k-am.
Cryptographie et problème du sac à dos
Il est intellectuellement séduisant de baser un algorithme de cryptographie sur le problème du sac à dos. En effet, contrairement au problème de la factorisation d'entiers, ce problème est prouvé mathématiquement comme étant difficile, c'est à dite NP-complet (lire les explications). Merkle et Hellman ont proposé d'utiliser un sac à dos supercroissant comme clé privée, et de le camoufler sous un sac à dos général pour en faire une clé publique. Plus en détails, voici ce que cela donne :
on se donne un entier m, une suite supercroissante a1,...,am, et un autre entier entier M vérifiant :
On dispose ainsi d'un sac à dos supercroissant.
on choisit au hasard un entier W, compris entre 1 et M-1, et premier avec M-1.
on choisit au hasard une permutation de l'ensemble {1,...,m}.
on calcule pour tous les i. On vient ainsi de camoufler le problème du sac à dos supercroissant en sac à dos général.
La clé publique du système est la suite (a priori quelconque) b1,...,bm, la clé privée consiste en les deux entiers M et W, la permutation , et la suite supercroissante a1,...,am. Si on souhaite envoyer au détenteur du système (Bob) le message constitué de la suite de m bits x1,...,xm, on calcule d'abord :
puis on lui envoie C. Quelqu'un qui intercepte C et connait la clé publique b1,...,bm ne peut remonter aux xi, car la résolution du sac à dos général est un problème très compliqué.
En revanche, Bob qui connait la clé privée retrouve les xi de la façon suivante : il calcule d'abord
Il résout ensuite le sac à dos supercroissant avec le poids total D, et les poids a1,...,am. Il calcule des nombres ei valant 0 ou 1 et tels que :
Il en déduit les xi par la relation :
Justifions cette phase de déchiffrement. On a en effet, modulo M :
Malheureusement, pour séduisante qu'elle est, cette méthode de cryptographie n'est pas sûre. Très peu de temps après son invention, des failles très importantes ont été détectées. Le sac à dos "camouflé" n'est pas aussi général que souhaité, et des méthodes de théorie algorithmique des nombres permettent de le résoudre.
Application numérique
Fabrication des clés publiques et privées :
on choisit m=5 et la suite supercroissante :
Soit M=113, W=27 (premier avec M), et la permutation :
Le calcul de donne :
Envoi du message : on veut envoyer le message 10101 (en binaire). On transmet donc : C=b1+b3+b5=149. Remarquons que, comme prévu, lorsque l'on connait 149 et les poids 22, 16, 71, 54 et 56, il n'est pas du tout évident de retrouver ceux qui ont servi à former 149.
Réception du message : on calcule W-1 par l'algorithme d'Euclide, et on trouve W-1=67. Le calcul de W-1C donne 39 (tous les calculs s'effectuent modulo 113). On redécompose 39 dans la suite supercroissante :
A votre droite, un sac à dos vide. A votre gauche, m objets, de poids respectifs a1,...,am. Quels objets doit-on mettre dans le sac à dos pour obtenir un poids total égal à k?
Il s'agit là d'un problème très difficile, à la fois en pratique (il est insoluble, même avec un ordinateur, pour de grandes valeurs de m), et en théorie (il fait partie des problèmes NP-complets). Il est très difficile, sauf dans le cas particulier où la suite (an) est supercroissante, c'est-à-dire si pour tout entier i :
, et la suite supercroissante a1,...,am. Si on souhaite envoyer au détenteur du système (Bob) le message constitué de la suite de m bits x1,...,xm, on calcule d'abord :
pour tous les i. On vient ainsi de camoufler le problème du sac à dos supercroissant en sac à dos général.
donne :
