Zufallszahlen-Generator: Math.random vs. CSPRNG und Fisher-Yates

Inhalt
Wer Gewinner einer Verlosung ermittelt oder Preise und Lottozahlen auslost, braucht vor allem zwei Dinge: ein faires und nicht vorhersagbares Ergebnis. Auch wenn auf dem Bildschirm scheinbar zufällige Zahlen erscheinen, geht das Vertrauen in die Ziehung verloren, sobald die interne Umsetzung verzerrt ist oder sich der nächste Wert vorhersagen lässt. In diesem Beitrag erfahren Sie, warum die Zufallszahlen in JavaScript dabei zum Problem werden können und wie Sie ohne Verzerrung fair auslosen.
Zusammenfassung
- ①
Math.random()ist ein vorhersagbarer Pseudozufallszahlengenerator (PRNG) und eignet sich daher nicht für Situationen, in denen Fairness zählt, etwa bei der Auslosung von Preisen oder Gewinnern.- ② Mit einem CSPRNG auf Basis von
crypto.getRandomValues(), dem Fisher-Yates-Shuffle und Reservoir Sampling lässt sich ohne Verzerrung fair auslosen.- ③ Wenn Ihnen die eigene Umsetzung zu aufwendig ist, können Sie mit unserem Tool direkt eine faire Auslosung auf CSPRNG-Basis durchführen.
Warum das Zufallsverfahren das Ergebnis einer Auslosung bestimmt
Ein Computer ist ein deterministisches System, das festgelegte Algorithmen abarbeitet. Allein mit Software lassen sich deshalb keine völlig zufälligen Werte erzeugen. Stattdessen werden Pseudozufallszahlen verwendet: Werte, die nur wie Zufallszahlen aussehen und berechnet werden. Von diesem Berechnungsverfahren hängt ab, wie fair eine Auslosung ist.
Die Grenzen von Math.random()
Math.random() arbeitet auf Grundlage eines Pseudozufallszahlengenerators (PRNG, Pseudo-Random Number Generator). JavaScript-Engines wie V8 verwenden intern Algorithmen der Familie xorshift128+ oder LCG (Linear Congruential Generator).
- Determinismus durch den Seed: Sobald der Anfangswert (Seed) und der interne Zustand feststehen, ist die danach erzeugte Zahlenfolge festgelegt.
- Vorhersagbarkeit: Beobachtet man mehrere Zufallszahlen hintereinander, lassen sich der vorherige Zustand oder der nächste Wert mathematisch rekonstruieren und vorhersagen.
- Manipulationsrisiko: Bei Preisverlosungen oder der Auswahl von Gewinnern könnte jemand das nächste Muster berechnen und so seine Gewinnchance durch Betrug erhöhen.
Verzerrung durch fehlerhaften Shuffle-Code
Der Code array.sort(() => Math.random() - 0.5) wird häufig verwendet, um eine Liste zufällig zu mischen oder K Elemente ohne Wiederholung zu ziehen. Bei kurzen Arrays scheint er problemlos zu funktionieren, erzeugt aber eine statistische Verzerrung.
Die Anzahl aller möglichen Permutationen von N Elementen beträgt N! (N Fakultät). Ruft ein JavaScript-Sortieralgorithmus (QuickSort, Timsort usw.) jedoch eine zufällige Vergleichsfunktion auf, liegt die Zahl der intern möglichen Entscheidungsverläufe in etwa bei N^N. In den meisten Fällen ist N^N kein ganzzahliges Vielfaches von N!. Dadurch entsteht ein Ungleichgewicht: Bestimmte Permutationen treten häufiger auf als andere.
So lösen Sie eine Auslosung fair und ohne Verzerrung
Damit eine Auslosung frei von Verzerrungen (Bias) bleibt, müssen drei Dinge zusammenkommen: (1) eine unvorhersehbare Zufallsquelle, (2) ein Mischalgorithmus, bei dem jede Permutation mit der gleichen Wahrscheinlichkeit auftritt, und (3) ein Ziehverfahren, das auch bei großen Datenmengen zuverlässig funktioniert. Im Folgenden finden Sie die Grundlagen und den Code für eine eigene Umsetzung.
1) Unvorhersehbare Zufallszahlen mit crypto.getRandomValues()
crypto.getRandomValues() nutzt einen kryptografisch sicheren Pseudozufallszahlengenerator (CSPRNG, Cryptographically Secure PRNG).
- Entropiequelle: Auf Betriebssystemebene sammelt das System Entropie aus physikalischen Vorgängen, etwa aus Mausbewegungen, Zeitstempeln von CPU-Interrupts oder dem Rauschen bei Tastatureingaben.
- Nicht umkehrbar: Selbst wenn alle früher erzeugten Zufallszahlen bekannt sind, lässt sich der nächste Wert praktisch nicht vorhersagen und der interne Seed nicht zurückverfolgen.
- Fairness: Überall dort, wo Vertrauenswürdigkeit wichtig ist – etwa bei Sachpreisen mit Geldwert, bei der Gewinnerauslosung oder bei der Erzeugung kryptografischer Schlüssel –, sollte ein CSPRNG zum Einsatz kommen.
Wenn Sie eine mit crypto.getRandomValues() erzeugte 32-Bit-Ganzzahl (0 bis 2^32-1) in den gewünschten Bereich [0, M-1] umrechnen und dafür einfach nur % M (Modulo-Operation) anwenden, entsteht ein Modulo-Bias. Solange 2^32 kein Vielfaches von M ist, werden die vorderen Zahlen nämlich minimal häufiger gezogen. Um das zu vermeiden, berechnen Sie mit dem Rejection Sampling (Verwerfungsverfahren) einen Grenzwert:
Rejection Limit = 2^32 − (2^32 mod M)
Ist die gezogene Zufallszahl R größer oder gleich diesem Grenzwert, wird sie verworfen und es wird neu gezogen. So erhalten Sie eine gleichmäßige Wahrscheinlichkeitsverteilung.
2) Fisher-Yates-Shuffle: alle Permutationen mit gleicher Wahrscheinlichkeit
Beim Fisher-Yates-Shuffle (Variante nach Durstenfeld) beginnt man am Ende des Arrays (N-1), wählt aus dem noch nicht festgelegten vorderen Bereich (0 bis i) einen zufälligen Index j und vertauscht die beiden Positionen.
- Zeitkomplexität: O(N), das Array wird nur einmal durchlaufen.
- Speicherkomplexität: O(1), die Elemente werden ohne zusätzliches Array an Ort und Stelle gemischt.
Berechnet man die Wahrscheinlichkeit, dass ein bestimmtes Element an Position i landet, sieht man, warum das Verfahren gleichverteilt ist:
- Die Wahrscheinlichkeit, dass ein bestimmtes Element an die letzte Position (N-1) des Arrays gezogen wird, beträgt 1/N.
- Die Wahrscheinlichkeit, dass ein bestimmtes Element an die vorletzte Position (N-2) gezogen wird, ergibt sich (es darf im vorherigen Schritt nicht gezogen worden sein und muss in diesem Schritt gezogen werden) zu (1 − 1/N) × 1/(N-1) = (N-1)/N × 1/(N-1) = 1/N.
- Allgemein gilt für die k-te Position: (N-1)/N × (N-2)/(N-1) × … × (k-1)/k × 1/(k-1) = 1/N.
Jedes Element landet also mit genau der Wahrscheinlichkeit 1/N an einer beliebigen Position, und jede der N! möglichen Permutationen tritt ebenfalls mit der gleichen Wahrscheinlichkeit 1/N! auf.
3) Große Datenmengen mit Reservoir Sampling verarbeiten
Soll aus einem großen Bereich wie 1 bis 1 Million eine kleine Anzahl von Werten ohne Wiederholung gezogen werden, oder sollen aus einem Datenstrom, dessen Gesamtumfang vorab nicht bekannt ist, K Elemente ausgelost werden, ist es ineffizient, das gesamte Array im Speicher aufzubauen und zu mischen. Hier kommt das Reservoir Sampling zum Einsatz.
Man legt ein Reservoir-Array der Größe K an, liest die Daten des Streams nacheinander ein und geht dabei so vor. Dabei ist i wie im Code ein bei 0 beginnender Index:
- Die ersten K Elemente (Index 0 bis K-1) werden ohne Bedingung in das Reservoir übernommen.
- Trifft ein Element mit dem Index i ein (mit i ≥ K), wird eine zufällige Ganzzahl j zwischen 0 und i erzeugt.
- Ist j kleiner als K, wird das j-te Element des Reservoirs durch den Eingabewert mit dem aktuellen Index i ersetzt.
Bei insgesamt N Datenelementen berechnen wir nun die Wahrscheinlichkeit, dass ein bestimmtes Element nach dem letzten Schritt im Reservoir verbleibt. Für ein Element, das als n-tes im Stream eintrifft (Zählung ab 1; im 0-basierten Index des Codes entspricht das i = n − 1), beträgt die Wahrscheinlichkeit, bis zum Ende im Reservoir zu bleiben:
P(Gewinn) = K/n × (1 − 1/(n+1)) × (1 − 1/(n+2)) × … × (1 − 1/N) = K/n × n/(n+1) × (n+1)/(n+2) × … × (N-1)/N = K/N
Auch ohne die Gesamtgröße N vorab zu kennen, lassen sich so mit nur einem Durchlauf (O(N)) und Speicher in der Größenordnung O(K) faire Stichproben von K aus N Elementen ohne Zurücklegen ziehen.
Umsetzung im Code: CSPRNG + Fisher-Yates + Reservoir Sampling
Der folgende TypeScript-Code enthält alles zusammen: die Beseitigung des Modulo-Bias auf CSPRNG-Basis, den Fisher-Yates-Shuffle und das Reservoir Sampling.
/**
* Zufällige Ganzzahl auf CSPRNG-Basis (ohne Modulo-Bias)
* @param min Minimalwert (inklusive)
* @param max Maximalwert (inklusive)
*/
export function getRandomIntSecure(min: number, max: number): number {
if (min > max) {
throw new Error("min muss kleiner oder gleich max sein.");
}
const range = max - min + 1;
if (range === 1) return min;
const totalValues = 0x100000000; // 2^32
const limit = totalValues - (totalValues % range);
const array = new Uint32Array(1);
let randomValue: number;
do {
crypto.getRandomValues(array);
randomValue = array[0];
} while (randomValue >= limit);
return min + (randomValue % range);
}
/**
* Fisher-Yates-Ziehung ohne Wiederholung auf CSPRNG-Basis (K Elemente)
* @param array Ursprüngliches Array der Teilnehmer bzw. Zahlen
* @param k Anzahl der zu ziehenden Gewinner (ohne Angabe: gesamtes Array mischen)
*/
export function pickRandomItems<T>(array: T[], k?: number): T[] {
const result = [...array];
const count = k !== undefined ? Math.min(k, result.length) : result.length;
for (let i = result.length - 1; i > result.length - 1 - count; i--) {
const j = getRandomIntSecure(0, i);
[result[i], result[j]] = [result[j], result[i]];
}
return result.slice(result.length - count);
}
/**
* Reservoir Sampling für große Bereiche bzw. Datenströme
* @param min Startwert des Bereichs
* @param max Endwert des Bereichs
* @param k Anzahl der zu ziehenden Gewinner
*/
export function reservoirSampleRange(min: number, max: number, k: number): number[] {
const total = max - min + 1;
const sampleCount = Math.min(k, total);
const reservoir: number[] = [];
// 1. Reservoir mit den ersten K Werten füllen
for (let i = 0; i < sampleCount; i++) {
reservoir.push(min + i);
}
// 2. Für das i-te Element zufällig entscheiden, ob es ersetzt wird
for (let i = sampleCount; i < total; i++) {
const currentValue = min + i;
const j = getRandomIntSecure(0, i);
if (j < sampleCount) {
reservoir[j] = currentValue;
}
}
return reservoir;
}
Ist das Ergebnis fair? Prüfung mit dem Chi-Quadrat-Anpassungstest
Ob ein Auslosungswerkzeug bestimmte Nummern oder Teilnehmer bevorzugt, lässt sich mit einem statistischen Test überprüfen. Bei insgesamt N Ziehungsversuchen und K Kategorien bezeichnen wir die tatsächlich beobachtete Häufigkeit mit Oᵢ und die theoretisch erwartete Häufigkeit mit Eᵢ = N/K. Die Chi-Quadrat-Teststatistik χ² ist dann definiert als:
χ² = Σ(i=1 bis K) (Oᵢ − Eᵢ)² / Eᵢ
- Nullhypothese (H₀): Der Zufallsalgorithmus folgt einer gleichmäßigen Wahrscheinlichkeitsverteilung ohne Verzerrung.
- Freiheitsgrade (df): K − 1
- Entscheidungskriterium: Ist die berechnete χ²-Teststatistik kleiner als der kritische Chi-Quadrat-Wert beim Signifikanzniveau (α = 0,05), gilt die Auslosung statistisch als unverzerrt.
Einen solchen statistischen Test selbst zu implementieren und jedes Mal durchzuführen, ist aufwendig. Das folgende Auslosungswerkzeug arbeitet bereits mit Beseitigung des Modulo-Bias auf CSPRNG-Basis und mit dem Fisher-Yates-Shuffle. Sie erhalten also ohne eigenen Prüfcode direkt ein unverzerrtes Ergebnis.
Kostenlos · auf kryptografischen Zufallszahlen basierend · faire Auslosung ohne Wiederholung

Math.random() und crypto.getRandomValues() im Vergleich
| Merkmal | Math.random() | crypto.getRandomValues() |
|---|---|---|
| Erzeugungsverfahren | Pseudozufallszahlen (PRNG) | Kryptografisch sichere Pseudozufallszahlen (CSPRNG) |
| Vorhersagbarkeit | Aus früheren Werten lässt sich der nächste Wert abschätzen | Rückrechnung praktisch unmöglich |
| Seed-Quelle | Interner Zustand des Algorithmus | Physikalische Entropie auf Betriebssystemebene |
| Geeigneter Einsatz | Spieleffekte, einfache Zufallseffekte | Verlosung von Preisen und Gewinnern, Erzeugung kryptografischer Schlüssel |
So sorgen Sie in der Praxis für Fairness
Neben dem Algorithmus ist auch ein transparenter Ablauf wichtig.
- Seed bzw. Hash vorab veröffentlichen: Wenn Sie vor der Auslosung den SHA-256-Hashwert der Teilnehmerliste oder den Seed-Wert öffentlich bekannt geben, etwa auf einer offiziellen Plattform, kann nach der Auslosung jeder dasselbe Ergebnis nachvollziehen und überprüfen.
- Bildschirmaufzeichnung und Protokolle aufbewahren: Zeichnen Sie den gesamten Ablauf auf – von der Eingabe der Liste über den Klick auf die Auslosungsschaltfläche bis zur Ergebnisanzeige. Bewahren Sie außerdem die gezogenen Zufallswerte und das Zeitprotokoll auf, um sie bei Bedarf vorlegen zu können.
- Doppelte Einträge bereinigen: Mehrfachteilnahmen derselben Person (Telefonnummer, E-Mail-Adresse, Konto-ID) fassen Sie vor der Auslosung zu einem einzigen Eintrag zusammen.
- Clientbasiertes Tool verwenden: Um die Möglichkeit von Manipulationen auf Serverseite zu verringern, empfiehlt sich ein Auslosungs-Tool, das
crypto.getRandomValues()direkt im Browser ausführt.
Fazit
Für eine faire Auslosung sollten Sie anstelle des vorhersagbaren Math.random() einen CSPRNG auf Basis von crypto.getRandomValues() verwenden und die Permutation nicht mit array.sort(), sondern mit dem Fisher-Yates-Shuffle erzeugen. Bei großen Datenmengen gelingt die Ziehung mit Reservoir Sampling ohne hohe Speicherbelastung, und mit dem Chi-Quadrat-Test lässt sich die Gleichverteilung der Ergebnisse überprüfen. Wenn Sie nichts selbst implementieren, sondern direkt ein faires Auslosungsergebnis sehen möchten, probieren Sie unten das Tool aus.
Kostenlos · auf kryptografischen Zufallszahlen basierend · faire Auslosung ohne Wiederholung
Häufig gestellte Fragen
Q1. Gibt es rechtliche Probleme, wenn Gewinner mit Math.random() ermittelt wurden?
Bei kleinen internen Aktionen oder einer Auslosung nur zum Spaß ist die Verwendung von Math.random() meist unproblematisch. Bei hochwertigen Geldpreisen oder offiziellen Aktionen von Behörden und Unternehmen sollten Sie jedoch einen Zufallsalgorithmus auf CSPRNG-Basis verwenden, um Zweifel an der Vorhersagbarkeit der Zufallszahlen und an einer möglichen Verzerrung auszuräumen.
Q2. Macht es einen Unterschied bei der Gewinnchance, ob zuerst der 1. oder zuerst der 5. Platz gezogen wird?
Bei einem gleichverteilten Zufalls-Shuffle wie dem Fisher-Yates-Algorithmus ist die Gewinnchance aller Teilnehmenden unabhängig von der Ziehungsreihenfolge gleich. Für den Ablauf der Veranstaltung ist es allerdings meist spannender, mit den niedrigeren Rängen zu beginnen.
Q3. Wann ziehe ich mit Zurücklegen und wann ohne Zurücklegen?
Ohne Zurücklegen (keine Duplikate) ziehen Sie dann, wenn eine bereits gezogene Nummer oder Person nicht erneut gezogen werden darf, etwa bei der Erzeugung von Lottozahlen oder der Auswahl von Gewinnern. Mit Zurücklegen (Duplikate erlaubt) ziehen Sie, wenn bei jeder Ziehung dieselbe Wahrscheinlichkeit gelten muss, etwa beim Würfeln.
Dieser Artikel basiert auf unserem koreanischen Original. Koreanisches Original lesen