Wie Zufallszahlengeneratoren wirklich arbeiten
Der meiste Zufallszahlencode ist subtil verzerrt. Hier steht, wo – und warum das selten auffällt, bis es auffällt.
Pseudozufall gegen kryptografisch sicher
Ein PRNG ist ein deterministischer Algorithmus mit internem Zustand. Bei gleichem Startwert liefert er dieselbe Folge – für Simulationen ein Vorteil, für Passwörter ein fataler Fehler. Math.random() ist einer: einmal pro Seite initialisiert, vorhersagbar, wenn man genug Ausgabe beobachtet.
Ein CSPRNG schöpft aus dem Entropiepool des Betriebssystems und ist so gebaut, dass beobachtete Ausgabe keine Vorhersage künftiger Ausgabe erlaubt. Browser stellen ihn als crypto.getRandomValues() bereit.
Das Problem der Modulo-Verzerrung
Die übliche Abkürzung ist `randomUint32() % n`. Sieht harmlos aus, aber 2^32 ist durch die meisten Werte von n nicht teilbar. Bei n = 3 erhalten 0, 1 und 2 jeweils 1.431.655.765, 1.431.655.765 und 1.431.655.766 Möglichkeiten – eine winzige Bevorzugung von 2, die nie verschwindet, egal wie viele Stichproben genommen werden.
Die Lösung ist Rejection Sampling: das größte Vielfache von n berechnen, das in 2^32 passt, jede Ziehung darüber verwerfen und erst dann den Rest nehmen. Das kostet eine seltene Neuziehung und beseitigt die Verzerrung vollständig.
Gleitkomma macht es schlimmer
`Math.floor(Math.random() * n)` hat dieselbe Problemklasse bei großem n, dazu die Tatsache, dass ein Double 53 Bit Mantisse hat – oberhalb von 2^53 lassen sich manche Ganzzahlen gar nicht darstellen, ein weiterer Bereich verliert also stillschweigend Werte.
Bei Dezimalwerten ist der verlässliche Weg, auf Ganzzahlen zu skalieren, zu ziehen und zurückzudividieren. Durchgehend in Gleitkomma zu arbeiten bringt Rundung ein, die ein Ergebnis knapp außerhalb des gewünschten Bereichs schieben kann.
Warum Gleichverteilung bei einer Verlosung zählt
Eine Verzerrung von 0,00000002 % ist bei einem Würfelwurf irrelevant und bei einer Verlosung immer noch irrelevant. Dieselbe verzerrte Funktion für Sitzungstoken oder Schlüssel ist etwas anderes: Verzerrung ist genau die Struktur, mit der ein Angreifer einen Suchraum verkleinern kann.
Die praktische Regel: Math.random() für kosmetische Effekte, ein CSPRNG mit Rejection Sampling für alles, woraus jemand Vorteile ziehen könnte, wenn er es vorhersagt.
Häufige Fragen
Reicht Math.random() für einen Zufallsauswähler?
Für die Wahl eines Restaurants ja. Für eine Verlosung mit Preis eine kryptografische Quelle nutzen, damit das Ergebnis für niemanden vorhersagbar oder reproduzierbar ist, der die Seite beobachtet.
Was ist Modulo-Verzerrung in einem Satz?
Wenn sich der Bereich einer Zufallszahl nicht glatt in den Ausgabebereich des Generators teilt, werden manche Ergebnisse etwas wahrscheinlicher als andere.
Kann ein Browser echten Zufall erzeugen?
Nein. Echter Zufall braucht eine physikalische Entropiequelle. Das Betriebssystem sammelt Entropie aus Hardware-Ereignissen und initialisiert damit den CSPRNG – das ist der praktische Standard für Sicherheit.