Funktionsweise von Zufallszahlengeneratoren: PRNGs, CSPRNGs und echte Zufälligkeit

Zufallszahlen ermöglichen Werbegeschenke, Spiele, Simulationen, Passwörter und Verschlüsselung. Das Überraschende daran ist, dass die meisten Zufallszahlen überhaupt nicht zufällig sind. Sie entstehen durch einen deterministischen Prozess, der von außen unvorhersehbar erscheint.

Wichtige Erkenntnisse

• Ein Pseudozufallszahlengenerator (PRNG) wandelt einen Startwert in eine lange, wiederholbare Sequenz um.
• Ein kryptografisch sicheres PRNG (CSPRNG) ist so konzipiert, dass vergangene Ausgaben praktisch keine Rückschlüsse auf zukünftige Ausgaben ermöglichen.
• Wahre Zufälligkeit entsteht durch physikalische Entropiequellen, nicht nur durch einen Algorithmus.

– Browser stellen ein CSPRNG über crypto.getRandomValues() bereit, was die richtige Wahl für alltägliche Messeauslosungen ist.

• Fairness hängt auch davon ab, wie Werte einem Bereich zugeordnet werden: Voreingenommene Modulo-Arithmetik kann einige Ergebnisse stillschweigend begünstigen.

Warum Zufälligkeit schwieriger ist, als es aussieht

Ein Computer folgt Anweisungen. Wenn Sie dasselbe Programm zweimal mit denselben Eingaben ausführen, erhalten Sie normalerweise dieselbe Ausgabe. Ein Zufallszahlengenerator muss diese Erwartung brechen, ohne die Maschine zu zerstören.

Software löst das Problem normalerweise in zwei Schichten. Erstens sammelt es eine kleine Menge unvorhersehbarer Daten, Entropie genannt, aus Quellen wie Timing-Jitter, Tastaturereignissen oder Hardware-Rauschen. Zweitens nutzt es diese Entropie als Ausgangspunkt für einen Algorithmus, der einen langen Zahlenstrom erzeugt. Der Stream sieht zufällig aus, wird aber vollständig durch den Seed und den Algorithmus bestimmt.

Dieses Design ist nützlich. Es macht Zufallszahlen für Simulationen und Tests reproduzierbar. Dies bedeutet auch, dass ein schlecht gesäter Generator die gleiche Sequenz auf verschiedenen Maschinen wiederholen kann, weshalb die Qualität des Saatguts wichtig ist.

Was ein Pseudozufallszahlengenerator macht

Ein PRNG behält einen internen Zustand bei. Jedes Mal, wenn Sie nach einer Zahl fragen, wird der Zustand umgewandelt und ein Teil des Ergebnisses zurückgegeben. Die Transformation ist normalerweise schnell und deterministisch. Bei gleichem Ausgangszustand erscheint die gleiche Sequenz erneut.

Die meisten PRNGs wiederholen schließlich ihren Zustand. Die Anzahl der Werte vor der Wiederholung wird als Periode bezeichnet. Ein langer Zeitraum ist hilfreich, macht einen Generator aber nicht automatisch sicher. Ein Angreifer, der genügend Ausgaben beobachten kann, kann möglicherweise den internen Zustand rekonstruieren und zukünftige Werte vorhersagen.

PRNG versus CSPRNG

Ein Allzweck-PRNG ist auf Geschwindigkeit und statistische Qualität optimiert. Ein CSPRNG ist so konzipiert, dass es Vorhersagen widersteht. Es verwendet kryptografische Grundelemente und ist so aufgebaut, dass das Erlernen einer Ausgabe nicht die nächste preisgeben sollte.

Math.random() von JavaScript ist nicht für sicherheitsrelevante Arbeiten geeignet. Es ist schnell und bequem, aber Engines garantieren keine kryptografische Qualität. Browser stellen crypto.getRandomValues() für sicherheitsrelevante Zufälligkeiten bereit. Es füllt ein typisiertes Array mit zufälligen Bytes unter Verwendung der kryptografischen Quelle der Plattform.

Verwenden Sie für Passwörter, Token, faire Verlosungen mit einem Preis und alles, was ein Angreifer vorhersagen möchte, ein CSPRNG. Für eine dekorative Animation oder eine grobe Simulation kann ein normales PRNG ausreichen.

Woher der wahre Zufall kommt

Kein Softwarealgorithmus kann Informationen aus dem Nichts erzeugen. Echte Zufälligkeit dringt durch physikalische Prozesse in das System ein: radioaktiver Zerfall, thermisches Rauschen oder das genaue Timing von Benutzereingaben. Betriebssysteme sammeln diese Signale in einem Entropiepool und verwenden sie zum Seeding kryptografischer Generatoren.

Moderne Betriebssysteme und Browser mischen die Entropie kontinuierlich. Sie müssen Ihre Maus nicht bewegen, um eine faire Auslosung zu erzielen, aber das System benötigt beim Booten und nach längeren Zeiträumen ohne Aktivität eine gesunde Entropiequelle. Dies ist einer der Gründe, warum kryptografische Generatoren sorgfältig entwickelt und nicht improvisiert werden.

Wie die Generatoren auf dieser Site funktionieren

Die Tools auf dieser Website verwenden crypto.getRandomValues() in Ihrem Browser. Die Ergebnisse werden lokal generiert und nicht hochgeladen.

Für ganzzahlige Bereiche gibt der Browser einen 32-Bit-Wert ohne Vorzeichen zurück. Ein naiver Ansatz verwendet den Rest nach der Division, aber das kann zu einer kleinen Verzerrung führen, wenn der Bereich nicht gleichmäßig in den gesamten 32-Bit-Raum aufgeteilt wird. Stattdessen verwenden die Generatoren eine Ablehnungsstichprobe: Werte außerhalb des unverzerrten Bereichs werden verworfen und neu gezeichnet. Das Ergebnis ist eine gleichmäßige Verteilung über den gewünschten Bereich.

Shuffles verwenden den Fisher-Yates-Algorithmus mit sicheren Zufallsindizes. Im Gegensatz zu einer zufälligen Sortierung mit einem Zufallskomparator erzeugt Fisher-Yates jede Permutation mit gleicher Wahrscheinlichkeit, wenn die Zufallsindizes einheitlich sind.

Was ist für Ihren Anwendungsfall zufällig genug?

Verwenden Sie gewöhnliche Pseudozufälligkeit für Animationen, Spielgrafiken oder grobe Simulationen, bei denen Vorhersagbarkeit keine Kosten verursacht. Verwenden Sie ein CSPRNG für:

• Passwörter und Wiederherstellungscodes.
• Giveaways, Tombolas und Castings mit einem echten Preis.
• Zufällige Zuweisung von Personen zu Teams oder Gruppen.

– Token, Sitzungskennungen und alles, was mit der Sicherheit zu tun hat.

• Jede Auslosung, die Sie möglicherweise öffentlich verteidigen müssen.

Verwenden Sie für langfristige kryptografische Schlüssel ein dediziertes Schlüsselverwaltungssystem anstelle einer Website. Die Zufälligkeit des Browsers ist stark, aber der Lebenszyklus, die Speicherung und die Zugriffskontrolle von Schlüsseln sind genauso wichtig wie die ersten Bits.

Eine einfache Fairnessprüfung

Sie können einen Generator informell testen, indem Sie viele Ziehungen ausführen und sich die Verteilung ansehen. Bei einem sechsseitigen Würfel sollte jedes Gesicht in etwa einem Sechstel der Fälle erscheinen. Bei kurzen Auflagen kann es zu Abweichungen kommen und Streifen sind normal. Entscheidend ist, ob der Prozess über viele Versuche hinweg unvoreingenommen ist und ob er für eine Prüfung reproduzierbar genug ist.

Notieren Sie bei öffentlichen Ziehungen die Eingaben, die Einstellungen und das Ergebnis. Die Aufzeichnung trägt mehr zum Vertrauen bei als jeder Anspruch auf Zufälligkeit.

Fazit

Zufälligkeit ist eine Kette technischer Entscheidungen: Entropiesammlung, Algorithmusauswahl, unvoreingenommene Zuordnung und transparente Nutzung. Ein guter Generator muss nicht geheimnisvoll sein. Es muss unvorhersehbar sein, wo es darauf ankommt, dokumentiert sein, wo es verwendet wird, und ehrlich über seine Grenzen sein.