Merkle-Hellman

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

Anwendung

B möchte an A eine verschlüsselte Nachricht senden

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

• A wählt ein beliebiges k, wobei $k>\sum_{i=1}^n g_{i}$

• A wählt ein w mit der Eigenschaft: $\operatorname{ggT}(k,w)=1$

• A berechnet a_i = w * g_imod k für i = 1,...,n

• A gibt $\vec a = (a_1,...,a_n)$ öffentlich bekannt

• Die Nachricht N wird binärkodiert und in Blöcke der Größe n eingeteilt

• Ein Block (x₁,...,x_n) wird verschlüsselt: $s=\sum_{i=1}^n a_{i} * x_{i}$
• s wird an den Empfänger gesendet.

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'))$

Beispiel

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

a_i = 73 * g_imod 170

z.B.: a₁ = 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

Entschlüsseln mit Euklidischen Algorithmus mit Rückverfolgung:

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} * smod 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 \leq 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.

Geschichte

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.