Solitaire-Verschlüsselung und Schlüsselstromerzeugung (Beschreibung)(Menü Ver-/Entschlüsseln \ Symmetrisch (klassisch))

Die Beschreibung des zugehörigen Dialoges findet sich hier.

Solitaire ist ein typisches symmetrisches Papier- und Bleistift-(Paper&Pencil-)Verschlüsselungsverfahren. Es wurde dadurch bekannt, dass Neal Stephenson diesen Algorithmus in seinem Roman "Cryptonomicon" benutzt hat.
Entwickelt wurde es von Bruce Schneier. Der Algorithmus weist eine hohe Sicherheit auf, sofern die Schlüsselerzeugung durch ein gut und zufällig gemischtes Kartenspiel erfolgt und sofern jeder Schlüssel (dieses gemischte Initialdeck) nur ein einziges Mal verwendet wird.

Der Schlüssel in diesem Verfahren ist das gemischte Kartendeck, das sowohl Sender wie Empfänger in einer identischen Mischreihenfolge haben müssen.
Der eigentliche Solitaire-Algorithmus beschreibt, wie sich aus dem Schlüssel (Initialdeck, Bridge-Kartenspiel) ein relativ zufälliger Schlüsselstrom erzeugt wird.
Dieser Schlüsselstrom wird dann zeichenweise entweder mit dem Klartext oder mit dem Ciphertext mittels einer einfachen Modulo-Operation verbunden (insofern basiert das Solitaire-Verfahren auf der Idee des One-Time-Pad, auch wenn der Schlüsselstrom natürlich nicht völlig zufällig ist).

Das Solitaire-Verfahren nutzt Ideen aus dem Vernam-Verfahren (Klartext mit dem Schlüsselstrom XOR-verknüpfen) und den Stromchiffren (aus einem Initialwert wird der Schlüsselstrom erzeugt). Der Zufall liegt also ausschließlich in dem Initialdeck.

Der eigentliche Solitaire-Algorithmus zur Schlüsselstromerzeugung besteht - wie unten genauer beschrieben ist - aus 5 Schritten: die ersten 4 Schritte permutieren das zuletzt erzeugte Abschlussdeck, wobei Schritt 1 und 2 nur jeweils die Karte des Jokers umsortiert, während in Schritt 3 und 4 ganze Kartenstapel vertauscht werden. Schritt 5 findet den Wert des nächsten Schlüsselstromzeichens, ändert aber nichts mehr an der Reihenfolge des aktuellen Abschlussdecks. Manchmal werden die zuletzt erreichten Kartenreihenfolgen auch als Zwischendecks bezeichnet und nur das letzte Zwischendeck wird Abschlussdeck genannt.
Im Standardfall enthalten Initial- und Abschlussdeck eine Permutation der Zahlenwerte 1 bis 54. Der Schlüsselstrom besteht „nur“ aus den Zahlen 1 bis 52 und hat die gleiche Länge wie die verschlüsselnde Datei.

Verschlüsseln mit Solitaire

Voraussetzung für die Verschlüsselung ist, dass ein Schlüsselstrom vorliegt, dessen Länge der Länge des Klartextes entspricht. Er besteht aus einer Folge von Zahlen zwischen 1 und 26.

Der Klartext wird zunächst in Gruppen mit jeweils fünf Buchstaben aufgeteilt (alle Nicht-Buchstabenzeichen werden weggelassen). Anschließend werden die einzelnen Klartextzeichen in Zahlenwerte zwischen 1 und 26 (A entspricht 1, B entspricht 2, C entspricht 3, … und Z entspricht 26) umgewandelt und anschließend modulo 26 mit den Schlüsselstromzahlen addiert [Da das Ergebnis bei der Rechnung modulo 26 zwischen 0 und 25 (einschließlich) liegt, wird der Wert 0 als 26 interpretiert und damit Z zugeordnet.]. Der durch das Rückkonvertieren des neuen Zahlenstroms in einen Buchstabenstrom enstandene Text ist der Geheimtext.

Entschlüsseln mit Solitaire

Da es sich bei Solitaire um ein symmetrisches Verschlüsselungsverfahren handelt, benutzt man sowohl zum Entschlüsseln als auch zum Verschlüsseln einen identischen Schlüssel bzw. Schlüsselstrom.

Zur Entschlüsselung wird auch der Geheimtext in Gruppen zu fünf Buchstaben (wie oben beim Klartext) aufgeteilt. Anschließend wird der Buchstabenstrom in einen Zahlenstrom umgewandelt. Zum Abschluss subtrahiert man modulo 26 die Schlüsselstromzahlen von den Chiffretextzahlen. Der sich ergebende Zahlenstrom muss nur noch in einen Buchstabenstrom konvertiert werden, um den Klartext zu erhalten.

Bemerkung:
Es empfiehlt sich, dass der Empfänger immer ein Ersatz-Initialdeck dabei hat, denn bei der Schlüsselstromerzeugung ändert er das Initialdeck. Macht er dabei einen Fehler, ist er nicht mehr in der Lage ist, neu aufzusetzen. Und somit kann er die Nachricht nicht mehr entschlüsseln.

Initiale Schlüsselerzeugung

Die Karten von Kreuz bekommen die Werte 1 für Ass, zwei für 2, bis zur 13 für König, die Farbe Karo die Werte 14 bis 26, Herz die Werte 27 bis 39 und Pik 40 bis 52. Der erzeugte Schlüsselstrom ist eine Sequenz von Zahlen zwischen 1 und 26, weil die Karten modulo 26 gerechnet werden.

Um das Kartenspiel zu initialisieren (also um das Initialdeck zu erzeugen), werden von Schneier drei verschiedene Möglichkeiten beschrieben:

1. Karten-Mischen:
Beim Mischen ist darauf zu achten, dass das Spiel nicht neu ist (da es sich dann schlecht mischen lässt) und dass die Karten ausreichend lang gemischt werden. Das zufällig gemischte Kartenspiel dient nun als Schlüssel. Der Empfänger braucht ein weiteres Kartenspiel, das genauso sortiert ist.

2. Bridge-Reihenfolge:
Bei diesem Verfahren benutzen Empfänger und Sender ein vorher bestimmtes Medium, welches abgebildete Bridgekartenspiele zeigt, wie z.B. die Tageszeitung auf der Rätselseite oder in einem ganz bestimmten Bridgebuch auf einer ganz bestimmten Seite. Die Kartenspiele werden nach diesem Bridge-Diagramm sortiert. Außerdem muss man vereinbaren, wie die Joker einsortiert werden.

3. Passwort:
Sender und Empfänger nutzen ein Passwort, um das Initialdeck zu sortieren. Das Kartenspiel ist in eine bestimmte Ausgangslage zu sortieren z.B. nach Kartenwert von 1-52, Joker A und Joker B. Jetzt wird der Solitaire-Algorithmus auf das Kartenspiel angewendet. Allerdings wird nicht der Schritt 5 durchgeführt sondern anstelle dessen wird Schritt 4 wiederholt. Hier benutzt man den Zählwert des Buchstabens des Passworts anstatt den Wert der letzten Karte. Beachte dabei, dass die oberen Karten direkt über die unterste Karte eingefügt werden. Dieser Vorgang wird für jeden Buchstaben des Passwortes wiederholt. Um eine gewisse Sicherheit zu gewähren, empfiehlt Schneier ein Passwort von mindestens 80 Buchstaben, was zu einem zusätzlichen hohen Zeitaufwand führt.

Sender und Empfänger benötigen dann ein Bridgespiel, das exakt in derselben Weise gemischt vorliegt. Daraus wird dann auf beiden Seiten der Schlüsselstrom generiert. Es gibt 54! (54 Fakultät ist ca. 2*10^71) verschiedene Möglichkeiten, in welcher Reihenfolge die Karten nach dem Mischen angeordnet sein können.

Schlüsselstromerzeugung

Dies ist der eigentliche Algorithmus:
Man nehme das Kartenspiel mit den Bildern nach oben in die Hand. Anschließend werden die folgenden fünf Schritte nacheinander so oft durchgeführt, wie der Klartext Zeichen besitzt.

Schritt 1:

Finde Joker A und sortiere ihn eine Karte nach unten wieder ein. Sollte der Joker die letzte Karte sein, dann sortiere ihn unter die oberste Karte wieder ein.

Schritt 2:

Finde den Joker B und sortiere ihn zwei Karten nach unten wieder ein. Sollte der Joker die letzte Karte sein, dann sortiere ihn unter die zwei obersten Karten wieder ein. Sollte der Joker die vorletzte Karte sein, so sortiere ihn unter die oberste Karte wieder ein. Nimm einfach an, das Kartenspiel sei eine Schleife.

Schritt 3:

Jetzt folgt ein dreigeteiltes Abheben, d.h. vertausche die Karten vor dem ersten Joker mit denen nach dem zweiten Joker. Hierbei spielt es keine Rolle, ob der erste Joker A oder B ist. Mit erstem Joker ist einfach der gemeint, der am nächsten an der obersten Karte liegt bzw. die oberste Karte ist. Die Joker werden nicht mitvertauscht. Sollte einer der Abschnitte keine Karten enthalten, so nimm einfach an das er leer sei und bewege ihn trotzdem.

Schritt 4:

Führe ein Zählabheben wie folgt durch:
Bestimme den Wert u der untersten Karte (u ist der Kartenwert und kann Werte von 1-53 annehmen), und zähle von der obersten Karte dann u einzelne Karten nach unten. Hebe nach der Karte, bis zu der gezählt wurde, ab und lasse die unterste Karte zuunterst.

Schritt 5:

Finde die Ausgabekarte:
Zähle von oben so viele Karten ab wie der Wert der obersten Karte (zähle die oberste Karte als 1). Die Karte unter derjenigen, bis zu der gezählt wurde entspricht dem gesuchten Kartenwert. Sie wird nicht entfernt. Findest du einen Joker so schreibe nichts auf (im Folgenden Nullrunde genannt), sondern beginne erneut bei Schritt 1.
Der Wert (zwischen 1 und 52) der gefundenen Karte ergibt modulo 26 ein Schlüsselstromzeichen. Wenn noch nicht genügend Zeichen erzeugt wurden beginne erneut mit 1.

Mit CrypTool ist es möglich,