4.5.3 Merkle-Hellman Kryptosystem

1976 stellten W. Diffie und Hellman ein neues Konzept der Kryptographie vor: Public-Key Kryptographie. Kurz darauf, 1978, veröffentlichten Merkle und Hellman in [MH78] ein Kryptosystem, das auf dem Subset-Sum Problem basiert.

Wie schon im Kapitel Subset-Sum Problem erklärt, gibt es Knapsacks, so dass ein Problem (A, s) einfach zu Lösen ist. Superansteigende Knapsacks gehören in diese Kategorie. Andererseits kann es äußerst schwierig sein, für einen Knapsack A eine Lösung zu finden, wenn A nicht superansteigend ist.
Diese Tatsache benutzten Merkle und Hellman, um darauf ein Kryptosystem aufzubauen. Ausgangspunkt ist ein superansteigender Knapsack A. Dieser ist Teil des privaten Schlüssels. Ein zweiter Knapsack, B, wird dann aus A konstruiert und als öffentlicher Schlüssel bereitgestellt. B besitzt die superansteigende Eigenschaft nicht. Eine Nachricht p wird chiffriert, indem die Summe c = pB = p₁b₁ + p₂b₂ +... + p_nb_n berechnet wird. Dabei ist p_i ist das i-te Bit der Klartextnachricht p.

Jemand, der eine chiffrierte Nachricht c abfängt, ist mit dem schweren Problem (B, c) konfrontiert; er muss also herausfinden, welche Elemente b_i von B sich zu c aufsummieren. Der Besitzer des privaten Schlüssels jedoch kann aus c leicht die Nachricht p bestimmen, da er die zu B passende superansteigende Menge A kennt.

Im Folgenden wird das Merkle-Hellman Kryptosystem näher beschrieben.

1. Schlüsselerzeugung
• Festlegen des Parameters n. Dieser Parameter gibt an, wieviele Komponenten die Knapsack-Vektoren A und B haben. Gleichzeitig wird damit festgelegt, dass n-bit Nachrichten chiffriert werden.
• Erzeuge eine superansteigende Menge A = (a₁, ..., a_n)
• Wähle eine Zahl M, so dass M > SUM_i=1...n(a_i). M ist der Modulus.
• Wähle einen Multiplikanden W mit 1 <= W < M und ggT(M, W) = 1
  Diese Wahl von W garantiert ein inverses Element U mit UW = 1 (mod M)
• optional: wähle eine Permutation pi: {1,..., n} -> {1, ..., n}
• Die einzelnen Komponenten b_i des öffentlichen Schlüssels B werden durch folgende Vorschrift erzeugt:
  b_i = a_pi(i)W mod M, i = 1 ... n.

Die superansteigende Eigenschaft von A wird durch modulare Multiplikation verschleiert.
• Öffentlicher Schlüssel ist der Knapsack-Vektor B .
• Das Tupel (A, M, W) bildet den privaten Schlüssel.
2. Verschlüsselung
• Der Parameter n legt fest, dass pro Verschlüsselungsvorgang eine n-Bit Nachricht chiffriert wird. Daher muss vor Verschlüsselung eine evtl. größere Nachricht p in n-Bit Blöcke unterteilt werden.
• Sei nun p = (p₁, p₂, ..., p_n) die zu verschlüsselnde binäre Nachricht. Der Chiffretext c wird durch die Vorschrift c = pB = p₁b₁ + p₂b₂ + ... + p_nb_n erzeugt.

Das i-te Element von B wird zu c hinzuaddiert, wenn das i-te Bit von p Eins ist.
3. Entschlüsselung
Die Entschlüsselung eines Chiffretextes c erfolgt in zwei Schritten:
1. Berechne c' = Uc mod M = W^-1c mod M
2. Lösen des Problems (A, c').
   Da A eine superansteigende Menge ist, lässt sich das Problem (A, c') einfach lösen. Sei X = (x₁, ..., x_n) der erhaltene Lösungsvektor für (A, c'). Bei Verwendung einer Permutation ergeben sich die Nachrichtenbits p_i aus p_i = x_pi(i). Ansonsten gilt p_i = x_i

Damit ein Kryptosystem korrekt funktioniert, muss d(e(p)) = p sein. Dabei ist p die Klartextnachricht, e die Verschlüsselungsfunktion und d die Entschlüsselungsfunktion.
Tatsächlich gilt

Da sowohl c' < M als auch SUM (a_i) < M, folgt c' = pA = p₁a₁ + ... + p_na_n. Die Klartextbits p_i ergeben sich durch Lösen von (A, c') und anschließendem Rückgängigmachen der Permutation pi.

Applet starten

Anmerkungen zum Merkle-Hellman Kryptosystem

1. Merkle und Hellman gaben zur Schlüsselerzeugung folgende Werte als untere Grenze für n, M und A an:
• n = 100: die Knapsack-Vektoren A und B haben jeweils 100 Elemente.
• a₁ sollte etwa 100 Bit lang sein: |a₁| = 100
• |a_i| = 100 + i - 1
• |M| = 202
• Durch Verwenden dieser Parameter ergibt sich für den Chiffretext c eine binäre Länge von 209 Bit. Eine 100-bit Nachricht p wird durch eine 209-bit Chiffre dargestellt: die Datenexpansion beträgt 2,09.
2. A. Shamir hat 1983 in [SH83] einen Algorithmus vorgestellt, der das Basis-Merkle-Hellman Kryptosystem erfolgreich kompromittierte. Aus dem öffentlichen Schlüssel B ermittelte Shamir ein Trapdoor-Paar (U', M'). Mit B, M' und U' kann eine superansteigende Menge A' konstruiert werden. Diese wiederum kann anstatt des ursprünglichen Knapsack-Vektors A benutzt werden, um alle Nachrichten zu entschlüsseln, die mit B verschlüsselt wurden.
3. Ein weiterer Angriff auf das Merkle-Hellman System erfolgt mit Hilfe der Gitter-Basis-Reduktion. Hier kann aus dem öffentlichen Schlüssel B und einer gegebenen verschlüsselten Nachricht c die Klartextnachricht p bestimmt werden.

 

Knapsack mit geringer Dichte