Einführung

Bevor wir uns mit dem Thema Zufallszahlengeneratoren befassen, definieren wir zunächst einmal den Begriff Zufall. Was ist der Zufall eigentlich und wann kann man tatsächlich von Zufall sprechen? Eine zufällige Zahl ist zunächst einmal das Ergebnis von speziellen Zufallsexperimenten. Umgangssprachlich wird der Begriff Zufall - oder „reiner“ Zufall - verwendet, wenn Ereignisse scheinbar nicht kausal erklärbar sind. In unserem realen Umfeld erleben wir Phänomene die in unseren Augen zufällig erscheinen und daher nicht vorhersehbar sind. Das Wetter ist in der Regel ein chaotisches System, in welchem der Zufall regiert und daher sind Wettervorhersagen, die über eine bestimmte Zeitspanne hinausgehen ohne praktischen Nutzen. Streng gesehen bezeichnen wir viele Vorgänge als chaotisch und vom Zufall bestimmt, obwohl diese in Wahrheit durchaus deterministisch geprägt sein können. So lässt sich ein System theoretisch exakt beschreiben wenn die Anfangsbedingungen und physikalischen Gesetzmäßigkeiten des Systems dem Beobachter vollständig bekannt sind.

Laplacescher Dämon

Die Überlegung das die Welt deterministisch sei, hat in der Geschichte bereits viele Menschen beschäftigt, darunter den berühmten Mathematiker Pierre-Simon Laplace, Schöpfer der Integraltransformation, auch Laplace-Transformation genannt. Laplace stellte die Theorie des Laplacesche'n Dämon auf der die erkenntnis- und wissenschaftstheoretische Auffassung bezeichnet, dergemäß es möglich ist, unter der Kenntnis sämtlicher Naturgesetze und aller Initialbedingungen jeden vergangenen und jeden zukünftigen Zustand zu berechnen.

Aus heutiger Sicht wissen wir das der Laplacescher Dämon ein Phantasiegebilde war, da die Heisenbergsche Unschärferelation eine vollständige Kenntnis des Zustands eines Systems unmöglich macht und ein System deshalb in letzter Konsquenz für den Beobachter in seiner Gesamtheit nicht erfassbar bleibt. Zudem haben insbesondere die Phänomene der Quantenphysik Bereiche aufgezeigt, in denen es durchaus „reine“ Zufälle geben könnte. Die Gleichungen der Quantenmechanik nutzen den Zufall allerdings ohne die Existenz eines absoluten Zufalls zu beweisen bzw. diesen in letzter Konsequenz vorauszusetzen. Zudem ist es auch in der Quantenmechanik nicht erlaubt, Ereignisse in der Vergangenheit zu verändern, sodass in jedem Fall das Kausalprinzip vorherrscht.

Wir gelangen an einen Grenzpunkt an dem wir festhalten müssen das Zufall und Determinismus fließend ineinander übergehen. Für uns ist im Prinzip nur wichtig ob wir einen quantitativen Zufall erreichen können. Das bedeutet ob wir Zahlen generieren können die für uns prinzipiell ausreichend zufällig sind.

Zufallszahlengenerator

Für die Erzeugung von Zufallszahlen gibt es verschiedene Verfahren. Diese werden als Zufallszahlengeneratoren bezeichnet. Der Zufallszahlengenerator, gelegentlich auch einfach nur Zufallsgenerator oder schlicht Generator genannt, bezeichnet ein Verfahren, das eine Folge von Zufallszahlen erzeugt. Der Bereich, aus dem die Zufallszahlen erzeugt werden, hängt dabei vom Zufallszahlengenerator ab. Es kann beispielsweise die Menge aller 32-Bit-Zahlen oder auch die Menge der reellen Zahlen im Intervall [0,1] sein. Ein entscheidendes Kriterium für Zufallszahlen ist, ob das Ergebnis der Generierung als unabhängig von früheren Ergebnissen angesehen werden kann oder nicht. Ein guter Zufallszahlengenerator muss dieses wichtige Kriterium erfüllen. Diese Bedingung mag auf den ersten Blick nicht sonderlich aufregend sein, ist für die Qualität der produzierten Zufallszahlen allerdings von entscheidender Bedeutung.

Von einem Zufallszahlengenerator wird darüberhinaus erwartet, dass er gleichverteilte Werte aus dem jeweiligen Bereich erzeugt. Diese Gleichverteilung ist ein entscheidendes Kriterium für die Güte des Zufallszahlengenerators. Wir betrachten dazu einmal die Funktion rand() aus Microsoft Excel die Zufallszahlen berechnet und stellen diese in einem dreidimensionalen Raum grafisch dar.

Wir können erkennen das die Anordnung der Ergebnisse teilweise zentrisch ist, allerdings in der Gesamtheit die komplette Sphäre einnehmen. Das bedeutet die Funktion liefert gute, gleichverteilte Werte über das gesamte Spektrum gesehen.

Nun liefern Funktionen, wie die aus Microsoft Excel oder der C-Standardbibliothek bekannten Funktion rand(), in Wahrheit keine tatsächlichen Zufallszahlen, sondern pseudozufällige Zahlen. Als Pseudozufall wird bezeichnet, was zufällig erscheint, in Wirklichkeit jedoch berechenbar ist. Ein Generator auf dem Computer ist daher in der Regel ein Pseudozufallszahlengenerator (engl. PRNG, pseudo random number generator) und kein echter Zufallszahlengenerator. PRNG erzeugen eine Zahlenfolge, die zwar zufällig aussieht, es aber nicht wirklich ist, da sie durch einen deterministischen Algorithmus berechnet wird. Bei jedem Start der Zufallszahlenberechnung mit gleichem Startwert, der so genannten Saat (engl. seed), wird die gleiche pseudozufällige Zahlenfolge erzeugt.

Dies lässt sich in der Sprache C sehr gut bei der Funktion rand() beobachten und ist ein häufig gemachter Anfängerfehler. Oft wird nämlich für die Initialisierung mithilfe von srand() ein gleichbleibender Wert herangezogen, wodurch die Zufallszahl dieselbe bleibt. Abhilfe schafft hier beispielsweise die Initialisierung mit der Funktion time() als Seed. Letztenendes bleibt das Ergebnis, nämlich die Zufallszahl, in Wirklichkeit aber eine Pseudozufallszahl.

/* Es werden 10 Zufallszahlen zwischen 0.0 und 1.0 ausgegeben. */
 
#include <stdio.h>
#include <stdlib.h>
 
int rand(void);
 
int main()
{
    int i;
 
    srand((unsigned)time(NULL));    // Mit aktuellen Zeit initialisieren.
 
    for(i = 1; i <= 10; i++)
        printf(" %2d. Zufallszahl:   %.f\n", i, (double)rand() / RAND_MAX);
 
    return 0;
}

Oftmals sind die von rand() generierten Zufallszahlen hinreichend. In kryptographischen Programmen und Anwendungen, die auf Zufallszahlen hoher Güte angewiesen sind, sollten allerdings bessere Methoden für die Erzeugung von Zufallszahlen genutzt werden. Eine Möglichkeit ist, spezielle Quellen des Betriebssystems zu nutzen. Diese und weitere Varianten werden nachfolgend detailliert beschrieben.

Entropie

Die Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichens, das in einem System oder einer Informationsfolge steckt. So besitzt eine geordnete Datenreihe (z.B. 10101010101010101010) die Entropie 0, oder nahe 0. Die Menge an Zufall einer Reihe lässt sich durch diese Entropie bzw. den Informationsgehalt quantifizieren, bezüglicher der sich Bitreihen unterscheiden. Dies ist Gegenstand der Informationstheorie, die erstmals von Claude Shannon formalisiert wurde.

In Rechnerarchitekturen stellt die Entropie eine Quelle für das Betriebssystem dar. Genauer gesagt kann die Entropie als der Zufall, der von einem Betriebssystem oder einem Programm gesammelt wird, um beispielsweise kryptographischen Zwecken zugeführt zu werden, beschrieben werden. In der Praxis wird dieser Zufall meist mithilfe der Hardware erlangt, beispielsweise durch Aufzeichnung der Mausbewegungen oder der Spin-Up Zeit der Festplatte.

Unter Linux generiert der Kernel die Entropie mitunter aus den Tastaturzeiten, Mausbewegungen und IDE-Timings und stellt diese Zufallsdaten, seit der Linux-Version 1.3.30 allen Systemprozessen, mithilfe einer besonderen Datei namens /dev/random, zur Verfügung. Microsoft Windows besitzt eine ähnliche Funktion in der CryptoAPI (CAPI), eine Schnittstelle die diverse kryptographische Funktionen bereitstellt. Programmierer können die CAPI nutzen um zufällige Zahlen zu erhalten, indem sie CAPIs CryptGenRandom aufrufen, nachdem sie diese korrekt initialisiert haben.

//--------------------------------------------------------------------
// Declare and initialize variables (msdn).
 
HCRYPTPROV   hCryptProv;
BYTE         pbData[16];
 
//--------------------------------------------------------------------
//  This code assumes that a cryptographic context has been acquired 
//  For code details, see "Example C Program: Duplicating a Session 
//  Key."
 
//--------------------------------------------------------------------
// Generate a random initialization vector.
 
if(CryptGenRandom(hCryptProv, 8, pbData)) {
     printf("Random sequence generated. \n");
} else {
     printf("Error during CryptGenRandom.\n");
     exit(1);
}

In dem gezeigten Beispiel werden 8 zufällige Bytes generiert, die im Buffer pbData abgelegt werden. CryptGenRandom wird als kryptographisch sicherer PRNG eingestuft.

Echte Zufallszahlen

Echte Zufallszahlen werden mit Hilfe physikalischer Phänomene erzeugt: Münzwurf, Würfel, Roulette, Rauschen, radioaktive Zerfallsprozesse oder quantenphysikalische Effekte. Oft werden beispielsweise Impulsschwankungen elektronischer Schaltungen (z. B. thermisches Rauschen eines Widerstands oder radioaktive Zerfallsvorgänge) ausgenutzt. Diese Schaltungen werden auf kleinen Platinen realisiert, die sich leicht in ein schmales Gehäuse integrieren lassen. Das Ausgangssignal der Schaltung wird dem Computer als Seed zugeführt.

Diese Verfahren nennen sich physikalische Zufallszahlengeneratoren, sind jedoch zeitlich oder technisch recht aufwändig. Physikalische Zufallszahlengeneratoren gelten nicht als schnell, da eine Unabhängigkeit und Gleichverteilung der erzeugten Zufallszahlen nur durch hinreichend große Abstände bei der Beobachtung der physikalischen Prozesse bzw. Abfangverfahren erreicht werden können. Dies ist aber nur eine Frage der verwendeten Technik, denn Zufallsprozesse wie thermisches Rauschen haben Grenzfrequenzen von vielen Terahertz.

Algorithmen

Alle bisherigen Informationen haben gezeigt das hinter dem Großteil der vom Computer produzierten Zufallszahlen Algorithmen stecken, die aufgrund ihrer natürlichen deterministischen Natur so genannte Pseudozufallszahlen generieren. Sie werden in aller Regel mit dieser Art von Zufallszahlen auskommen, da für die meisten Anwendungen diese Zahlen hinreichend zufällig sind. Wir werden uns in diesem Tutorial nicht nur darauf beschränken bestehende Algorithmen zu nutzen, dafür liefern alle großen Bibliotheken (.NET Framework Class Library, C++ Boost Library) bereits entsprechende Implementierungen von Haus aus mit, stattdessen werden wir die Funktionsweise der dahinterstehenden Algorithmen etwas näher betrachten.

Die Qualität eines Algorithmus bestimmt letztenendes die Güte eines Pseudozufallszahlengenerators die durch statistische Eigenschaften charakterisiert wird. Dazu gehört die erzeugte Verteilung (z. B. Normalverteilung, Gleichverteilung, Exponentialverteilung etc.) oder die Unabhängigkeit aufeinanderfolgender Zahlen. Wie gut die erzeugten Zahlen den statistischen Vorgaben entsprechen, bestimmt die Güte eines Pseudozufallszahlengenerators.

Meist werden periodische Zahlenfolgen erzeugt, die gleichen Zahlen wiederholen sich also nach einer bestimmten Länge. Ihr Vorteil ist die hohe Geschwindigkeit. Durch geschickte Wahl der Parameter kann man die Periode genügend groß machen. Einige Pseudozufallszahlengeneratoren generieren nur endliche Zahlenfolgen. Die bedeutendsten Pseudozufallszahlengeneratoren sind rekursive arithmetische Zufallszahlengeneratoren. Im nachfolgenden werden wir uns mit der Arbeitsweise der Algorithmen vertraut machen, insbesondere mit der Art und Weise nach welchen Prinzip ein Generator statistisch verteilte Zufallszahlen erzeugt und welche mathematischen Grundlagen dahinter stecken.

Gaußsche Normalverteilung

In der Wahrscheinlichkeitsrechnung gibt die Wahrscheinlichkeitsverteilung an, wie sich die Wahrscheinlichkeiten auf die möglichen Zufallsergebnisse, insbesondere die möglichen Werte einer Zufallsvariable, verteilen. Bei der Entwicklung eines Zufallszahlengenerators spielt es eine entscheidende Rolle wie die produzierten Resultate statistisch verteilt sind. Wir hatten in dem eingangs gezeigten Bild veranschaulicht, wie Ergebnisse, die mit der aus Microsoft Excel bekannten Funktion rand() berechnet wurden, statistisch im Raum verteilt sind.

Die Wahrscheinlichkeitsverteilung erfasst also den Zufall in einem stochastischen Vorgang quantitativ und stellt das theoretische Gegenstück zur empirischen Häufigkeitsverteilung dar, die sich aus der Analyse von Daten (z.B. Messwerten) ergibt.

Dabei unterscheidet man die Art der Verteilungen. Neben den diskreten Verteilungen, die sich auf eine endliche oder abzählbare Menge konzentrieren, gibt es die stetigen (kontinuierlichen) Verteilungen, die sich auf größere Bereiche erstrecken und bei denen einzelne Punkte die Wahrscheinlichkeit 0 haben. Ein prototypischer Vertreter von stetigen Verteilungen, durch den sich viele reale Situationen approximativ beschreiben lassen und der mathematisch einfach zu behandeln ist, ist die Normalverteilung, bei der die Wahrscheinlichkeiten einer Gaußschen Glockenkurve folgen.

Zahlreiche Zufallsvariable in der Naturwissenschaft und Technik, wie z.B. physikalisch-technische Meßgrößen genügen einer stetigen Verteilung mit der Dichtefunktion

Das nachfolgende Bild zeigt den typischen Verlauf dieser Funktion.

Dichtefunktion: f(x) der Gaußschen Normalverteilung („Gaußsche Glockenkurve“)

Die in der Dichtefunktion auftretenden Parameter μ und σ > 0 sind zugleich spezielle Kennwerte dieser allgemeinen Normalverteilung: μ ist der Mittel- oder Erwartungswert, σ die Standardabweichung und σ² die Varianz der normalverteilten stetigen Zufallsvariablen X. Die Verteilungsfunktion der allgemeinen Normalverteilung besitzt dabei die folgende Integraldarstellung:

Der Verlauf ist im folgenden Bild wiedergegeben.

Verteilungsfunktion: F(x) der Gaußschen Normalverteilung

Anhand der grafischen Darstellung im vorletzten Bild kann man erkennen das die Funktion f(x) einer Glocke ähnelt. Daher der Name „Gaußsche Glockenkurve“. Die variablen Parameter μ und σ beeinflussen das Aussehen dieser Glockenkurve. Während μ das Maximum festlegt bestimmt der zweite Parameter σ Breite und Höhe der Kurve. Je kleiner die Standardabweichung σ ist, desto höher liegt das Maximum und umso steiler fällt die Dichtekurve nach beiden Seiten hin ab. Unser nächstes Bild zeigt drei verschiedene Parameter. Es wird bei der Darstellung sehr oft das Symbol N(μ; σ) verwendet. Bei einer der drei Kurven handelt es sich um eine besondere Normalverteilung, nämlich der Standardnormalverteilung.

Normalverteilungen: Dichten von normalverteilten Zufallsgrößen mit unterschiedlichen Parametern

Die Abhängigkeit der Funktion von den Parametern μ und σ wird besonders deutlich, wenn man eine mehrdimensionale Verallgemeinerung der Normalverteilung vornimmt. Die so genannte multivariate Normalverteilung ist eine gemeinsame Wahrscheinlichkeitsverteilung mehrerer Zufallsvariablen und wird deshalb auch mehrdimensionale Verteilung genannt.