Verschlüsselung im Chaos (Chaos-based encryption)

Verschlüsselung im Chaos

A copy of this text I received in the late 1980s in Harare (Zimbabwe) by the mathematician Sönke Rehder; back then as a pupil I implemented (“coded”) the herein described algorithm in BASIC on an Atari 600XL. Sönke Rehder has worked out the algorithm and has written the document, many thanks to him for this inspiring text! The possibilities offered by the 8-bit home computers seemed practically unlimited and have opened whole new worlds (to me) …” [Siegfried Steiner, 15/04/2015]

Einleitung

Vertrauliche Daten, Texte und Programme müssen vor unbefugtem Zugriff wirksam geschützt werden. Wenn ein physikalischer Zugriff auf den Rechner oder den Datenträger nicht verhindert werden kann, stellt die Verschlüsselung von Dateien eine gute Schutzmaßnahme gegen Missbrauch dar. Sie verdirbt einem Datendieb gründlich die Freude am schnellen Erfolg.

Natürlich gibt es viele kommerzielle Computerprogramme mit unterschiedlichen Methoden der Verschlüsselung. Wer jedoch sein Geld sparen will oder tieferen Einblick in eine Methode der Verschlüsselung nehmen möchte, kann ohne großen Programmieraufwand sein eigenes Programm erstellen. Die Anwendung wird so aussehen, dass sich der Benutzer eine Folge von Zeichen ausdenkt und dem Verschlüsselungsprogramm diesen Schlüssel mitteilt. Daraufhin legt das Programm eine neue Datei mit dem verschlüsselten Text an. Diese neue Datei ist genauso lang wie die Originaldatei, da die Verschlüsselung Zeichenweise vorgenommen wird. Zur Entschlüsselung muss genau der alte Schlüssel eingegeben werden. Ansonsten besteht keine Möglichkeit, den alten Text wiederherzustellen. Es nützt dem Datendieb auch nichts, wenn er über das gleiche Programm verfügt.

Problem

Zuerst wird das Problem auf ein numerisches Problem reduziert. Jedem Zeichen 1äßt sich auf einfache Weise eine ganze Zahl zuordnen. Dieser ASCII-Code liege zwischen 0 und 255. Umgekehrt 1äßt sich jede beliebig große Zahl in ein ASCII-Zeichen umwandeln. Dazu wird die Zahl über eine Modulo-Funktion auf den Bereich zwischen 0 und 255 abgebildet. Anschließend wendet man die zur ASCII-Funktion inverse Operation an. Für die Verschlüsselungsmethode ist es unerheblich, ob die Standardfunktionen für ASCII-Umwandlungen benutzt werden. Nur die eindeutige Zuordnung ist entscheidend. Der Programmierer wird natürlich auf die schnellsten ihm verfügbaren Funktionen zurückgreifen.

Im vorigen Absatz haben wir zwar eine Umwandlung der Zeichen in Zahlen vorgenommen, sie hat aber nur den Sinn, dass wir uns bei der eigentlichen Verschlüsselung auf das Ver- und Entschlüsseln von ganzen Zahlen beschränken können. An dieser Stelle könnte man auf den Gedanken kommen, jeder Zahl zwischen 0 und 255 eine neue Zahl zuzuordnen, sodass die Null immer in q(0), 1 in q(1) usw. umgewandelt wird. Dieser Weg ist aber nicht ratsam, weil quasi nur die Schreibweise der einzelnen Zahlen bzw. Zeichen geändert würde. Ein solcher Text wäre relativ leicht zu entschlüsseln. Wir werden daher die Verschlüsselung zusätzlich von der Position i im Text (i = 1, … N mit N=Länge des Textes) abhängig machen. Es ist also das Ziel, ein einfaches Verfahren zu finden, das uns eine beliebig lange Folge von unterschiedlichen ganzen Zahlen k(i) liefert, die dann zu den Ausgangszahlen n(i) addiert werden. Der resultierende Wert c(i) = n(i)+k(i) ist der kodierte Wert. Ist ein kodierter Wert gegeben, so erhält man durch Subtraktion den ursprünglichen Wert zurück. Würden wir als Zahlenfolge k(i) die Folge aus abwechselnd Null und Eins wählen, so müsste man zu der ersten auftretenden Zahl nä1) eine Null addieren, zur zweiten eine Eins zur dritten wieder eine Null usw. Für die Verschlüsselung von Texten hätte ein solches Vorgehen zur Folge, dass das erste, dritte, fünfte .. Zeichen unverändert bliebe. An allen geraden Stellen wäre das ASCII-Zeichen um ein Zeichen in der ASCII-Tabelle verschoben. Das Verfahren wäre extrem schlecht. Es scheitert daran, dass die oben definierte Folge zu “brav” ist. Bevor wir ein Beispiel für das ganze Gegenteil, nämlich eine chaotische Funktion angeben, sollen einige Forderungen an die Folge k(i) gestellt werden.

Forderungen

  1. Die Folge k(i) soll durch einige wenige Parameter, die der Benutzer eingibt, vollständig definiert sein.
  2. Selbst geringfügigste Abweichungen von diesen Parametern müssen zu völlig falschen Ergebnissen führen.
  3. Innerhalb der Folge k(i) dürfen keine Regelmäßigkeiten auftauchen.
  4. Die Folge k(i) muss selbst für große i’s determiniert bleiben, und darf insbesondere den für den Rechner gültigen Bereich nicht verlassen.
  5. Für die praktische Anwendung ist eine schnelle Ausführungszeit sehr wünschenswert.

Nachfolger- oder Poincaré Funktion

Betrachten wir die “Nachfolger-“ oder “Poincaré” Funktion N(x) = Ax(1-x). Durch diese Vorschrift wird eine interessante Folge beschrieben. Man beginnt mit einem Startwert x(0). Den Wert x(1) erhält man durch Einsetzen von x(0). Danach erhält man x(2) durch Einsetzen von x(1) usw. Wählen wir als Startwert eine reelle Zahl zwischen Null und Eins und A kleiner als 4, so können wir sicher sein, dass auch keiner der Nachfolger außerhalb dieses Bereichs liegt. Da für Kodierung und Dekodierung die gleichen Zahlen benötigt werden, können Rechenungenauigkeiten weitgehend vernachlässigt werden. Damit sind bereits die Forderungen 1, 4 und 5 erfüllt. Der erste vom Benutzer einzugebende Wert muss der Startwert x(0) sein. Wie aber muss der Parameter A beschaffen sein? Für A=2.5 strebt die Folge unabhängig vom Startwert x(0) gegen 0.6. Für A=3 wird die Folge nach einiger Zeit nur noch zwischen zwei Fixpunkten pendeln. Vergrößern wir A weiterhin, so wird die Zahl der Fixpunkte in immer schnellerem Maß zunehmen. Ab dem Grenzwert A = 3.549945… schließlich stellt sich das gewünschte Verhalten ein. Die Folge wird nicht mehr periodisch und durchläuft wie zufällig Zahlen aus dem Bereich zwischen Null und Eins. Die aus unserer Sicht erfreulichste Eigenschaft ist die Verletzung der starken Kausalität, die besagt, das ähnliche Ursachen auch ähnliche Wirkungen haben. Das Gegenteil ist hier der Fall. Selbst wenn die Anfangswerte noch so nahe beieinander liegen, nach einiger Zeit werden die sich daraus ergebenden Folgen völlig unterschiedliches Verhalten zeigen.

Es bleibt nur noch ein kleines Problem. Die chaotische Funktion liefert reelle Werte zwischen Null und Eins. Wir brauchen jedoch ganzzahlige Werte k(i) zwischen Null und einer großen Zahl, die aber vom Rechner noch verarbeitet werden kann. Dazu wird einfach jeder Wert x(i) mit einem großen konstanten Faktor S multipliziert und gerundet: k(i) = S*x(i).

Damit sind alle Bausteine für den Verschlüsselungsalgorithmus definiert:

Verschlüsselungsalgorithmus

  • Schritt 0: Setzen der Parameter: - Startpunkt x(0) (reelle Zahl zwischen 0 und 1) - Parabelkoeffizient A (reelle Zahl zwischen 3.57 und 4) - Weitungsfaktor S (große reelle Zahl, aber kleiner als die größte vom Rechner darzustellende INTEGER)
  • Schritt 1: 4 Einlesen des nächsten zu kodierenden Zeichens a(i)
  • Schritt 2: Ermitteln des zu a(i) gehörigen ASCII-Codes n(i)
  • Schritt 3: Anwenden der Chaos-Funktion x(i) = x(i-1)A(1-x(i-1))
  • Schritt 4: Berechnung. des Verschiebungskoeffizienten k(i)=S*x(i) (gerundet).
  • Schritt 5: Verschieben des ASCII-Codes m(i)=(n(i)+k(i)) MODULO 256
  • Schritt 6: Ermitteln des kodierten Zeichens b(i) mit dem ASCII-Code m(i).
  • Schritt 7: Erhöhe den Index i = 1+1 und gehe zu Schritt 1

Die Entschlüsselung verläuft analog. Der einzige wesentliche Unterschied besteht darin, dass bei Schritt 5 nicht addiert, sondern subtrahiert wird:

  • Schritt 0: wie oben
  • Schritt 1: Einlesen des nächsten zu dekodierenden Zeichens b(1)
  • Schritt 2: Ermitteln des zu b(i) gehörigen ASCII-Codes m(i)
  • Schritt 3: Anwenden der Chaosfunktion x(i) = x(i-1)A(1-x(i-1))
  • Schritt 4: Berechnung des Verschiebungskoeffizienten k(1)=S*x(i) (gerundet).
  • Schritt 5: Verschieben des ASCII-Codes n(i)=(m(i)-k(i)) MODULO 256
  • Schritt 6: Ermitteln des dekodierten Zeichens a(i) mit dem ASCII-Code n(i).
  • Schritt 7: Erhöhe den Index i = i+1 und gehe zu Schritt 1

“For an implementation of this chaos-based encryption algorithm, see the refcodes-security-alt-chaos artifact, the source codes for encryption are found in the files ChaosDecrypter and ChaosEncrypter. A plain example on its usage you find in the ChaosTest unit test.” [Siegfried Steiner, 15.04.2015] - A reference CHAOS application you will find in this blog’s downloads section and the according sources are found in the funcodes-chaos repository.

Überlegungen

Durch die folgenden Überlegungen kann der Algorithmus noch verfeinert oder verändert werden:

  1. Es können andere chaotische Funktionen benutzt Werden. Hierzu sei auf die Literaturangaben verwiesen.
  2. Der oben geschilderten Prozedur kann eine kleine Prozedur vorgeschaltet werden. Man startet die Verschlüsselung des ersten Zeichens dann nicht mit x(1), sondern z.B. mit x(100). Dadurch. wird erreicht, daß bei Eingabe von extrem benachbarten Eingabeparametern bereits die Entschlüsselung des ersten Zeichens nicht mehr gelingt. Die Rechengenauigkeit des Rechners setzt hier natürlich Grenzen.
  3. Es fällt manchen Anwendern schwer, sich Zahlen als Schlüsselparameter zu merken. Sie würden lieber einen Text statt Zahlen eingeben. Die Programmierung ist nicht schwer. Es sollte aber bedacht werden, dass bei der Wahl allzu vordergründiger Schlüsselworte (oder Sätze) die ganze Mühe einer guten Verschlüsselung vergebens ist.
  4. Der vorgestellte Algorithmus benutzt zur Verschlüsselung des i+1 ten Zeichens nur den Chaoswert x(i) der vorherigen Textposition i, nicht aber das Zeichen a(i). Das könnte man zwar ändern. Ein Chaos wird aber nicht dadurch chaotischer, indem man ein zweites Chaos hinzufügt.
  5. Wenn der Originaltext und der verschlüsselte Text nur bestimmte ASCII-Zeichen z.B. die normalen darstellbaren Zeichen enthalten sollen, so ist auch dies leicht realisierbar. Sei 32 das erste, und 126 das letzte Zeichen, so muss Schritt 5 ersetzt werden durch m(i)=32+(n(i)+k(i)-32) MODULO 95 bzw. n(i)=32+(m(i)- k(i)-32) MODULO 95.
  6. In manchen Fällen ist es wünschenswert, einen Text, einte Liste, ein Programm oder eine Zeichnung so zu verschlüsseln, daß er nur im Beisein einer zweiten Person wieder entschlüsselt werden kann. Auch dies ist natürlich leicht zu realisieren. Eine Möglichkeit wäre, wenn einer Person nur der Parameter A, und der anderen die Parameter x(0) und S bekannt sind.

Diese Liste von Verbesserungen und Anwendungen ließe sich beliebig erweitern.

Diesen Text habe ich Ende der 1980er Jahre in Harare (Simbabwe) von dem Mathematiker Sönke Rehder erhalten; damals hatte ich als Schüler auf einem Atari 600XL den hier beschriebenen Algorithmus umgesetzt (“nachprogrammiert”). Sönke Rehder hatte den Algorithmus ausgearbeitet gehabt sowie die Beschreibung dazu verfasst, vielen Dank an Sönke Rehder für diesen inspirierenden Text! Die Möglichkeiten mit den 8-Bit Homecomputern schienen schier unbegrenzt und haben (mir) ganz neue Welten eröffnet …” [Siegfried Steiner, 15.04.2015]

See also