www.wikidata.de-de.nina.az

Merkles Puzzle ist das erste Schlüsselaustauschprotokoll bei dem die beiden Parteien nicht bereits einen geheimen Schlüs

Merkles Puzzle

Merkles Puzzle ist das erste Schlüsselaustauschprotokoll, bei dem die beiden Parteien nicht bereits einen geheimen Schlüssel mit der jeweils anderen oder einer dritten Partei teilen müssen. Es wurde im Jahr 1974 von Ralph Merkle entdeckt, aber erst 1978 veröffentlicht. Die Existenz eines solchen Protokolls wurde lange für unmöglich gehalten, und seine Entdeckung kann als Beginn der Public-Key-Kryptographie gesehen werden.

Beschreibung Bearbeiten

Alice und Bob einigen sich zunächst auf ein symmetrisches Verschlüsselungsverfahren und eine Schlüssellänge , die so gewählt wird, dass eine mit und Bit langem Schlüssel verschlüsselte Nachricht mit realistischem, aber nicht zu kleinem Aufwand entziffert werden kann. Dann erzeugt Alice zufällige Schlüssel der Länge Bit, und sie legt eine Tabelle mit zufälligen Schlüsseln an, die ausreichend lang sind, um keine Entzifferung zu erlauben (128 Bit oder mehr). Sie verschlüsselt mit jedem Schlüssel den Tabelleneintrag zusammen mit seinem Tabellenindex . Die so erzeugten Chiffrate mit sendet sie in zufälliger Reihenfolge an Bob.

Bob wählt zufällig eines der Chiffrate aus und entziffert es, indem er alle möglichen Schlüssel der Länge durchprobiert. Dafür braucht er höchstens Versuche, im Mittel . Er merkt sich den Schlüssel und sendet den Index zurück an Alice. Damit haben die beiden den gemeinsamen Schlüssel vereinbart, mit dem sie nun z. B. mit einer symmetrischen Verschlüsselung, evtl. mit dem gleichen Verfahren wie oben, Nachrichten austauschen können.

In der Praxis müssen die Chiffrate auch redundante Information enthalten, damit Bob das richtige Dechiffrat erkennen kann. Alice könnte beispielsweise einen Text ausreichender Länge wählen und an alle Tabelleneinträge anhängen. wird im Klartext zusammen mit den Chiffraten an Bob gesendet. Oder man macht das Feld für den Index genügend groß (ausreichend für Zahlen bis über ), dann kann Bob einen falschen Schlüssel daran erkennen, dass ein Index größer als herauskommt.

Sicherheit Bearbeiten

Ein Angreifer, der die Kommunikation der beiden belauscht, sieht zuerst die Chiffrate, die Alice an Bob schickt, dann den Index, den Bob zurückschickt, der aber von der Reihenfolge, in der die Chiffrate gesendet wurden, unabhängig ist. Es bleibt ihm also nichts anderes übrig, als so lange Chiffrate zu entziffern, bis er dasjenige findet, das den Index enthält. Dafür muss er im Mittel Chiffrate entziffern. Bei jeweils Versuchen, den richtigen Schlüssel zu finden, braucht er insgesamt im Mittel Versuche. Wenn gewählt wurde, ist seine Laufzeit also quadratisch in der von Alice und Bob.

Angenommen, Bob kann pro Sekunde Schlüssel durchprobieren. Dann braucht er bei maximal eine, im Mittel 1/2 Sekunde, um ein Chiffrat zu entziffern. Ein Angreifer mit derselben Rechenleistung bräuchte bei jedoch im Durchschnitt drei Monate. Allerdings kann ein Angreifer den Schlüssel mit Glück auch deutlich früher erraten.

In der theoretischen Kryptologie wird heutzutage in der Regel angenommen, dass die Laufzeit des Angreifers polynomial in einem Sicherheitsparameter ist. Nach dieser Definition reicht ein quadratischer Unterschied in der Laufzeit zwischen den Benutzern und dem Angreifer nicht aus, der Angreifer könnte alle Chiffrate durchprobieren. Das Verfahren ist in einem solchen Modell also nicht sicher.

Einzelnachweise Bearbeiten

  1. Ralph Merkle: Secure Communications over Insecure Channels. In: Communications of the ACM. Band 21, Nr. 4, April 1978, S. 294–299, doi:10.1145/359460.359473.

Weblinks Bearbeiten

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:
Merkles Puzzle ist das erste Schlusselaustauschprotokoll bei dem die beiden Parteien nicht bereits einen geheimen Schlussel mit der jeweils anderen oder einer dritten Partei teilen mussen Es wurde im Jahr 1974 von Ralph Merkle entdeckt aber erst 1978 veroffentlicht 1 Die Existenz eines solchen Protokolls wurde lange fur unmoglich gehalten und seine Entdeckung kann als Beginn der Public Key Kryptographie gesehen werden Inhaltsverzeichnis 1 Beschreibung 2 Sicherheit 3 Einzelnachweise 4 WeblinksBeschreibung BearbeitenAlice und Bob einigen sich zunachst auf ein symmetrisches Verschlusselungsverfahren E displaystyle E nbsp und eine Schlussellange n displaystyle n nbsp die so gewahlt wird dass eine mit E displaystyle E nbsp und n displaystyle n nbsp Bit langem Schlussel verschlusselte Nachricht mit realistischem aber nicht zu kleinem Aufwand entziffert werden kann Dann erzeugt Alice m displaystyle m nbsp zufallige Schlussel k 0 k m 1 displaystyle k 0 cdots k m 1 nbsp der Lange n displaystyle n nbsp Bit und sie legt eine Tabelle mit m displaystyle m nbsp zufalligen Schlusseln K 0 K m 1 displaystyle K 0 cdots K m 1 nbsp an die ausreichend lang sind um keine Entzifferung zu erlauben 128 Bit oder mehr Sie verschlusselt mit jedem Schlussel k i displaystyle k i nbsp den Tabelleneintrag K i displaystyle K i nbsp zusammen mit seinem Tabellenindex i displaystyle i nbsp Die so erzeugten Chiffrate E k i K i i displaystyle E k i K i i nbsp mit i 0 1 m 1 displaystyle i 0 1 cdots m 1 nbsp sendet sie in zufalliger Reihenfolge an Bob Bob wahlt zufallig eines der Chiffrate aus und entziffert es indem er alle moglichen Schlussel der Lange n displaystyle n nbsp durchprobiert Dafur braucht er hochstens 2 n displaystyle 2 n nbsp Versuche im Mittel 2 n 2 displaystyle 2 n 2 nbsp Er merkt sich den Schlussel K i displaystyle K i nbsp und sendet den Index i displaystyle i nbsp zuruck an Alice Damit haben die beiden den gemeinsamen Schlussel K i displaystyle K i nbsp vereinbart mit dem sie nun z B mit einer symmetrischen Verschlusselung evtl mit dem gleichen Verfahren E displaystyle E nbsp wie oben Nachrichten austauschen konnen In der Praxis mussen die Chiffrate auch redundante Information enthalten damit Bob das richtige Dechiffrat erkennen kann Alice konnte beispielsweise einen Text T displaystyle T nbsp ausreichender Lange wahlen und an alle Tabelleneintrage anhangen T displaystyle T nbsp wird im Klartext zusammen mit den Chiffraten E k i K i i T displaystyle E k i K i i T nbsp an Bob gesendet Oder man macht das Feld fur den Index i displaystyle i nbsp genugend gross ausreichend fur Zahlen bis uber m 2 displaystyle m 2 nbsp dann kann Bob einen falschen Schlussel daran erkennen dass ein Index grosser als m 1 displaystyle m 1 nbsp herauskommt Sicherheit BearbeitenEin Angreifer der die Kommunikation der beiden belauscht sieht zuerst die m displaystyle m nbsp Chiffrate die Alice an Bob schickt dann den Index den Bob zuruckschickt der aber von der Reihenfolge in der die Chiffrate gesendet wurden unabhangig ist Es bleibt ihm also nichts anderes ubrig als so lange Chiffrate zu entziffern bis er dasjenige findet das den Index i displaystyle i nbsp enthalt Dafur muss er im Mittel m 2 displaystyle m 2 nbsp Chiffrate entziffern Bei jeweils 2 n 2 displaystyle 2 n 2 nbsp Versuchen den richtigen Schlussel k i displaystyle k i nbsp zu finden braucht er insgesamt im Mittel m 2 n 4 displaystyle m cdot 2 n 4 nbsp Versuche Wenn m 2 n displaystyle m 2 n nbsp gewahlt wurde ist seine Laufzeit also quadratisch in der von Alice und Bob Angenommen Bob kann pro Sekunde 2 25 displaystyle 2 25 nbsp Schlussel durchprobieren Dann braucht er bei n 25 displaystyle n 25 nbsp maximal eine im Mittel 1 2 Sekunde um ein Chiffrat zu entziffern Ein Angreifer mit derselben Rechenleistung brauchte bei m 2 25 displaystyle m 2 25 nbsp jedoch im Durchschnitt drei Monate Allerdings kann ein Angreifer den Schlussel mit Gluck auch deutlich fruher erraten In der theoretischen Kryptologie wird heutzutage in der Regel angenommen dass die Laufzeit des Angreifers polynomial in einem Sicherheitsparameter ist Nach dieser Definition reicht ein quadratischer Unterschied in der Laufzeit zwischen den Benutzern und dem Angreifer nicht aus der Angreifer konnte alle Chiffrate durchprobieren Das Verfahren ist in einem solchen Modell also nicht sicher Einzelnachweise Bearbeiten Ralph Merkle Secure Communications over Insecure Channels In Communications of the ACM Band 21 Nr 4 April 1978 S 294 299 doi 10 1145 359460 359473 Weblinks BearbeitenRalph Merkle Secure Communications over Insecure Channels 1974 Paper und Interview mit Ralph Merkle Ralph Merkle 1974 project Publishing a new idea Geschichte der Entdeckung und Scan der Ideenskizze Abgerufen von https de wikipedia org w index php title Merkles Puzzle amp oldid 235451777