Merkle-Hellman-Kryptosystem

Das Merkle-Hellman-Kryptosystem (MH) ist ein asymmetrisches Kryptosystem, basierend auf dem Subset-Sum-Entscheidungsproblem (einem Spezialfall des Rucksackproblems).

Inhaltsverzeichnis

Verschlüsselung

Entschlüsselung

A wählt einen extra simplen Vektor $\vec g$ (bei einem extra simplen Vektor ist der Wert $a_i > \sum_{k=1}^{i-1} a_{k}$ ), auch superwachsende Folge genannt

Entschlüsseln:

A berechnet $w - 1$ mit Hilfe des Euklidischen Algorithmus. Durch Rückverfolgung der einzelnen Zeilen kann man $w - 1$ ermitteln. $w - 1$ ist dann der Multiplikator von w.

Es wird $s'$ berechnet: $s' = w - 1 * s$
Der Knapsack kann einfach gelöst werden (da $\vec g$ extra simpel). $K((\vec g ),s'))$

$n=6, \vec g=(3,5,11,20,41,83), k=170, w=73$

$a i = 73 * g i mod 170$

z.B.: $a 1 = 73 * 3mod 170$

$\Rightarrow \ \vec a =(49,25,123,100,103,109)$

Es soll die Nachricht $\vec x =(0,1,0,1,0,0)$ gesendet werden. Dazu wird berechnet:

$s = 49 * 0 + 25 * 1 + 123 * 0 + 100 * 1 + 103 * 0 + 109 * 0 = 125$

Es wird also $s = 125$ an den Empfänger geschickt

Euklidischer Algorithmus:

$k=170; w=73; n=6; \vec g= ($

$170 = 73 * 2 + 24$

$73 = 24 * 3 + 1$ ... 1 ist der ggT

$24 = 1 * 24 + 0$

Rückverfolgung:

$1 = 73 - 24 * 3$

$1 = 73 - (170 - 73 * 2) * 3$

$1 = 73 - (170 * 3 - 73 * 6)$

$1 = 73 * 7 - 170 * 3$

Daraus folgt: $w - 1 = 7$

außerdem ist $s' = w - 1 * s mod k = 7 * 125mod 170 = 25$

Danach muss eine Lösung zu $K ((3,5,11,20,41,83),25)$ gefunden werden, daher ergibt sich das Nachrichtenwort $\vec x = (0,1,0,1,0,0)$

Lösung des Problems $K((a_1,\dots,a_n), m):$

Ist $a n < m$ , dann ist Lösung $\vec x$ an der Stelle $n$ gleich $1$ . Fahre mit $m - a n$ und $a n - 1$ fort, bis $m = 0$ .

Andernfalls ist Lösung $\vec x$ an der Stelle $n$ gleich $0$ . Fahre mit $m$ und $a n - 1$ fort, bis $m = 0$ .

Das auch unter dem Namen Knapsack bekannte Verfahren wurde 1978 von Ralph Merkle und Martin Hellman erfunden. Es schien sich als Konkurrenz zu RSA und dem Diffie-Hellman-Algorithmus zu etablieren, wurde aber 1983 von Adi Shamir und Richard Zippel in Theorie und Praxis (auf einem Apple II) gebrochen.