© Liashko/Shutterstock.com
Teil 2: Zufallszahlengeneratoren und symmetrische Verschlüsselung

Zufälliger Determinismus?


Computer sind letztlich Rechenmaschinen, daher arbeiten sie deterministisch. Wenn aber Zufall eine große Rolle in der Kryptografie spielt, wie lässt sich das miteinander vereinbaren?

Im ersten Teil dieser Serie wurde im Zusammenhang mit dem One-Time Pad (OTP) erwähnt, wie wichtig das Verwenden von Zufall beziehungsweise Zufallszahlen ist, um wiederkehrende Muster zu vermeiden. Diese können in der Verschlüsselung rasch auftreten, da zumindest Textnachrichten in natürlichen Sprachen verfasst werden, die per se besondere Eigenheiten und Muster aufweisen. Diese gilt es aufzubrechen.

In Anbetracht der enormen Rechenleistung, die heute selbst in Mobiltelefonen zur Verfügung steht, stellt man sich die Frage, wie schwer es denn sein kann, ein paar Zufallszahlen zu erzeugen. Diese Aufgabe sollte doch im 21. Jahrhundert verhältnismäßig einfach zu lösen sein – meint man. Wie schwer das jedoch tatsächlich ist, merkt man, wenn man selbst einmal von Hand versucht, eine zufällige Reihe von Nullen und Einsen aufzuschreiben. Im Folgenden der Versuch des Autors, der durch spontanes Tippen ohne weiteres Nachdenken entstanden ist:

001010101011010101001010101001010010101001010

Analysiert man diese Reihe, stellt man fest, dass weder die eine noch die andere Ziffer mehr als zwei Mal in Folge auftritt – und selbst das ist schon selten. Tatsächlich wechseln sich die beiden Ziffern im Wesentlichen mit schöner Regelmäßigkeit ab. In einer echt zufälligen Reihe müssten auch längere Sequenzen enthalten sein, im Extremfall könnte sie sogar so aussehen:

000000000000000000001111111111111111111111111

Rein statistisch betrachtet ist diese Reihe nicht wahrscheinlicher oder unwahrscheinlicher als die vorige. Auf einen Menschen wirkt sie aber geplant und systematisch.

Die fehlende Unregelmäßigkeit in dem vermeintlich zufällig erzeugten Ergebnis lässt sich durch das Maß der Entropie [1] beschreiben, das angibt, wie unstrukturiert ein Text ist. Verwandt damit ist die Redundanz, die quasi das Gegenteil der Entropie beschreibt: Ein echt zufälliger Text hat eine Redundanz von 0, in natürlich-sprachlichen Texten liegt sie weitaus höher.

Eine eigene Zufallsfunktion bauen

Nun überlässt man in der Kryptografie das Erzeugen von Zufallszahlen selten einem Menschen, sondern verwendet dafür die Mittel der jeweiligen Programmiersprache. Praktisch jede Sprache kennt dafür geeignete Funktionen, wie beispielsweise Math.random in JavaScript. Warum also nicht diese Funktionen verwenden?

Tatsächlich ist das, was diese Funktionen liefern, kein echter Zufall, sondern sogenannter Pseudozufall. Da Computer, wie bereits erwähnt, deterministische Rechenmaschinen sind, können sie per Definition keinen Zufall erzeugen – andernfalls wären sie ja nicht mehr deterministisch. Stattdessen wird für Pseudozufallszahlen auf mathematische Funktionen zurückgegriffen, die so komplex sind, dass ihre Ergebnisse zufällig aussehen, auch wenn sie es streng genommen nicht sind.

Ein einfaches Beispiel dafür bietet die Funktion in Listing 1.

Listing 1: Pseudozufall

const getRandomNumber = function (seed) {
  const randomNumber = (seed * 7) % 11;
 
  return randomNumber;
};

Ruft man diese Funktion auf und initialisiert sie mit dem Wert 1, erhält man im ersten Schritt als Ergebnis die Zahl 7. Verwendet man dieses Ergebnis nun als Ausgangswert für die nächste Iteration, erhält man 5. Anschließend erhält man 2, 3 und so weiter. Die Modulo-Division, die durch % 11 ausgeführt wird, bewirkt, dass die Ergebnisse allesamt zwischen 0 und 10 liegen. Erzeugt man nun zehn Zufallszahlen, erhält man mit dieser Funktion die folgende Reihe:

7 5 2 3 10 4 6 9 8 1

Wie man sieht, ist diese Reihe gar nicht schlecht gewählt. Jede Zahl zwischen 1 und 10 kommt genau einmal vor, das heißt, die Zahlen sind prinzipiell gleichverteilt. Außerdem steigen die Zahlen teilweise, teilweise fallen sie. Manche Zahlen liegen dicht beieinander (wie die 9 und die 8), andere hingegen sind weit voneinander entfernt (wie die 3 und die 10). Alles in allem macht diese simple Funktion also bereits einen guten ersten Eindruck.

Was passiert nun, wenn man mehr als zehn Zufallszahlen benötigt? Leider ist absehbar, was geschehen wird: Da die 1 das zehnte Ergebnis darstellt, wird als elfter Wert wieder die Zahl 7 berechnet werden. Ab der elften (vermeintlichen) Zufallszahl wiederholen sich die Ergebnisse...

headline from sands settings