Chiffre de Merkle-Hellman

1. Introduction teur contenu. Pour un contenu X donné, la valeur to-

tale contenue dans le sac est naturellement :
En 1978, Ralph Merkle et Martin Hellman n
proposèrent un cryptosystème à clé publique basé sur
un problème célèbre: le problème du sac à dos
z ( X )= ∑ pi=∑ x i p i
{i , x i=1 } i =1
(Knapsack problem). Qui est sous la forme suivante :
Imaginons une collection de cailloux de poids {a1, De même, la somme des poids des objets choisis est :
a2, .... , an} connus. Supposons que l'on place certains n
de ces cailloux dans un sac à dos et que l'on pèse le
tout. Est-il possible, connaissant ce poids total, de
w ( X )= ∑ w i =∑ x i wi
{i , xi =1 } i=1
savoir quels cailloux sont dans le sac ?
Le problème peut alors être reformulé comme la re-
Pour ce dit crypto système, les clés sont des "sac à cherche d'un vecteur contenu X = (x1, x2,..., xn) (les
dos". Pour chiffrer le message, on utilise un sous- composantes valant 0 ou 1), réalisant le maximum de
ensemble du sac, choisi en le comparant avec un la fonction valeur totale z(X), sous la contrainte :
ensemble de bits (le texte en clair) de même longueur
n
que la clé, et tel que chaque terme de la clé publique
corresponde à un 1 du texte en clair. Les 0 sont w ( X )=∑ x i wi ≤W (1)
i=1
ignorés. Dès lors, on fait la somme de ce sous-
ensemble, constituant le texte chiffré. L'algorithme de C'est-à-dire que la somme des poids des objets choisis
déchiffrement de Merkle-Hellman consiste à résoudre ne dépasse pas la capacité du sac à dos.
un problème de sac à dos, mais cette fois-ci sur un sac
supercroissant donc transformable en temps En général, on ajoute les contraintes suivantes afin
polynomial en la clé publique : le sac facile. d'éviter les cas singuliers :

2. Problème de Sac à Dos  On ne peut pas mettre tous les objets :

n
En algorithmique, le problème du sac à dos, [4] noté
également KP (en anglais, Knapsack Problem) est un ∑ wi >W
i=1
problème d'optimisation combinatoire. Il modélise une
situation analogue au remplissage d'un sac à dos, ne  Aucun objet n’est plus lourd que ce que le
pouvant supporter plus d'un certain poids, avec tout ou sac peut porter :
partie d'un ensemble donné d'objets ayant chacun un
poids et une valeur. Les objets mis dans le sac à dos w i ≤ W , ∀ i ∈{1 ,… , n }
doivent maximiser la valeur totale, sans dépasser le  Tout objet a une valeur et apporte un gain :
poids maximum.
pi >0 , ∀ i∈{1 ,… ,n }
2.1 Énoncé Mathématique
Les données du problème peuvent être exprimées en  Tout objet a un certain poids et consomme
termes mathématiques. Les objets sont numérotés par des ressources :
l'indice i variant de 1 à n. Les nombres wi et pi repré- w i> 0 , ∀ i ∈{1 , … , n }
sentent respectivement le poids et la valeur de l'objet
numéro i. La capacité du sac sera notée W. Il existe de 2.2 Terminologie :
multiples façons de remplir le sac à dos.
 z(X) est appelée fonction objectif ;
Pour décrire l'une d'elles il faut indiquer pour chaque
 tout vecteur X vérifiant la contrainte (1) est
élément s'il est pris ou non. On peut utiliser un codage
dit réalisable ;
binaire :
 si la valeur de z(X) est maximale, alors X est
 l'état du ième élément vaudra xi = 1 si l'élément
dit optimale.
est mis dans le sac, ou
 xi = 0 s'il est laissé de côté.  Une séquence de nombres est une séquence
super-croissante (super-increasing sequence)
Une façon de remplir le sac est donc complètement
si chaque nombre de cette séquence est plus
décrite par un vecteur, appelé vecteur contenu, ou sim-
grand ou égal à la somme des éléments qui le
plement contenu : X = (x1, x2,..., xn) ; et le poids asso-
précédent dans la séquence.
cié, ainsi que la valeur associée, à ce remplissage,
peuvent alors être exprimés comme fonction du vec-
  on appelle efficacité d'un objet le rapport de
sa valeur sur son poids. Plus la valeur de l'ob-
jet est importante par rapport à ce qu'il
consomme, plus l'objet est intéressant.
2.3 NP-Complétude Algorithme glouton

Le problème de sac à dos peut être représenté sous une Pour i = n à 1 faire
forme décisionnelle en remplaçant la maximisation Si T Pi alors
par la question suivante : un nombre k étant donné, T = T - Pi
existe-t-il une valeur des xi pour laquelle : bi = 1
sinon
n
bi = 0
∑ pi . xi ≥ k Si T = 0 alors {b 1, ..., bn} est solution
i=1
sinon il n'y a pas de solution.
Avec respect de la contrainte ? Il y a un lien entre la
version « décision » et la version « optimisation » du Dans les cas où l'algorithme ne fournit pas
problème dans la mesure où s'il existe un algorithme systématiquement la solution optimale, il est appelé
polynomial qui résout la version « décision », alors on une heuristique gloutonne.
peut trouver la valeur maximale pour le problème
d'optimisation de manière polynomiale en appliquant 3. Crypto Système de Merkle et Hellman
itérativement cet algorithme tout en augmentant la va- Le crypto système de Merkle et Hellman [3, 6, 8]
leur de k. D'autre part, si un algorithme trouve la va- utilise le problème de sac à dos précédemment décrit
leur optimale du problème d'optimisation en un temps de la manière suivante :
polynomial, alors le problème de décision peut être ré-
solu en temps polynomial en comparant la valeur de la 3.1 Génération des Clés :
solution sortie par cet algorithme avec la valeur de k.
Ainsi, les deux versions du problème sont de difficulté o Un entier positif n suffisamment grand
similaire. Sous sa forme décisionnelle, le problème est (Merkle et Hellman recommandaient de
NP-complet, ce qui signifie qu'il n'existe pas de mé- prendre n de l'ordre de 100).
thode générale connue pour construire une solution o Choisir une suite {b1, b2,..., bn} d'entiers
optimale, à part l'examen systématique de toutes les positifs vérifiant la propriété suivante :
solutions envisageables. Le problème d'optimisation
est NP-difficile, sa résolution est au moins aussi diffi- i−1

cile que celle du problème de décision, et il n'existe ∀ i∈ [ 2 , n ] , bi > ∑ b j

pas d'algorithme polynomial connu qui, étant donné j=1
une solution, peut dire si elle est optimale (ce qui re- o Choisir un entier M, appelé module, tel que :
viendrait à dire qu'il n'existe pas de solution avec un k
n
plus grand, donc à résoudre le problème de décision
NP-complet). M >∑ b i
i=1
Comme pour la plupart des problèmes NP-complets, il
peut être intéressant de trouver des solutions réali- o Choisir un entier W[1, M-1] premier avec
sables mais non optimales (algorithme de glouton). M, i.e. tel que le pgcd(W, M) = 1.
De préférence avec une garantie sur l'écart entre la va- o Calculer :
leur de la solution trouvée et la valeur de la solution
optimale. ai'=W× bi mod M pour i [1, n]
2.4 Algorithme de Glouton C'est-à-dire calculer le produit de W et bi et
ne conserver que le reste de la division
Un algorithme glouton [6] est un algorithme qui suit euclidienne du résultat par M; l'entier obtenu
le principe de faire, étape par étape, un choix optimum est donc compris entre 0 et M-1).
local, dans l'espoir d'obtenir un résultat optimum
global. Son idée est d'ajouter en priorité les objets les o Calculer la permutation π de {1, 2,..., n} telle
plus efficaces, jusqu'à saturation du sac. que {aπ(1)', aπ(2)',..., aπ(n)'} soit une suite
croissante.
Par exemple, dans le problème du rendu de monnaie
(donner une somme avec le moins possible de pièces), o La clé publique est :
l'algorithme consistant à répéter le choix de la pièce de
(a1, a2,..., an) = (aπ(1)', aπ(2)',..., aπ(n)')
plus grande valeur qui ne dépasse pas la somme
restante est un algorithme glouton. Cette clé peut-être librement diffusée à tous ses
correspondants potentiels ou stockée dans un
 annuaire comparable à ceux utilisés pour les  Calcul de la permutation π : π(1)=8, π(2)=6,
numéros de téléphone. π(3)=7, π(4)=5, π(5)=2, π(6)=4, π(7)=10,
π(8)=3, π(9)=1, π(10)=9
La clé privée est composée de M, W, (b1, b2,..., bn)
ainsi que de la permutation π; cette clé privée doit  La clé publique est : (14406, 23206, 23446,
impérativement être gardée confidentielle et ne 25373, 24912, 25930, 32642, 32691, 44638,
doit être fournie à personne car elle n'est pas 47680)
nécessaire pour pouvoir chiffrer un message. Elle
 La clé privée est composée de M, W,
est par contre indispensable (si le système est sûr)
(b1,b2,...,b10) et de la permutation π
afin de pouvoir déchiffrer un message.
 Chiffrement message (1,0,0,1,0,0,0,1,1,0) :
Au contraire, si la suite des poids n'est pas super-
c=14406+25373+32691+44638=117108
croissante, le seul algorithme connu consiste à es-
sayer successivement toutes les solutions (b1,  Déchiffrement de c : application de l'algo-
b2, ..., bn) possibles. Si la suite est suffisamment rithme d'Euclide étendu à W et M : 7864× W-
longue, c'est un algorithme impraticable. 5675× M=1 donc W-1=7864 modM, calcul de
d=W-1× c modM=7865× 117108 mod
3.2 Chiffrement d'un Message :
50349=3753
 Le message à chiffrer est écrit en binaire sous
 Résolution du problème de sac à dos avec les
la forme m1m2... mn, avec mi{0,1} (si le
bi et la valeur cible 3753 : 3534+185+
message est trop long, il est coupé en blocs
30+4=3753=b1+b3+b5+b8, soit : (1,2,3, 4,
de n bits au plus)
5, 6, 7, 8, 9, 10)= (1,0,1,0,1,0,0,1,0,0)
 Calculer le chiffré C tel que :
 Calcule de m1=π(1)= 8=1, m2=π(2)= 6=0,
n m3=7=0, m4=5=1, m5=0, m6=0, m7=0, m8=1,
C=∑ mi . ai m9=1, m10=0
i=1
 On retrouve bien le message initial
 Transmettre C (1,0,0,1,0,0,0,1,1,0).
3.3 Déchiffrement d'un Message Chiffré: 4.2 Exemple 2:
 -1
Calculer d =W ×(c mod M) en utilisant 1er Étape : Pour un n =9 [5], Alice choisit S= ( 1, 3, 5,
l'algorithme d'Euclide étendu 11, 25, 53, 101, 205, 512), m = 960 et w = 143.
 Calculer 1, 2,...,n tels que d est donné par : L’inverse d de 143 mod 960 est 47.
n 2ème Étape : Pour chaque élément ai de S, Alice
d=∑ ε i . bi calcule bi = ai · e mod m, ce qui donne (143, 429,
i=1 715, 613, 695, 859, 43, 515, 256). En ordonnant
bi, elle obtient la clé publique ‘knapsack’ S' = (43,
Il s'agit de résoudre un problème de sac à dos très 143, 256, 429, 515, 613, 695, 715, 859).
simple grâce à de la propriété bi :
i−1
3ème Étape : Pour exprimer le message « RAS » en
code binaire, Bernard peut, par exemple, utiliser le
b i> ∑ b j code ASCII à 8 bits. R correspond à 01010010, A
j=1
à 01000001 et S à 01010011. Le message à coder
 Calculer mi= π(i) pour i [1, n] est RAS = 0101001 0010000 0101010 011. Il le
décompose en blocs de longueur convenue (7 par
 Le message déchiffré s'écrit, en binaire, sous
exemple) et chiffre chacun des blocs :
la forme m1 m2... mn.
0101001 se code 43 + 429 + 613 = 1085,
4. Résultats et Interprétations :
0010000 se code 515,
4.1 Exemple Numérique:
0101010 se code 143 + 429 + 613 = 1185,
 Pour un n artificiellement petit, n = 10
011  0110000 et se code 515 + 613 = 1128.
 Choix des bi : 4, 9, 30, 70, 185, 451, 1306,
3534, 6517, 17486 Il transmet à Alice le message 108 515 1185 1128
 n
Choix de M : 50349 (>i=1 bi) 4ème Étape : Alice va déchiffrer ce message élément
par élément , en calculant M d mod m et en
 Choix de W : 36334 (premier avec M)
déterminant la solution du problème du sac à dos.
 Calcul des ai : 44638, 24912, 32691, 25930,
1085 · 47 mod 960 = 115
25373, 23209, 23446, 14406, 47680, 32642
515 · 47 mod 960 = 205
 1185 · 47 mod 960 = 15 157,0,1296,2041,2320,569,0,2035,1726,436,1865,115
7,2320,1144,1599,2756,1466,0,1157,436,1599,2174,1
1128 · 47 mod 960 = 216
751,2756,1005,1732,1296,1011,2610,569,0,2187,172
115 = 101+11+3 correspond à 0000001 + 6,1865,575,0,1751,2035,1599,1732,2187,1751,1011,1
0100000 + 0001000 = 0101001 030,1030,1144,1290,2326,2756,1605,575,436,1466,1
144,569,2326,3331,1157,575,436,2187,2610,1290,23
205 = 205 correspond à 0010000
26,1466,0,1732,1466,1599,1599,0,2326,1005,1599,17
15 = 11+3+1 correspond à 0100000 + 32,2762,1466,1144,2187,2320,1005,1732,1296,1605,
0001000 + 0000010 = 0101010 1030,1144,721,2762,1157,0,1865,1732,1030,2174,11
44,721,1580,0,575,436,1599,1144,2895,2326,2187,0,
216 = 205+11 correspond à 001000 + 1011,436,1011,2174,2326,1751,1726,1030,1865,1732
0100000 = 0110000 ,1030,2174,1144,2320,2187,0,1865,436,2187,1144,28
Alice retrouve le message : 95,1751,2035,1296,1296,2041,2174,1599,0,2187,172
0101001001000001010100110000: RAS. 6,1865,575,436,1030,2174,2326,2187,2756,1296,129
6,1011,1605,2610,1144,1290,1157,1865,575,436,575,
4.3 Chiffrement d’un Texte : 2174,1751,721,1005,1865,575,2762,1599,2610,1144,
1. n=9 2762,436,0,1865,436,2174,1580,1290,2326,2187,0,18
2. Choisissez une suite [7] super-croissante S 65,2041,2320,1144,1599,2756,1005,1157,1865,2301,
contenant au moins neuf éléments (séparez 1605,1599,0,1751,1726,1005,1865,1466,2320,2174,1
vos nombres par des virgules) : 2, 5, 9, 21, 290,2756,1005,1296,1296,2041,2174,2174,1290,2756
45, 103, 215, 450, 946 ,2035,1605,575,436,1751,1580,1290,2320,1726,2035,
1865,1011,2320,2174,1290,721,1005,1005,1296,1605
3. i=1n ai = 1796 ,1030,1144,1144,2320,1005,1157,1296,2187,2035,15
4. Choisissez un nombre M supérieur à (i=1n 80,575,2187,1157,1296,575,436,1030,2174,1599,275
ai) et un nombre W premier avec M : 6,2035,2035,1732,575,1030,1580,569,2762,1726,101
1,575,436,1599,1144,1290,721,1005,1865,1732,2762,
 M = 2003 2174,2174,575,2326,2035,1011,1865,2041,2187,2174
 W = 1289 ,1290,2326,2187,0,1865,2187,1030,2610,575,2320,17
26,436,1732,2187,2320,1144,1290,2326,2187,1296,5
5. Votre clé publique est :{436, 569, 575, 75,436,1030,1599,436,2320,1726,1605,2762,575,103
721, 1030, 1183, 1570, 1586, 1921}. 0,1144,1144,1751,1726,2035,1865,2301,1605,1599,0,
6. L'inverse de W mod m est : 317 1751,1726,2041,575,436,1599,1865,1599,1751,2035,
2041,1865,1030,1030,1144,721,2187,1726,2035,575,
7. Choisissez la longueur L des blocs de chif- 436,1030,2174,2326,2756,2610,1157,1296,2041,2187
frement, L inférieure ou égale à 9 ,1599,0,1865,436,1030,575,436,1751,1144,569,2326,
 L=5 1466,0,721,1011,1599,1144,1599,721,569,2035,1732,
436,1030,2174,2320,2320,1726,1599,1011,175. ».
 L=8
Texte en clair : « Le premier cryptosystème à clef
Texte Chiffré avec L= 8 : « 2866,3764,1183,3783,
publique, qui fut proposé par Ralph Merkle et Martin
4352,3764,4485,3910,3764,4352,1183,3758,4352,494
Hellman en 1978, est basé sur le problème du sac à 0,3783,4358,5054,4788,4940,4788,4358,5060,4485,3
dos (Knapsack problem en anglais). Il n'est plus 764,1183,4339,1183,3758,4049,3764,3897,1183,3783
utilisé actuellement puisque ce chiffre, ainsi que de ,4794,3322,4049,3910,4219,4794,3764,2479,1183,42
nombreuses variantes, a été cassé au début des 19,4794,3910,1183,3897,4794,4358,1183,3783,4352,
années 80 par Adi Shamir. » 5054,3783,5054,4788,5496,1183,3783,3189,4352,118
3,3169,3189,4049,3783,3474,1183,3302,3764,4352,4
479,4049,3764,1183,3764,4358,1183,3302,3189,4352
Texte Chiffré avec L= 5 : « 1157,1466,1599,1599,0, ,4358,3910,4618,1183,2291,3764,4049,4049,4485,31
2326,1005,1599,1296,2041,2174,2174,1599,2187,172 89,4618,1183,3764,4618,1183,2649,3370,3793,2934,
6,1599,575,436,1466,2610,575,2895,1726,1030,1865, 2479,1183,3764,4788,4358,1183,3322,3189,4788,549
1466,2610,2610,1144,2895,1726,2035,1865,2035,160 6,1183,4788,4794,4352,1183,4049,3764,1183,3783,4
5,1144,2320,2187,1157,0,2326,0,1030,1144,1144,275 352,5054,3322,4049,5060,4485,3764,1183,3328,4794
6,1005,1011,1296,1751,1030,1580,0,2762,1726,569,1 ,1183,4788,3189,3758,1183,4339,1183,3328,5054,47
732,1466,1605,2610,569,2762,1726,1011,1011,1030, 88,1183,1904,3296,4618,3189,3783,4788,3189,3758,
1030,1580,569,2762,1726,1157,575,436,2035,1580,1 4479,1183,3783,4352,5054,3322,4049,3764,4485,118
290,2762,436,0,1865,436,2187,1144,2895,2326,1005, 3,3764,4618,1183,3189,4618,4333,4049,3189,3910,4
2301,1865,2301,1605,1599,0,2326,1005,436,1865,72 788,2340,3048,1183,2727,4049,1183,4618,2763,3764
1,1030,1011,575,1751,1726,1296,1865,436,1605,569, ,4788,4358,1183,3783,4049,4794,4788,1183,4794,43
0,2035,1726,1011,1865,1157,2041,2174,1751,2187,1 58,3910,4049,3910,4788,5496,1183,3189,3758,4358,
4794,3764,4049,4049,3764,4485,3764,4618,4358,118 contre, pour les dimensions supérieures on utilise
3,3783,4794,3910,4788,4219,4794,3764,1183,3758,3 l’algorithme LLL.
764,1183,3758,3474,3910,3897,3897,4352,3764,2479
,1183,3189,3910,4618,4788,3910,1183,4219,4794,37
64,1183,3328,3764,1183,4618,5054,4485,3322,4352,
3764,4794,4788,3764,4788,1183,4927,3189,4352,391
5.1 Réduction de Réseau
0,3189,4618,4358,3764,4788,2479,1183,3189,1183,5
496,4358,5496,1183,3758,3189,4788,4788,5496,1183 Afin de le décrire, il faut introduire un objet
,3189,4794,1183,3328,5496,3322,4794,4358,1183,33 mathématique appelé réseau ; considérons n vecteurs
28,3764,4788,1183,3189,4618,4618,5496,3764,4788, bi à n dimensions dont les composantes sont par
1183,2934,2213,1183,3783,3189,4352,1183,2006,332 exemple des réels. On considère l'ensemble des
8,3910,1183,3605,3474,3189,4485,3910,4352,3048 ». vecteurs de Rn engendrés en additionnant un nombre
quelconque, mais entier, de chaque vecteur. Cet
Plusieurs remarques s'imposent :
ensemble est appelé ''réseau engendré par la base
1. Si la longueur des blocs de chiffrement est {b1,b2,...,bn}'' et noté L. Il peut être simplement défini
égale à celle des caractères en code ASCII par :
à 8 bits, chaque lettre sera codée par le

{∑ }
n
même nombre. Le système est alors vulné- L=Z x b1 + Z x b2 +…+ Z x bn = r i x bi : ( r 1 ,r 2 , … , r n ) ∈ Z n
rable à une attaque à l'aide d'une analyse de i=1
fréquence. Il convient donc de choisir des
blocs de chiffrement de longueur inférieure L'idée de la réduction de réseau est de calculer une
à celle de la clé. nouvelle base engendrant le même réseau que
{b1,b2,...,bn} mais dont les vecteurs sont plus courts et
2. Seule la connaissance de la clé publique est ''plus orthogonaux''.
nécessaire pour chiffrer un message. Par
contre, il faut nécessairement disposer de Le principal algorithme de réduction de réseau, appelé
l'ensemble des éléments de la clé privée pour LLL, a été proposé en 1982 par Lenstra, Lenstra et
pouvoir déchiffrer en utilisant l'algorithme Lovász avec comme objectif de factoriser des
proposé. Nous sommes donc bien dans un polynômes.
scénario de chiffrement à clé publique. L'idée élémentaire est que, étant donné une base d'un
3. Retrouver le message clair associé à un chif- réseau, on continue à engendrer la même base en
fré nécessite la résolution d'un problème de échangeant des vecteurs ou en additionnant une
sac à dos comme décrit précédemment ; la combinaison linéaire à coefficients entiers de vecteurs
sécurité du cryptosystème repose donc en à un autre vecteur de la base.
grande partie sur l'hypothèse que ce problème Dans cet algorithme, on note entre crochets le produit
est impossible à résoudre sans connaître la scalaire habituel, i.e.
clé privée.
n
4. Connaissant la clé privée, il est facile de re- ¿ ( a 1 , a 2 , … , an ) ,( b1 ,b 2 ,… , b n)≥∑ ai . bi
calculer la clé publique. Par contre, retrouver i=1
la clé privée, et notamment les bi, à partir de
la clé publique, i.e. des ai, est un problème On note également  x  l'entier le plus proche de x.
apparemment difficile. L'algorithme nécessite de plus l'emploi de deux
matrices à n lignes et n colonnes notées µ et b*.
5. Cryptanalyse du Chiffrement Merkle-Hellman
Enfin, si b est une matrice, bi désigne le vecteur de la
Attaquer le cryptosystème [3] de Merckle et Hellman ligne i et bi,j désigne la composante située à
va consister, étant donné un chiffré C et une clé l'intersection de la ligne i et de la colonne j.
publique (a1, a2,..., an) à trouver :
(m1, m2,..., mn){0, 1}n tel que i=1n mi× ai=c, Le principal intérêt de cette réduction est qu'elle
permet de trouver un vecteur court du réseau, au sens
C'est-à-dire à simplement retrouver le message à partir de la norme euclidienne, qui apparaît en résultat
du chiffré et de la clé publique. comme élément de la base réduite.
Nous allons utiliser un outil appelé réduction de Rien ne garantit que l'on trouve le vecteur non nul le
réseau, qui consiste à transformer [9] un réseau plus court mais, expérimentalement, l'algorithme LLL
quelconque en un réseau dans lequel les vecteurs sont est très performant et permet d'obtenir des vecteurs
assez courts et presque orthogonaux. C'est un très courts.
problème classique en mathématiques
orthogonalisation de Gram-Schmidt qui remonte à En particulier, si un réseau possède un vecteur
Lagrange et Gauss pour les réseaux de rang 2. Par ''anormalement'' court, il y a de grandes chances qu'on
l'obtienne grâce à cet algorithme.
5.2 Définition du Réseau Plusieurs failles ont été découvertes qui a rendu
l’algorithme de Merkle-Hellman, aujourd'hui,
Considérons le réseau engendré par les lignes de la
complètement abandonné. Même avec diverses
matrice suivante :
améliorations (permutation sur les éléments de la base,
algorithme itéré, etc), il n'est pas sûr et l'on a trouvé
1 0 0 ... 0 a1 des algorithmes capables de le « casser » en un temps
0 1 0 ... 0 a2 polynomial. Herlestam a démontré en 1978 qu’un bit
0 0 1 ... 0 a3 de texte clair pouvait souvent être retrouvé.
. . . . . . Malgré les modifications apportées à l’algorithme à la
. . . . . . suite de ces découvertes, des travaux de Shamir (1982-
. . . . . . 84) et Brickell (1985) ont poussé [10] à l’abandon de
0 0 0 ... 1 an cet algorithme.
0 0 0 ... 0 c
Notons enfin qu'il n'existe qu'un seul système de
cryptage sûr basé sur le principe du ''sac à dos''. Il
Notons bi la ligne i de la matrice. Si i=1n mi× ai=c, il s'agit de l'algorithme de Chor-Rivest. Son principal
est alors clair que: inconvénient est la taille des clefs (de l'ordre de 50000
n bits).
∑ mi X bi −bn +1=(m1 , m2 , … , mn , 0) Bibliographies:
i=1

Puisque la dernière composante est égale à : [1] Schneier, Bruce, « Cryptographie appliquée »,
International Thomson Publishing France, Paris, 1997.
n

∑ mi . ai−C [2] Stinson Douglas, « Cryptographie - Théorie et

pratique », Vuibert Informatique, Paris, 2001.
i=1

La norme euclidienne de ce vecteur est donc inférieure [3] Guillaume Poupard, « L'étrange sac à dos de
à (n)1/2 (borne atteinte dans le cas le pire où tous les mi Merkle et Hellman », [Link]
sont égaux à 1). [Link]/profs/informatique/Guillaume.
Poupard/PI
On observe donc qu'à une solution du problème de sac
à dos est associé un vecteur particulièrement court du [4] [Link]
réseau. _sac_%C3%A0_dos

Si LLL est capable de trouver ce vecteur court, il sera [5] E. Chanthery, ORANCI Sevan, POURROY Louis,
possible d'en déduire les mi, i.e. de casser le « Cryptage et le problème du sac à dos », [Link]
cryptosystème de Merkle et Hellman ! [Link]/echanthe/doc/TIPE_cryptage.pdf, 2006.
[6] [Link]
knapsack/[Link]
6. Conclusion :
[7] [Link]
Cet algorithme, s'il est correctement implémenté, a ematique/cryptographie/nombres/merkle_hell.htm
une complexité en O(n× 2n/2), soit beaucoup moins que
la recherche exhaustive. Il nécessite cependant [8] [Link]
beaucoup de mémoire (de l'ordre de O(2n/2) octets). crypto/Slides/[Link]
Notons que cet algorithme est toujours exponentiel et [9] Abderrahmane Nitaj, « Applications de
difficilement praticable dès que n dépasse 80. Il est l'algorithme LLL en cryptographie », http://
clair que plus la clef est longue plus le message sera [Link]/~nitaj/[Link]
difficile à décrypter. Dans la pratique, on utilise au
moins 250 nombres dans la clef et le module m est [10] Jean-Marc Alliot, « Cryptographie »,
choisi pour avoir une longueur comprise entre 100 et [Link]
200 bits.