Accueilretour

Systèmes modernes à clé publique

1. "Sac à dos" (knapsack)

Généralités

Stéganographie

Cryptanalyse

Littérature

Transpositions

Subs. monoα

Subs. polyα 1 - 2

One-time pad

DES 1 - 2

Clef publique

Knapsack

problème du sac à dos

application

confection des clefs
chiffrage
déchiffrage

exemple

destin

Diffie-Hellman

RSA 1 - 2

Grands noms

Références



 Le système de chiffrage Merkle-Hellman est plus connu sous le nom de "sac à dos" (knapsack) en référence au célèbre problème de combinatoire dont il dérive.

Apparu en 1978, c'est l'un des premiers systèmes de chiffrement asymétriques inventés. Bien qu'il n'ait pas survécu à une cryptanalyse approfondie, il illustre bien dans sa simplicité les principes d'un cryptosystème à clef publique.

Le problème du sac à dos

Considérons un sac à dos pouvant supporter un poids maximal Pmax. On cherche à le remplir d'objets d'utilités ui , de poids pi . On code leur présence à l'aide de coefficients δi∈{0, 1} (0 : absent, 1 : présent).

Le problème du sac à dos consiste alors à maximiser ∑δi ui sous la condition ∑δi pi ≤ Pmax, idéalement ∑δi pi = Pmax.

retour

Application au chiffrage

Supposons que la séquence des δi∈{0, 1} représente le codage binaire d'un message de longueur ℓ. Connaissant P = ∑δi pi , peut-on retrouver les δi ? Il n'y a pas de solution simple, voire unique, dans le cas général.

C'est facile en revanche si la suite (pn)n∈ℕ* est super-croissante, càd si pk+1 > ∑i=1k pi . Alors il suffit de calculer
  • i0 = max(i | pi ≤ P) (→ δi0 = 1)
  • i1 = max(i | pi ≤ P − pi0) (→ δi1 = 1)
    ...
  • ik = max(i | pi ≤ P − ∑i=0k−1pi) (→ δik =1)
Un exemple simple est la suite des puissances de 2 : pk = 2k−1. En effet, ∑i=1k pi =  ∑i=0k−1 2i = 2k−1 < 2k = pk+1 [1].

retour

confection des clefs

On sélectionne tout d'abord une suite super-croissante (pn)n∈ℕ* -- on ne l'utilisera que jusqu'à la longueur ℓ maximale des messages. Si, comme nous l'envisageons ensuite, ceux-ci sont découpés caractère par caractère, alors ℓ = 8 (1 octet) suffit.

On fixe ensuite deux entiers a et b, avec 1 ≤ a < b, satisfaisant les deux conditions :
  1. a > p1 + ... + pℓ (Cette condition est nécessaire pour assurer l'injectivité du chiffrage. Sans elle, deux clairs distincts pourraient donner deux chiffrés identiques.)

  2. a∧b = 1 (a et b premiers entre eux) (Cette condition assure l'existence d'un inverse modulo a pour b, ce qui rend possible le déchiffrage.)
On calcule ensuite (ci)1≤i≤ℓ∈[0, a−1]ℓ  tels que

ci = b × pi (mod. a).

La liste (ci)1≤i≤ℓ constitue la clef publique [2].

On détermine un entier c tel que

b × c ≡ 1 (mod. a)

(l'inverse de b modulo a).
La liste (pi)1≤i≤ℓ , accompagnée de l'entier c (ou de a et b) constitue la clef secrète ou privée.

retour

principe de chiffrage

Le texte clair M est tout d'abord converti en segments de ℓ bits (typiquement 1 octet) qui seront chiffrés individuellement.

Pour chaque tel segment S = [bℓbℓ−1...b1]2 (= ∑i=1ℓ 2i−1bi), le message chiffré correspondant sera

SC = ∑i=1ℓ ci × bi .

retour

principe de déchiffrage

Le destinataire forme simplement

    c × SC = ∑i=1ℓ bi × c × ci
               ≡ ∑i=1ℓ bi × c × b × pi (mod. a)
               ≡ ∑i=1ℓ bi × pi (mod. a)

et la détermination des bi nous ramène au problème du sac à dos dans le cas de la suite super-croissante (pi).

Le cas pi = 2i−1 est particulièrement favorable, puisque alors il vient tout simplement :

c × SC ≡ S (mod. a).

retour

Exemple

Endossons le rôle de Bob qui souhaite créer un jeu de clefs, privée et publique, afin que chacun puisse écrire des messages cryptés à son attention.

Dédaignant le cas trivial ci-dessus, Bob choisit comme séquence super-croissante :

p = [2, 3, 6, 15, 40, 100, 215, 570].


C'est la première partie de sa clef privée.

La somme des pi est 951 ; Bob fixe donc a = 1452 puis b = 545 (non sans vérifier qu'il est bien premier avec a) [3].

À partir de b, Bob calcule :
  • la séquence (ci)1≤i≤ℓ des b × pi mod. a : [1090, 183, 366, 915, 20, 776, 1015, 1374] -- cela sera sa clef publique -- ;
  • l'inverse c de b modulo a : c = 365 (puisque 365 × 545 = 198 925 ≡ 1 mod. 1452) : c'est la seconde partie de sa clef privée.
Bob diffuse sa clef publique. Son système de chiffrement est désormais opérationnel.

Mettons-nous maintenant à la place d'Alice.

Nous nous attelons avec Alice à la lourde tâche de coder pour Bob l'unique caractère "X" -- un message hautement suggestif.

Le codage binaire (ASCII) de X est

[01011000]2 (= [88]10).

Alice a eu connaissance de la clef publique de Bob -- comme tout le monde --. Elle forme donc :

SC = ∑i=1ℓ ci × bi
     = 0 × 1090 + 1 × 183 + 0 × 366 + 1 × 915 + 1 × 20 + 0 × 776 + 0 × 1015 + 0 × 1374
     = 1118.

Alice envoie donc "1118" à Bob.

Reprenons maintenant le rôle de ce dernier.

Il utilise sa clef secrète c . Bob calcule

c × SC = 365 × 1118 = 408 070 ≡ 58 mod. 1452.

Notons que ce nombre n'est pas identique à celui dont est partie Alice. Ce n'est ni surprenant ni contradictoire, puisque la suite super-croissante p choisie n'est pas celle des puissances de 2.

À l'aide de cette suite p = [2, 3, 6, 15, 40, 100, 215, 570] -- l'autre partie de sa clef secrète --, Bob doit résoudre le problème du sac à dos correspondant au nombre d = 58. Il calcule ainsi :
  • le plus grand des pi ≤ d est 40 = p5 de sorte que d5 = 1 (d6 = d7 = d8 = 0) ;
  • le plus grand des pi ≤ d − p5 = 18 est 15 = p4 donc d4 = 1 également ;
  • le plus grand des pi ≤ d − p5 − p4 = 3 est 3 = p2 donc d2 = 1 (d3 = 0) ;
  • enfin d - p5 − p4 − p2 = 0, ce qui met fin à la résolution (et d1 = 0).
En somme, Bob a reconstitué la séquence 01011000 qui est bien le code binaire du caractère X transmis par Alice. Il peut se frotter les mains. Le message a voyagé en toute sécurité.

retour

Destin du système knapsack

Nous avons cité ce système pour son côté ludique et sa facilité de mise en œuvre.

Néanmoins, il n'est plus actuellement un système de cryptage sûr. En 1982, A. Shamir a publié un algorithme pour "casser" en temps polynomial le système Merkle-Hellman.

retour

Notes

[1]  Il s'agit de la plus petite suite super-croissante.

[2]  Cette suite-là n'est pas nécessairement croissante.

[3]  Ces valeurs ont été générées aléatoirement en conformité avec les hypothèses.