Merkles Puzzle

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Merkles Puzzle ist der Name des ersten Schlüsselaustauschprotokolls, 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.[1] 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]

Wenn Alice mit Bob einen Schlüssel austauschen möchte, legt sie zuerst eine Tabelle mit m zufälligen Schlüsseln K_i der gewünschten Länge an. Für ein gegebenes symmetrisches Verschlüsselungsverfahren E wählt sie nun m zufällige Schlüssel k_i mit einer nicht zu großen Länge von n Bit und verschlüsselt mit jedem dieser Schlüssel einen Tabelleneintrag zusammen mit seinem Index in der Tabelle. Die m Chiffrate E_{k_i}(i, K_i) sendet sie in zufälliger Reihenfolge an Bob.

Bob wählt ein zufälliges Chiffrat aus und probiert alle möglichen Schlüssel aus, bis er richtig rät und das Chiffrat entschlüsseln kann. Dafür braucht er höchstens 2^n Versuche. Er merkt sich den Schlüssel K und sendet den Index i zurück an Alice, die damit weiß, welchen Schlüssel Bob benutzt.

Sicherheit[Bearbeiten]

Ein Angreifer, der die Kommunikation der beiden belauscht, sieht zuerst die m 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 knacken, bis er dasjenige findet, das den Index i enthält. Dafür braucht er m \cdot 2^n Versuche, bei m = 2^n ist seine Laufzeit also quadratisch in der von Alice und Bob.

Angenommen, Bob kann pro Sekunde 2^{25} Schlüssel durchprobieren. Dann braucht er bei m = 2^{25} und  n = 25 weniger als eine Sekunde, um ein Chiffrat zu knacken, ein Angreifer mit derselben Rechenleistung jedoch im Durchschnitt ein halbes Jahr.

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. 21, Nr. 4, April 1978, S. 294–299, doi:10.1145/359460.359473.

Weblinks[Bearbeiten]