Die Chaos-Verschlüsselung

Brasilianische Forscher haben mit zellulären Automaten ein neues Verfahren zum Schutz privater Bilder entwickelt.

Die Idee, chaotische Zustände zur Verschlüsselung zu verwenden, ist schon Jahrzehnte alt. Der Ansatz klingt einfach: Man nehme eine Mitteilung, mische sie einem scheinbar zufälligen Signal bei und sende sie dann. Wenn das Signal gut gewählt ist, wirkt die Botschaft so, als könnte sie auch Hintergrundrauschen sein. Um das Original zu entschlüsseln, muss der Empfänger einfach nur das gleiche chaotische Signal kennen und kann dieses dann mathematisch herausrechnen.

Marina Jeaneth Machicao und ihre Kollegen an der Universität der brasilianischen Stadt Sao Paulo haben nun ein Verfahren vorgestellt, mit dem sich diese Methode auf die Verschlüsselung von Bildern übertragen lässt. Dabei werden zelluläre Automaten verwendet, um ein Signal zu schaffen, das höchst zufällig wirkt.

Ein solcher zweidimensionaler zellulärer Automat besteht aus einem Kästchenraster, einem Zellularraum, in dem jede Zelle entweder schwarz oder weiß sein kann. In jedem Zyklus wird der Zustand jeder Zelle einzeln abgefragt und anhand vordefinierter Regeln geändert – eine solche Regel könnte beispielsweise lauten: Schalte das Kästchen auf weiß, wenn ein oder mehrere Nachbarkästchen weiß sind. Mit diesem Verfahren ist es möglich, einen pseudozufälligen Output zu generieren, bei dem das Ergebnis wie Rauschen aussieht. Das gilt allerdings keineswegs für jeden zellulären Automaten.

Deshalb untersuchten Machicao und ihr Team zunächst eine große Anzahl zellulärer Automaten darauf, welche den zufälligsten Output liefern. Zentraler Messwert war die Qualität des Zufallsoutputs nach 20 Millionen Durchgängen, die mit Hilfe der Standard-Statistiktests ENT und DIEHARD überprüft wurden. "Gewinner" war Fredkin B1357/S02468 – dieser zelluläre Automat lieferte das beste Pseudozufallsergebnis.

Um das Verfahren für eine Verschlüsselung einzusetzen, muss sich das scheinbar zufällige Ergebnis natürlich wiederholen lassen. Dabei nutzten die Forscher die Eigenschaft ihres zellulären Automaten, dass sein Output stets von der Startkonfiguration abhängt. Das ist wichtig, weil diese Startkonfiguration nun als Passwort dienen kann. Das bedeutet, dass der zelluläre Automat frei im Internet verbreitet werden könnte, ohne dass dies die Sicherheit gefährdet – nur derjenige, der das Passwort kennt, kann die Botschaft auch dechiffrieren.

Praktisch funktioniert das dann so: Ein eingegebenes Passwort erzeugt ein Startmuster der Zellen im zellulären Automaten. Dann werden 20 Millionen Durchgänge erzeugt, um den pseudozufälligen Output zu erhalten. Diesem wird dann ein digitales Bild überlagert. Dann wird das Chaossignal verschickt – fertig. Der Empfänger mit dem korrekten Passwort kann es sich ansehen, indem er den Vorgang in umgekehrter Reihenfolge durchlaufen lässt.

Noch ist nicht abschließend überprüft, wie sicher das Verfahren der brasilianischen Forscher ist. Das Hauptproblem: Zwar wirkt der Output wie zufällig, doch wird er eben faktisch durch einen vorherbestimmten Prozess generiert. Lücken in solchen Pseudo-Zufallsgeneratoren haben Kryptologen schon viele gefunden.

Allerdings sind zelluläre Automaten durchaus in der Lage, Outputs zu erzeugen, die sich von natürlichen Zufallsmustern so gut wie nicht unterscheiden lassen. Stephen Wolfram, einer der Pioniere auf diesem Gebiet, denkt beispielsweise, dass das Universum seinen "Zufall" durch einen ähnlichen Prozess generiert. Der Zufallsgenerator in Wolframs bekannter Mathematica-Software nutzt diesen Ansatz.

Nun müssen Machicao und ihre Kollegen beweisen, dass ihr Ansatz wirklich nicht zu knacken ist – auch mit großer Rechenleistung nicht. Dann würde sich die Idee mindestens für kürzere Botschaften und einzelne Bilder eignen. (bsc)