Basiswissen

Zufallsgeneratoren erzeugen üblicherweise Abfolgen von Zahlen (oder anderen Symbolen), die idealerweise möglichst zufällig sind. Wie zufällig eine Zahlenfolge tatsächlich ist, ist schwer zu prüfen.^[1] Bei echten Zufallsgeneratoren geht man davon aus, dass die Zahlenfolge tatsächlich zufällig ist. Bei Pseudozufallsgeneratoren ist der Zufall nur scheinbar.

Einführung

Ein einfaches Beispiel zur Betrachtung der Zufälligkeit von Zahlenfolgen ist die sogenannte Bitfolge. Als Bitfolge bezeichnet man jede geordnete Liste die ausschließlich Nullen und Einsen enthält.

Bitfolge A: 0001010111110110010110001100

Bitfolge B: 1111111111111111111111111111

Man die Abfolge der Zahlen 0 und 1 als Ergebnis eines Wurfes mit einer fairen Münze deuten. Die Wahrscheinlichkeit für eine 0 ist dann ½ oder 0,5. Auch die Wahrscheinlichkeit für eine 1 ist genau ½ oder 0,5. Mit Hilfe der Wahrscheinlichkeitsrechnung kann man dann die Wahrscheinlichkeit einer jeden längeren Folge von Nullen und Einsen berechnen. Siehe dazu den Artikel zum Münzen werfen (externer Link)

Beim ersten Hinsehen würde man die Folge A für zufälliger halten als die Folge B. Doch das Gefühl kann trügen. Beide Abfolgen haben die Wahrscheinlichkeit ½ hoch 28. Wie groß die Zahl in dezimaler Schreibweise ist, spielt hier keine Rolle. Bemerkenswert aber ist, dass die Zahlenfolge ganz aus Einsen dieselbe Wahrscheinlichkeit hat wie die scheinbar gut und zufällig gemischte Zahlenfolge aus Nullen und Einsen. Dieser vielleicht verblüffende Befund wirft dann die Frage auf, woran man die Zufälligkeit einer Zahlenfolge überhaupt erkennen will.

Zwei Typen

Zufallsgeneratoren

Bei echten Zufallsgeneratoren für Zahlenfolgen (Random Number Generator, RNG), auch als Entropiequelle (entropy source)^[2] bezeichnet, bildet ein physikalischer Prozess die Grundlage. Das können Geräusche aus einem elektrischen Schaltkreis sein, die zeitlichen Muster beim Tippen einer Tastatur oder Bewegen einer Maus durch einen Menschen oder auch Quanteneffekte in einem Halbleiter.^[2] Man geht dann davon aus, dass die daraus erzeugten Abfolgen von Ereignissen tatsächlich zufällig sind. Sie sollen nicht-deterministisch (non-deterministic^[2]) sein. Ob es in der Natur wirklich einen echten Indeterminismus gibt, ist jedoch unklar.^[3] Solche Zufallsgeneratoren haben jedoch oft Schwachstellen. Aus einem elektrischen Schaltkreis gewonnene Geräusche könnten durch unbekannte Sinusförmige Schwingungen oder andere regelmäßigen Einflüsse verunreinigt sein. Solche Störfaktoren zu erkennen ist in der Praxis ein oft wichtiges Problem.

Pseudozufallsgeneratoren

Sogenannte Pseudozufallsgeneratoren für Zahlen (Pseudorandom Number Generators, PRNG) erzeugen feste Zahlenfolgen mit Hilfe von einer Rechenregel, also einem Algorithmus. Wer die Rechenregel kennt, kann die Zahlenfolge vorausberechnen. Hier ist der Zufall also nur ein scheinbarer, daher das Wort Pseudozufallsgenerator. Pseudo, als Verb eigentlich pseudein, stammt aus dem Altgriechischen und heißt so viel wie täuschen oder lügen. Um Zahlenfolgen aus einem Pseudozufallsgenerator schwerer vorhersagbarer zu machen, lässt man die Zahlenfolge an einer zufällig gewählten Stelle (Englisch: seed) starten.^[4]

Zufälligkeit bewerten

Eine wichtige und schwer zu lösende Fragestellung ist es, die Zufälligkeit einer Zahlenfolge zu bewerten. Betrachten wir drei sogenannten Bitfolgen. Eine Bitfolge ist eine Abfolge von zum Beispiel Nullen und Einsen. Jede 0 oder 1 soll die Wahrscheinlichkeit ½ haben. Welche drei der Bitfolgen ist am zufälligsten entstanden?

Variante A: 1111111111

Variante B: 1111100000

Variante C: 1001011101

Wer der ersten Intuition folgt, kommt wahrscheinlich zu dem Ergebnis, dass A nicht besonders zufällig aussieht, B nur geringfügig mehr so und C am ehesten echt zufällig wirkt. Doch nutzt man die Rechenregeln für mehrstufige Zufallsversuche bei denen jeder Einzelversuch (jede einzelne 0 oder 1) in seinem Ausgang unabhängig von den vorherigen Versuchen ist (im Urnenmodell: mit zurücklegen), dann kommt man für alle drei Varianten auf das Rechenergebnis ½ hoch 10. Wichtig für den Gedanken hier ist, dass alle drei Zahlenfolgen gleich wahrscheinlich sind. Wie kommt man also zu einem guten Maßstab für die Zufälligkeit von Zahlenfolgen?

Vorab: es gibt keinen einzelnen Test, der ein befriedigendes Maß für die Zufälligkeit einer Zahlenfolge liefert. Stattdessen kann man sich quasi unendlich viele mögliche solche Tests denken. In der Praxis führt man dann mehrere solche Tests durch und deutet sie im Einzelfall. Ein konkreter Vorschlag^[2] verwendet zum Beispiel 15 solcher Einzeltests als sogenannte Testbatterie. Als Mindestlänge einer Bitfolge werden 100 Zeichen empfohlen.^[2] Hier sind dann einige Beispiele für Tests.

Die 0 und die 1 sollten gleich oft vorkommen.

Jede beliebige Teilfolge (z. B. 110 oder 100) sollte die gleiche Wahrscheinlichkeit haben.

Auf welche Weise erscheinen längere Abfolgen gleicher Zahlen, etwa 1111111 (runs)?

Wie gut passt die längste Abfolge von nur 1en auf die Annahme von Zufälligkeit?

Und derlei mehr. Die Schwierigkeit einer Bewertung der Zufälligkeit liegt darin, dass man in Unkenntnis der Entstehung einer Zahlenfolge scheinbar willentlich erzeugte Folgen nicht sicher von scheinbar zufällig entstanden Folgen unterscheiden kann.

Fußnoten

[1] Leung, C., Brown, A., Nguyen, H., Friedman, A.S., Kaiser, D.I., and Gallicchio, J.,: Astronomical Random Numbers for Quantum Foundations Experiments. In: Physical Review A, Vol. 97, Issue 4, 2018. id. 042120 (arXiv:1706.02276) (DOI).

[2] Es gibt unendlich viele und dabei auch unvollständige Arten, die Zufälligkeit einer Abfolge von Nullen und Einsen (Bitfolge) zu testen: "There are an infinite number of possible statistical tests, each assessing the presence or absence of a “pattern” which, if detected, would indicate that the sequence is nonrandom. Because there are so many tests for judging whether a sequence is random or not, no specific finite set of tests is deemed “complete.” In addition, the results of statistical testing must be interpreted with some care and caution to avoid incorrect conclusions about a specific generator". 15 solche Verfahre werden sehr ausführlich vorgestellt in: Andrew Rukhin: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22. Revision 1a. April 2010. Online: https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf

[3] Indeterministisch heißt ein Ereignis, wenn es ohne Ursache, ohne kausale Beziehung zu anderen Ereignissen eintreten kann. Physiker behandeln etwa den Zeitpunkt eines Atomzerfalls als indeterministisch. Wie problematisch das Denkkonzept ist zeigt das Beispiel eines Würfelns. Würde man die Position, Form und Bewegung der Hand und des Würfel und die Ausprägung der Tischfläche während eines Würfelvorganges beliebig exakt kennen und würde man zusätzlich alle Naturgesetze kennen, die wirken, dann könnte man theoretisch vorausberechnen, welche Zahl eines Würfels am Ende nach oben zeigt. Das ist die Grundidee des sogenannten Laplaceschen Dämons. Denselben Gedanken könnte man auch auf den Zeitpunkt eines Atomzerfalls übertragen. So gedacht, wäre der Zeitpunkt eines Atomzerfalls nicht mehr wirklich zufällig. Siehe auch 👉 Indeterminismus

[4] "A PRNG uses one or more inputs and generates multiple “pseudorandom” numbers. Inputs to PRNGs are called seeds. In contexts in which unpredictability is needed, the seed itself must be random and unpredictable. Hence, by default, a PRNG should obtain its seeds from the outputs of an RNG; i.e., a PRNG requires a RNG as a companion. The outputs of a PRNG are typically deterministic functions of the seed; i.e., all true randomness is confined to seed generation." In:

In: Andrew Rukhin: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22. Revision 1a. April 2010. Online: https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf