Merkle-Hellman-Kryptosystem

Das Merkle-Hellman-Kryptosystem (MH) ist ein 1978 veröffentlichtes, asymmetrisches Verschlüsselungsverfahren, das auf dem Rucksackproblem basiert. Es wurde 1983 gebrochen.

Beschreibung

Das Merkle-Hellman-Kryptosystem ist eines der ersten asymmetrischen Verschlüsselungsverfahren und wurde von Ralph Merkle und Martin Hellman entwickelt. Anders als bei manchen anderen Verschlüsselungsverfahren (bspw. dem RSA-Kryptosystem) gibt es hier kein analoges Verfahren zur digitalen Signatur. Da es sich um ein asymmetrisches Verfahren handelt, wird zur Verschlüsselung ein öffentlicher Schlüssel benutzt, der von dem zur Entschlüsselung benutzten geheimen Schlüssel verschieden ist.

Das Merkle-Hellman-Kryptosystem basiert auf dem Rucksackproblem. Da das allgemeine Rucksackproblem ein NP-schweres Problem ist, eignet es sich, um daraus eine Einwegfunktion zu konstruieren. Dabei dient eine Menge aus Gegenständen unterschiedlichen Gewichts, die solch ein allgemeines Rucksackproblem beschreiben, als öffentlicher Schlüssel. Der geheime Schlüssel besteht auch aus einer solchen Menge von Gewichten, welche aber ein einfaches Rucksackproblem beschreiben. In dem geheimen Schlüssel bilden die Gewichte einen stark steigenden Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} , für den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i > \sum_{k=1}^{i-1} a_{k}} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} gilt. Ein so beschriebenes Rucksackproblem ist einfach durch einen Greedy-Algorithmus in Linearzeit lösbar. Der öffentliche Schlüssel berechnet sich aus dem geheimen Schlüssel.

Schlüsselerzeugung

Im Merkle-Hellman-Kryptosystem sind die Schlüssel Mengen aus Gegenständen mit einem bestimmten Gewicht. Der öffentliche Schlüssel formuliert ein 'schweres', der private ein 'einfaches' Rucksackproblem. Kombiniert man den privaten Schlüssel mit zwei Zahlen, dem Multiplikator und dem Modul, kann man aus dem einfachen Rucksackproblem ein schweres konstruieren. Da diese beiden Zahlen auch gebraucht werden, um aus dem schweren Problem das einfache zu gewinnen, gehören diese beiden Zahlen auch zum privaten Schlüssel. Diese Transformation gelingt in Polynomialzeit.

Aus dem privaten Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} , dem Multiplikator $n$ und dem Modul Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} erhält man den öffentlichen Schlüssel $B$ folgendermaßen: $B_{i}=\left(A_{i}\cdot n\right)\mod {m}$

Dabei sollten der Multiplikator Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} und der Modul Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} teilerfremd sein. Am einfachsten erreicht man dies dadurch, dass man als Modul eine Primzahl wählt. Außerdem sollte der Modul eine Zahl sein, die größer ist als die Summe der Elemente des Rucksackes.

Verschlüsselung

Um eine Nachricht zu verschlüsseln, verwendet man den öffentlichen Schlüssel. Wir nehmen an, dass die zu verschlüsselnde Nachricht in einem Binärformat vorliegt. Diese wird dann in Blöcke Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{i} = (x_{1}, \ldots, x_{\left\vert B \right\vert})} geteilt, deren Größe der Größe der Menge an Gegenständen im öffentlichen Schlüssel entspricht. Jeder dieser Blöcke wird einzeln mit dem öffentlichen Schlüssel verschlüsselt. Korrespondiert nun ein Element im Schlüssel mit einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} im Block, dann werden diese Elemente zum Ergebniswert addiert.

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle C_{i}=\sum _{k=1}^{\left\vert B\right\vert }B_{k}\cdot {b_{i}}_{k}}

Die Werte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C_{i}} ergeben dann den Geheimtext.

Entschlüsselung

Die Entschlüsselung ist möglich, weil der Multiplikator und der Modul, die für die Erzeugung des öffentlichen Schlüssels benutzt wurden, auch dazu benutzt werden können, den Geheimtext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C_{i}} in eine Summe von Elementen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i}} des einfachen Rucksackproblems zu transformieren. Daraufhin kann dann ein naiver Greedy-Algorithmus verwendet werden, um zu bestimmen, welche Elemente des privaten Schlüssels in der Summe vorkommen.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i} = \sum_{k=1}^{\left\vert A \right\vert} A_{k} \cdot {b_{i}}_{k} }

Um die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i}} zu berechnen, braucht man das Inverse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{-1}} des Multiplikators $n$, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \cdot n^{-1} \equiv 1 \mod{m}} . Dieses Inverse lässt sich mit dem erweiterten Euklidischen Algorithmus berechnen.

$D_{i}=\left(C_{i}\cdot n^{-1}\right)\mod {m}$

Der Klartext entsteht dann wieder aus den Bits, die zu den Elementen aus dem privaten Schlüssel korrespondieren und die Summe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i}} ergeben.

Beispiel

Schlüsselerzeugung

Wählen eines privaten Schlüssels. Dieser muss ein stark wachsender Vektor sein.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A = \left\{ 2, 3, 6, 13, 27, 52 \right\} }

Weiterhin werden noch der Multiplikator Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} und der Modulo $m$ benötigt.

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle n=31}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m = 105 }

Nun kann man sich den öffentlichen Schlüssel berechnen:

${\begin{aligned}\left(2\cdot 31\right)\mod {105}&=62\\\left(3\cdot 31\right)\mod {105}&=93\\\left(6\cdot 31\right)\mod {105}&=81\\\left(13\cdot 31\right)\mod {105}&=88\\\left(27\cdot 31\right)\mod {105}&=102\\\left(52\cdot 31\right)\mod {105}&=37\\\end{aligned}}$

Damit ergibt sich der öffentliche Schlüssel als:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B = \left\{ 62, 93, 81, 88, 102, 37 \right\} }

Verschlüsselung

Soll ein Text verschlüsselt werden, so wird dieser in Blöcke derselben Länge wie die des Schlüssels zerlegt. Für das Beispiel nutzen wir den Text 011000 110101 101110.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b = 011000 110101 101110 }

$b_{1}=011000$

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{2} = 110101 }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{3} = 101110 }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B = \left\{ 62, 93, 81, 88, 102, 37 \right\} }

Nun bestimmt ein Bit aus dem Block Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{1}} , ob das korrespondierende Element aus dem Schlüssel in den Geheimtext einfließt:

0	1	1	0	0	0
62	93	81	88	102	37
0	93	81	0	0	0	Summe: 174

Block Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{2}}

1	1	0	1	0	1
62	93	81	88	102	37
62	93	0	88	0	37	Summe: 280

Block Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{3}}

1	0	1	1	1	0
62	93	81	88	102	37
62	0	81	88	102	0	Summe: 333

Der Geheimtext $C$ ist dann 174, 280, 333.

Entschlüsselung

Zum Entschlüsseln eines Geheimtextes brauchen wir den privaten Schlüssel sowie den Multiplikator Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} und den Modul Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} . Aus dem Multiplikator und dem Modul berechnet sich das Inverse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{-1}} . Dies geht mit dem erweiterten Euklidischen Algorithmus. Für die gegebenen Werte von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ergibt sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{-1} = 61}

$n^{-1}=61$

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left( 174 \cdot 61 \right) \mod{105} = 9 }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left( 280 \cdot 61 \right) \mod{105} = 70 }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left( 333 \cdot 61 \right) \mod{105} = 48 }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D = \left\{ 9, 70, 48 \right\} }

Dazu werden einfach die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i}} als Summe von Elementen des privaten Schlüssels betrachtet. Nun ziehen wir von dieser Summe das größte Element aus dem Schlüssel ab, welches kleiner oder gleich der Summe $D_{i}$ ist. Wenn wir die Liste durch sind, sollte die Summe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} ergeben. Tut sie das nicht, wurde versucht, den Text mit einem falschen Schlüssel zu entschlüsseln. Die Elemente, die wir von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{i}} abgezogen haben, werden als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} gewertet, die, die nicht gebraucht werden, werden dagegen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} gewertet.

Für den Block Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{1}} lässt sich der Klartext dann folgendermaßen wiederherstellen:

2	3	6	13	27	52
0	3	6	0	0	0	Summe: 9
0	1	1	0	0	0	Klartext

Block Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{2}}

2	3	6	13	27	52
2	3	0	13	0	52	Summe: 70
1	1	0	1	0	1	Klartext

Block Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_{3}}

2	3	6	13	27	52
2	0	6	13	27	0	Summe: 48
1	0	1	1	1	0	Klartext

Der Klartext lautet also 011000 110101 101110.

Geschichte

Das auch unter dem Namen Knapsack-Algorithmus 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. Selbst ein iteriertes Verfahren, bei dem die Gewichte mehrfach mit unterschiedlichen Paaren von Multiplikatoren und Moduln transformiert werden, um das 'schwierige' Rucksackproblem zu generieren, kann erfolgreich mit polynomialem Aufwand angegriffen werden.

Literatur

• Bruce Schneier: Applied Cryptography: protocols, algorithms, and source code in C. 2. Auflage. John Wiley & Sons, New York 1995, ISBN 0-471-11709-9, S. 462–466.