Der Merkle-Hellman Rucksack cryptosystem war einer des frühsten öffentlichen Schlüssels cryptosystems erfunden von Ralph Merkle und Martin Hellman 1978. Obwohl seine Ideen elegant, und viel einfacher sind als RSA, ist er gebrochen worden.

Beschreibung

Merkle-Hellman ist ein asymmetrischer Schlüssel cryptosystem, bedeutend, dass für die Kommunikation zwei Schlüssel erforderlich sind: ein öffentlicher Schlüssel und ein privater Schlüssel. Außerdem, verschieden von RSA, ist es Einweg-— der öffentliche Schlüssel wird nur für die Verschlüsselung verwendet, und der private Schlüssel wird nur für die Dekodierung verwendet. So ist es für die Beglaubigung durch das kryptografische Unterzeichnen unbrauchbar.

Das Merkle-Hellman System basiert auf dem Teilmenge-Summe-Problem (ein spezieller Fall des Rucksack-Problems). Das Problem ist wie folgt: In Anbetracht einer Reihe von Zahlen und einer Nummer b, finden Sie eine Teilmenge dessen, der zu b resümiert. Im Allgemeinen, wie man bekannt, ist dieses Problem NP-complete. Jedoch, wenn der Satz von Zahlen (hat den Rucksack genannt), superzunimmt — d. h. ist jedes Element des Satzes größer als die Summe aller Zahlen davor — das Problem ist 'leicht' und in der polynomischen Zeit mit einem einfachen gierigen Algorithmus lösbar.

Schlüsselgeneration

In Merkle-Hellman sind die Schlüssel Rucksäcke. Der öffentliche Schlüssel ist ein 'harter' Rucksack, und der private Schlüssel ist ein 'leichter', oder Supererhöhung, Rucksack, der mit zwei zusätzlichen Zahlen, einem Vermehrer und einem Modul verbunden ist, die verwendet wurden, um den superzunehmenden Rucksack in den harten Rucksack umzuwandeln. Diese dieselben Zahlen werden verwendet, um die Summe der Teilmenge des harten Rucksacks in die Summe der Teilmenge des leichten Rucksacks umzugestalten, der in der polynomischen Zeit lösbar ist.

Verschlüsselung

Zu encrypt eine Nachricht wird eine Teilmenge des harten Rucksacks durch das Vergleichen davon mit einer Reihe Bit (der plaintext) gleich in der Länge zum Schlüssel und das Bilden jedes Begriffes im öffentlichen Schlüssel gewählt, der 1 im plaintext ein Element der Teilmenge entspricht, während er die Begriffe entsprechend 0 Begriffen im plaintext ignoriert. Die Elemente dieser Teilmenge werden zusammen hinzugefügt, und die resultierende Summe ist der cyphertext.

Dekodierung

Dekodierung ist möglich, weil der Vermehrer und das Modul gepflegt haben sich zu verwandeln, kann der leichte, superzunehmende Rucksack in den öffentlichen Schlüssel auch verwendet werden, um die Zahl umzugestalten, die den ciphertext in die Summe der entsprechenden Elemente des superzunehmenden Rucksacks vertritt. Dann, mit einem einfachen gierigen Algorithmus, kann der leichte Rucksack mit O (n) arithmetische Operationen gelöst werden, der die Nachricht entschlüsselt.

Mathematische Methode

Schlüsselgeneration

Zu encrypt N-Bit-Nachrichten, wählen Sie eine superzunehmende Folge

:w = (w, w..., w)

n natürlicher Nichtnullzahlen. Picken Sie eine zufällige ganze Zahl q, solch dass auf

:

und eine zufällige ganze Zahl, r, solch dass gcd (r, q) = 1 (d. h. r und q sind coprime).

q wird diese Weise gewählt, die Einzigartigkeit des ciphertext zu sichern. Wenn es etwas kleiner ist, kann mehr als ein plaintext encrypt zu demselben ciphertext. r muss coprime zu q sein, oder es kein Gegenteil mod q haben wird. Die Existenz des Gegenteils von r ist notwendig, so dass Dekodierung möglich ist.

Berechnen Sie jetzt die Folge

:β = (β, β..., β)

wo

:β = rw mod q.

Der öffentliche Schlüssel ist β, während der private Schlüssel (w, q, r) ist.

Verschlüsselung

Zu encrypt eine N-Bit-Nachricht

:α = (α, α..., α),

wo das i-th Bit der Nachricht und {0, 1} ist, berechnen Sie

:

Das Kryptogramm ist dann c.

Dekodierung

Um einen ciphertext c zu entschlüsseln, muss ein Empfänger die Nachrichtenbit α solch finden, dass sie befriedigen

:

Das würde ein hartes Problem sein, wenn die β zufällige Werte wären, weil der Empfänger ein Beispiel des Teilmenge-Summe-Problems würde lösen müssen, das, wie man bekannt, NP-hard ist. Jedoch wurden die Werte β solch gewählt, dass Dekodierung leicht ist, wenn der private Schlüssel (w, q, r) bekannt ist.

Der Schlüssel zur Dekodierung ist, eine ganze Zahl s zu finden, der das Modulgegenteil von r modulo q ist. Das bedeutet, dass s die Gleichung s r mod q = 1 befriedigt oder gleichwertig dort bestehen Sie eine ganze Zahl k solch dass sr = kq + 1. Seitdem r solch gewählt wurde, dass gcd (r q) =1 es möglich ist, s und k durch das Verwenden des Verlängerten Euklidischen Algorithmus zu finden. Als nächstes schätzt der Empfänger des ciphertext c

:

Folglich

:

Wegen rs mod q = 1 und β = rw mod folgt q

:Folglich:

Die Summe aller Werte w ist kleiner als q und ist folglich auch im Zwischenraum [0, q-1].

So muss der Empfänger das Teilmenge-Summe-Problem beheben

:

Dieses Problem ist leicht, weil w eine superzunehmende Folge ist.

Nehmen Sie das größte Element in w, sagen Sie w. Wenn w> c', dann α = 0, wenn wc', dann α = 1. Dann ziehen Sie w×α von c ab', und wiederholen Sie diese Schritte, bis Sie α ausgerechnet haben.

Beispiel

Erstens wird eine superzunehmende Folge w geschaffen

w = {2, 7, 11, 21, 42, 89, 180, 354 }\

Das ist die Basis für einen privaten Schlüssel. Davon, berechnen Sie die Summe.

:

Dann wählen Sie eine Nummer q, die größer ist als die Summe.

Wählen Sie außerdem eine Nummer r, die in der Reihe ist und coprime zu q ist.

Der private Schlüssel besteht aus q, w und r.

Um einen öffentlichen Schlüssel zu berechnen, erzeugen Sie die Folge β, indem Sie jedes Element in w durch r mod q multiplizieren

β = {295, 592, 301, 14, 28, 353, 120, 236 }\

weil

2 * 588 mod 881 = 295

7 * 588 mod 881 = 592

11 * 588 mod 881 = 301

21 * 588 mod 881 = 14

42 * 588 mod 881 = 28

89 * 588 mod 881 = 353

180 * 588 mod 881 = 120

354 * 588 mod 881 = 236

Die Folge β setzt den öffentlichen Schlüssel zusammen.

Sagen Sie, dass Alice zu encrypt "a" wünscht. Erstens muss sie "a" zum binären übersetzen (in diesem Fall, mit ASCII oder UTF-8)

01100001

Sie multipliziert jedes jeweilige Bit mit der entsprechenden Zahl in β\

0 * 295

+ 1 * 592

+ 1 * 301

+ 0 * 14

+ 0 * 28

+ 0 * 353

+ 0 * 120

+ 1 * 236

= 1129

Sie sendet das dem Empfänger.

Um zu entschlüsseln, bewegen Sie sich Auf und ab multipliziert 1129 mit r mod </Code> (Sieh Modulgegenteil)

Jetzt zersetzt sich Bob 372, indem er das größte Element in w auswählt, der weniger ist als oder gleich 372. Dann das folgende größte Element weniger auswählend, als oder gleich dem Unterschied bis ist der Unterschied:

Die Elemente, die wir von unserem privaten Schlüssel ausgewählt haben, entsprechen dem 1 Bit in der Nachricht

Wenn übersetzt, zurück von der Dualzahl ist dieser "a" die entschlüsselte Endnachricht.