www.wikidata.de-de.nina.az

Merkle Hellman Kryptosystem Das MH ist ein 1978 veröffentlichtes asymmetrisches Verschlüsselungsverfahren das auf dem Ru

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 Bearbeiten

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 , für den für alle 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 Bearbeiten

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 , dem Multiplikator und dem Modul erhält man den öffentlichen Schlüssel folgendermaßen:

Dabei sollten der Multiplikator und der Modul 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 Bearbeiten

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 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 im Block, dann werden diese Elemente zum Ergebniswert addiert.

Die Werte ergeben dann den Geheimtext.

Entschlüsselung Bearbeiten

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 in eine Summe von Elementen 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.

Um die zu berechnen, braucht man das Inverse des Multiplikators , so dass . Dieses Inverse lässt sich mit dem erweiterten Euklidischen Algorithmus berechnen.

Der Klartext entsteht dann wieder aus den Bits, die zu den Elementen aus dem privaten Schlüssel korrespondieren und die Summe ergeben.

Beispiel Bearbeiten

Schlüsselerzeugung Bearbeiten

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

Weiterhin werden noch der Multiplikator und der Modulo benötigt.

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

Damit ergibt sich der öffentliche Schlüssel als:

Verschlüsselung Bearbeiten

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.

Nun bestimmt ein Bit aus dem Block , 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

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

Block

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

Der Geheimtext ist dann 174, 280, 333.

Entschlüsselung Bearbeiten

Zum Entschlüsseln eines Geheimtextes brauchen wir den privaten Schlüssel sowie den Multiplikator und den Modul . Aus dem Multiplikator und dem Modul berechnet sich das Inverse . Dies geht mit dem erweiterten Euklidischen Algorithmus. Für die gegebenen Werte von und ergibt sich

Dazu werden einfach die 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 ist. Wenn wir die Liste durch sind, sollte die Summe ergeben. Tut sie das nicht, wurde versucht, den Text mit einem falschen Schlüssel zu entschlüsseln. Die Elemente, die wir von abgezogen haben, werden als gewertet, die, die nicht gebraucht werden, werden dagegen mit gewertet.

Für den Block 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

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

Block

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 Bearbeiten

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 Bearbeiten

  • 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.

Einzelnachweise Bearbeiten

  1. Ralph Merkle, Martin Hellman: Hiding information and signatures in trapdoor knapsacks. In: Information Theory, IEEE Transactions. Vol. 24, No. 5, Sep 1978, S. 525–530. (online auf: ieeexplore.ieee.org)
  2. Adi Shamir: A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem. In: Information Theory, IEEE Transactions Ausgabe. Band 30, Nr. 5, 1984, S. 699–704, doi:10.1109/SFCS.1982.5.
  3. Leonard M. Adleman: On Breaking the Iterated Merkle-Hellman Public-Key Cryptosystem. In: Advances in Cryptology: Proceedings of CRYPTO '82. Plenum Press, 1982, S. 303–308.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Merkle Hellman Kryptosystem MH ist ein 1978 veroffentlichtes asymmetrisches Verschlusselungsverfahren das auf dem Rucksackproblem basiert Es wurde 1983 gebrochen Inhaltsverzeichnis 1 Beschreibung 1 1 Schlusselerzeugung 1 2 Verschlusselung 1 3 Entschlusselung 2 Beispiel 2 1 Schlusselerzeugung 2 2 Verschlusselung 2 3 Entschlusselung 3 Geschichte 4 Literatur 5 EinzelnachweiseBeschreibung BearbeitenDas Merkle Hellman Kryptosystem ist eines der ersten asymmetrischen Verschlusselungsverfahren und wurde von Ralph Merkle und Martin Hellman entwickelt 1 Anders als bei manchen anderen Verschlusselungsverfahren bspw dem RSA Kryptosystem gibt es hier kein analoges Verfahren zur digitalen Signatur Da es sich um ein asymmetrisches Verfahren handelt wird zur Verschlusselung ein offentlicher Schlussel benutzt der von dem zur Entschlusselung benutzten geheimen Schlussel 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 Gegenstanden unterschiedlichen Gewichts die solch ein allgemeines Rucksackproblem beschreiben als offentlicher Schlussel Der geheime Schlussel besteht auch aus einer solchen Menge von Gewichten welche aber ein einfaches Rucksackproblem beschreiben In dem geheimen Schlussel bilden die Gewichte einen stark steigenden Vektor a displaystyle a nbsp fur den a i gt k 1 i 1 a k displaystyle a i gt sum k 1 i 1 a k nbsp fur alle i displaystyle i nbsp gilt Ein so beschriebenes Rucksackproblem ist einfach durch einen Greedy Algorithmus in Linearzeit losbar Der offentliche Schlussel berechnet sich aus dem geheimen Schlussel Schlusselerzeugung Bearbeiten Im Merkle Hellman Kryptosystem sind die Schlussel Mengen aus Gegenstanden mit einem bestimmten Gewicht Der offentliche Schlussel formuliert ein schweres der private ein einfaches Rucksackproblem Kombiniert man den privaten Schlussel 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 gehoren diese beiden Zahlen auch zum privaten Schlussel Diese Transformation gelingt in Polynomialzeit Aus dem privaten Schlussel A displaystyle A nbsp dem Multiplikator n displaystyle n nbsp und dem Modul m displaystyle m nbsp erhalt man den offentlichen Schlussel B displaystyle B nbsp folgendermassen B i A i n mod m displaystyle B i left A i cdot n right mod m nbsp Dabei sollten der Multiplikator n displaystyle n nbsp und der Modul m displaystyle m nbsp teilerfremd sein Am einfachsten erreicht man dies dadurch dass man als Modul eine Primzahl wahlt Ausserdem sollte der Modul eine Zahl sein die grosser ist als die Summe der Elemente des Rucksackes Verschlusselung Bearbeiten Um eine Nachricht zu verschlusseln verwendet man den offentlichen Schlussel Wir nehmen an dass die zu verschlusselnde Nachricht in einem Binarformat vorliegt Diese wird dann in Blocke b i x 1 x B displaystyle b i x 1 ldots x left vert B right vert nbsp geteilt deren Grosse der Grosse der Menge an Gegenstanden im offentlichen Schlussel entspricht Jeder dieser Blocke wird einzeln mit dem offentlichen Schlussel verschlusselt Korrespondiert nun ein Element im Schlussel mit einer 1 displaystyle 1 nbsp im Block dann werden diese Elemente zum Ergebniswert addiert C i k 1 B B k b i k displaystyle C i sum k 1 left vert B right vert B k cdot b i k nbsp Die Werte C i displaystyle C i nbsp ergeben dann den Geheimtext Entschlusselung Bearbeiten Die Entschlusselung ist moglich weil der Multiplikator und der Modul die fur die Erzeugung des offentlichen Schlussels benutzt wurden auch dazu benutzt werden konnen den Geheimtext C i displaystyle C i nbsp in eine Summe von Elementen D i displaystyle D i nbsp des einfachen Rucksackproblems zu transformieren Daraufhin kann dann ein naiver Greedy Algorithmus verwendet werden um zu bestimmen welche Elemente des privaten Schlussels in der Summe vorkommen D i k 1 A A k b i k displaystyle D i sum k 1 left vert A right vert A k cdot b i k nbsp Um die D i displaystyle D i nbsp zu berechnen braucht man das Inverse n 1 displaystyle n 1 nbsp des Multiplikators n displaystyle n nbsp so dass n n 1 1 mod m displaystyle n cdot n 1 equiv 1 mod m nbsp Dieses Inverse lasst sich mit dem erweiterten Euklidischen Algorithmus berechnen D i C i n 1 mod m displaystyle D i left C i cdot n 1 right mod m nbsp Der Klartext entsteht dann wieder aus den Bits die zu den Elementen aus dem privaten Schlussel korrespondieren und die Summe D i displaystyle D i nbsp ergeben Beispiel BearbeitenSchlusselerzeugung Bearbeiten Wahlen eines privaten Schlussels Dieser muss ein stark wachsender Vektor sein A 2 3 6 13 27 52 displaystyle A left 2 3 6 13 27 52 right nbsp Weiterhin werden noch der Multiplikator n displaystyle n nbsp und der Modulo m displaystyle m nbsp benotigt n 31 displaystyle n 31 nbsp m 105 displaystyle m 105 nbsp Nun kann man sich den offentlichen Schlussel berechnen 2 31 mod 105 62 3 31 mod 105 93 6 31 mod 105 81 13 31 mod 105 88 27 31 mod 105 102 52 31 mod 105 37 displaystyle begin aligned left 2 cdot 31 right mod 105 amp 62 left 3 cdot 31 right mod 105 amp 93 left 6 cdot 31 right mod 105 amp 81 left 13 cdot 31 right mod 105 amp 88 left 27 cdot 31 right mod 105 amp 102 left 52 cdot 31 right mod 105 amp 37 end aligned nbsp Damit ergibt sich der offentliche Schlussel als B 62 93 81 88 102 37 displaystyle B left 62 93 81 88 102 37 right nbsp Verschlusselung Bearbeiten Soll ein Text verschlusselt werden so wird dieser in Blocke derselben Lange wie die des Schlussels zerlegt Fur das Beispiel nutzen wir den Text 011000 110101 101110 b 011000110101101110 displaystyle b 011000110101101110 nbsp b 1 011000 displaystyle b 1 011000 nbsp b 2 110101 displaystyle b 2 110101 nbsp b 3 101110 displaystyle b 3 101110 nbsp B 62 93 81 88 102 37 displaystyle B left 62 93 81 88 102 37 right nbsp Nun bestimmt ein Bit aus dem Block b 1 displaystyle b 1 nbsp ob das korrespondierende Element aus dem Schlussel in den Geheimtext einfliesst 0 1 1 0 0 062 93 81 88 102 370 93 81 0 0 0 Summe 174Block b 2 displaystyle b 2 nbsp 1 1 0 1 0 162 93 81 88 102 3762 93 0 88 0 37 Summe 280Block b 3 displaystyle b 3 nbsp 1 0 1 1 1 062 93 81 88 102 3762 0 81 88 102 0 Summe 333Der Geheimtext C displaystyle C nbsp ist dann 174 280 333 Entschlusselung Bearbeiten Zum Entschlusseln eines Geheimtextes brauchen wir den privaten Schlussel sowie den Multiplikator n displaystyle n nbsp und den Modul m displaystyle m nbsp Aus dem Multiplikator und dem Modul berechnet sich das Inverse n 1 displaystyle n 1 nbsp Dies geht mit dem erweiterten Euklidischen Algorithmus Fur die gegebenen Werte von n displaystyle n nbsp und m displaystyle m nbsp ergibt sich n 1 61 displaystyle n 1 61 nbsp n 1 61 displaystyle n 1 61 nbsp 174 61 mod 105 9 displaystyle left 174 cdot 61 right mod 105 9 nbsp 280 61 mod 105 70 displaystyle left 280 cdot 61 right mod 105 70 nbsp 333 61 mod 105 48 displaystyle left 333 cdot 61 right mod 105 48 nbsp D 9 70 48 displaystyle D left 9 70 48 right nbsp Dazu werden einfach die D i displaystyle D i nbsp als Summe von Elementen des privaten Schlussels betrachtet Nun ziehen wir von dieser Summe das grosste Element aus dem Schlussel ab welches kleiner oder gleich der Summe D i displaystyle D i nbsp ist Wenn wir die Liste durch sind sollte die Summe 0 displaystyle 0 nbsp ergeben Tut sie das nicht wurde versucht den Text mit einem falschen Schlussel zu entschlusseln Die Elemente die wir von D i displaystyle D i nbsp abgezogen haben werden als 1 displaystyle 1 nbsp gewertet die die nicht gebraucht werden werden dagegen mit 0 displaystyle 0 nbsp gewertet Fur den Block D 1 displaystyle D 1 nbsp lasst sich der Klartext dann folgendermassen wiederherstellen 2 3 6 13 27 520 3 6 0 0 0 Summe 90 1 1 0 0 0 KlartextBlock D 2 displaystyle D 2 nbsp 2 3 6 13 27 522 3 0 13 0 52 Summe 701 1 0 1 0 1 KlartextBlock D 3 displaystyle D 3 nbsp 2 3 6 13 27 522 0 6 13 27 0 Summe 481 0 1 1 1 0 KlartextDer Klartext lautet also 011000 110101 101110 Geschichte BearbeitenDas 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 2 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 3 Literatur BearbeitenBruce Schneier Applied Cryptography protocols algorithms and source code in C 2 Auflage John Wiley amp Sons New York 1995 ISBN 0 471 11709 9 S 462 466 Einzelnachweise Bearbeiten Ralph Merkle Martin Hellman Hiding information and signatures in trapdoor knapsacks In Information Theory IEEE Transactions Vol 24 No 5 Sep 1978 S 525 530 online auf ieeexplore ieee org Adi Shamir A polynomial time algorithm for breaking the basic Merkle Hellman cryptosystem In Information Theory IEEE Transactions Ausgabe Band 30 Nr 5 1984 S 699 704 doi 10 1109 SFCS 1982 5 Leonard M Adleman On Breaking the Iterated Merkle Hellman Public Key Cryptosystem In Advances in Cryptology Proceedings of CRYPTO 82 Plenum Press 1982 S 303 308 Abgerufen von https de wikipedia org w index php title Merkle Hellman Kryptosystem amp oldid 220488427