Menu

Kryptologie

One-Time-Pad mit Clifford Attraktor

Es geht in diesem Kapitel um zwei Dinge: Wie kann man in Processing auf Bit-Ebene die XOR Verknüpfung darstellen und wie erzeugt man mit Hilfe des Clifford Attraktore ein One-Time-Pad ?
Ein One-Time-Pad ist ein "Einmalschlüsselung-Verfahren", das eine Schlüssel verwendet, der mindestens so lange ist, wie die Nachricht. Mit einem Schlüssel, der echt zufällig ist und auch nur ein einziges Mal verwendet wurde, kann die Nachricht nicht entschlüsselt werden. Das ist keine Vermutung: Es ist mathematisch beweisbar! Wer es genauer wissen will, schaut hier nach.
Der Haken an der Sache: Es ist nicht einfach, einen wirklich zufälligen Schlüssel zu erzeugen! Eine Methode wäre, radioaktiven Zerfall zu verwenden. Hat man bei einer radioaktiven Probe festgestellt, dass mit 50%-iger Wahrscheinlichkeit zehn Teilchen innerhalb einer Sekunde zerfallen, dann wählt man 1, falls dies zutrifft und 0 in gegenteiligen Fall. Mühsam! Man sucht daher Funktionen, die dem Zufall nahe kommen. Die einfachste ist random() in Java und Processing. Leider ist sie in keinster Weise sicher. Deutlich besser ist die Methode SecureRandom(), die aktuelle Daten des Betriebssystems mit verwendet.
Wir benutzen eine Variante des chaotischen Clifford Attraktors. Man erzeugt damit eine komplizierte Menge fraktalen Charakters. Das chaotische System erzeugt man durch genügend lange Iterationen der dynamischen Clifford Iteration. Wie die Abbildung genau aussieht, lesen Sie dort im Abschnitt Clifford Gleichungen als partielle Ableitungen interpretiert .
Eine wesentliche Eigenschaft, die die Abbildung haben sollte, ist eine hohe Empfindlichkeit (sensitivity) von den Parametern, die als Schlüssel dienen. Genau das aber ist bei chaotischen Abbildungen der Fall. In unserem Fall wird es fünf achtstellige Parameter geben. Falls nur eine der 40 Ziffern verändert wird, ist keine (auch teilweise) Entschlüsselung mehr möglich. Zudem sollten die, durch die Clifford Abbildung erzeugten möglichen Ergebnisse, gleichverteilt sein. Dies ist, wie wir sehen werden, ebenfalls erfüllt. Es ist bei chaotischen Abbildungen gänzlich unmöglich, einen Folgewert aus den vorhergehenden zu bestimmen, ohne den Algorithmus und die Paramter genau zu kennen .

Zur XOR Verknüpfung auf Bit-Ebene:
Zunächst bestimmen wir auf übliche Weise zwei Zufallsfarben (farbe1,farbe2) und bringen sie in ihre Einzel-Bit Darstellung.

Bedenken Sie, dass im RGB-Mode 32 Bit für eine Farbe samt Transparenz (alpha) benötigt werden. Von links nach rechts kommen erst 8 Bit für den Alphawert, dann 8 Bit für rot, dann 8 Bit für grün und schließlich 8 Bit für blau. Die erste Zeile bedeutet: Schiebe die acht Bit des Alphawerts a ganz nach vorn und ergänze durch 24 Bit mit Wert 0. Ohne Transparenz ist a =255 oder 11111111, insgesamt also 11111111 00000000 00000000 00000000. Für beispielsweise r = 17 oder 0010001, erhält man den Eintrag der 8 Bit vor der 16.Stelle: 00000000 00100001 00000000 00000000. Der senktrechte Strich "|" bei farbeBin1 ist die OR-Verknüpfung. Es gilt: 0 | 0 = 0 und 1 für alle andern Möglichkeiten. In unserem Beispiel wäre daher a | r :

11111111 00000000 00000000 00000000

00000000 00100001 00000000 00000000

11111111 00100001 00000000 00000000

Nach der Zeile farbeBin1 = a | r | g | b haben alle Bits ihren der Farbe entsprechenden Wert. Mit fill(farbeBin1) kann man das obere Quadrat einfärben. Entsprechend verfährt man beim 2. Quadart.
Die XOR-Verknüpfung (ausschließendes oder) ist definiert durch: 0 | 0 = 0 und 1 | 1 = 0. Bei verschiedenen Bit-Werten erhält man 1. So funktioniert die XOR-Verknüpfung in Java:
Das dritte Quadrat erhält seine Farbe durch Anwendung von XOR auf alle Bits der ersten und zweiten Farbe. Da wir keine Transparenz wünschen, reicht es, die ersten 24 Bit abzubilden. Ein Beispiel:

01100100 10001100 00110101 farbeBin1

00100001 01011100 11110000 farbeBin2

01000101 11010000 11000001 farbeBin1 XOR farbeBin2

00100001 01011100 11110000 farbeBin2

01100100 10001100 00110101 (farbeBin1 XOR farbeBin2) XOR farbeBin2

Wie Sie sehen, erhält man nach der wiederholten XOR-Verknüpfung mit farbeBin2 wieder den ursprünglichen Farbwert farbeBin1. Die zweite Farbe kann man zur Verschlüsselung der ersten Farbe verwenden. Sie ist offensichtlich der Schlüssel für beide Vorgänge: Zum Ver- und Entschlüsseln der Ursprungsfarbe.
Damit bekommt man ein Verfahren zur Ver- und Entschlüsselung eines Farbbildes, in dem man das beschriebene Verfahren auf jedes Pixel anwendet. Die Bilddimensionen müssen dabei mit den Schlüsseldimensionen übereinstimmen. Im Folgenden versuchen wir (der Einfachheit halber für ein Graustufenbild) einen Schlüssel zu erzeugen, der hinreichend "zufällig" ist.

Den Sketch zur Erzeugung des Schlüssels können Sie sich hier runterladen. Alle notwendigen Erläuterungen findet man im Kapitel Clifford Attraktors . Die fünf zu wählenden Parameter können zum Beispiel so aussehen: Wir gehen davon aus, dass ein Graustufenbild der Dimension 1000x1000 verschlüsselt werden soll. Ändern Sie gegebenenfalls size() zum Bild passend.
Nachdem der Sketch gestartet wurde, findet man bild2.bmp wie links (ohne Diagramm) im Programmordner. Jedes Pixel hat einen Grauwert zwischen 0 und 255. Diese Werte sollten unbedingt gleichverteilt sein. Das Programm ist bereits auf die Kontrolle vorbereitet. In der Console wird die Anzahl der Pixel mit Wert n ausgegeben. Wir kopieren diese Daten in Exel oder in Libre Office Calc und lassen uns das zugehörige Balkendiagramm anzeigen. Wie man links erkennen kann, ist die Gleichverteilung perfekt.
Kommen wir nun zum eigentlichen XOR-Verschlüsselungs Sketch xorSW. Wir benötigen, wie im Kapitel Bildbearbeitung , zwei Methoden: Legen Sie das zu verschlüsselnde Graustufenbild mit Namen bild1.jpg und das oben erstellte Schlüsselbild mit Namen bild2.jpg in den Programmordner. Wie man eine Farbe mit XOR verschlüsselt, wissen Sie schon. Bei einem Graustufenbild im RGB-Modus sind die Zahlenwerte für rot, grün und blau identisch. Das ändert am Verfahren aber nichts. Noch immer müssen 32 Bit eingetragen werden.
Rechts oben das zu verschlüsselnde Bild, darunter das Ergebnis, abgespeichert unter bild3.bmp. Um dieses Bild wieder zu entschlüsseln, speichern Sie bild3 als bild1 im Programmordner ab. Das bedeutet, dass alle Pixelwerte ein zweites Mal mit XOR "verschlüsselt" werden. Und in der Tat finden wir danach im Programmordner das ursprüngliche Bild als bild3.bmp.
Als letztes sollte die "Schlüsselempfindlichkeit" geprüft werden. Das ist schnell erledigt. In den Processing eigenen Funktionen wird mit float gearbeitet. Selbst wenn wir die Parameter als double-Werte anlegen, können wir uns nur auf sieben gültige Ziffern verlassen. Ändern Sie daher bei der Schlüsselerzeugung eine einzelne Ziffer bei einem der fünf Parameter im Bereich dieser ersten sieben Ziffern. Versuchen Sie nun das verschlüsselte Bild mit dem veränderten Schlüssel sichtbar zu machen. Das Ergebnis ist Chaos. Somit ist auch diese Forderung erfüllt.
Es gibt also 10³⁵ verschiedene Schlüssel!
Es ist etwas umständlich mit zwei Tools zu arbeiten. Daher wird die Schlüsselerzeugung und die Ver/Ent-schlüsselung in einen Sketch gepackt: Sketch Schlüsselerzeugung und XOR-Verschlüsselung



Typisch Clifford-Attraktor: Mitunter bekommen Sie als Schlüssel kein Chaos-Bild, sondern eine wie auch immer geartete Struktur:

Dann haben Sie zufällig eine der seltenen Parameter-Kombination gefunden, die wir im Kapitel Clifford Attraktore mühsam gesucht haben ;-))

Wie sieht die Übergabe der Information konkret aus?
Nehmen wir an, Bob will Eve eine Nachricht zukommen lassen. Eve sollte den Schlüssel, bestehend aus fünf Parametern haben. Dann erzeugt sie sich den schluesselXOR.bmp mit dem Sketch, den sie beispielsweise hier runterladen kann.

Sketch Farbe mit XOR verschlüsseln

Sketch Clifford Attraktor Schlüssel

Sketch SW-Bild verschlüsseln mit XOR

Sketch Schlüsselerzeugung und XOR-Verschlüsselung

Menu