Zahlengenerator

Die Generierung von Zufallszahlen ist ein Prozess, bei dem auf Abruf eine völlig unvorhersehbare Zahl erzeugt wird. Dabei ist es unmöglich, aus zuvor generierten Zahlen ein Muster abzuleiten. Diese Zufallszahlen können entweder durch einen softwarebasierten Algorithmus oder durch spezielle Hardware-Geräte erzeugt werden.

Die Verwendung von Zufallszahlengeneratoren

Zufallszahlengeneratoren (RNGs) kommen in unzähligen Bereichen zum Einsatz – von einfachen Computerspielen bis hin zu hochkomplexen Webanwendungen. Ein alltägliches Beispiel: Websites nutzen einen Zufallszahlengenerator, um Werbebanner oder bestimmte Anzeigenblöcke in rotierender, unvorhersehbarer Reihenfolge auszuspielen. Auch in der Kryptographie sind Zufallszahlen unverzichtbar, etwa um einzigartige Chiffren oder sichere Verschlüsselungsschlüssel zu generieren.

Konkret wird die Generierung von Zufallszahlen genutzt für: Captchas, Datenverschlüsselungen, die Erzeugung von Salts für die sichere Passwortspeicherung, Passwortgeneratoren, das Mischen von Karten in Online-Casinos, algorithmische Entscheidungsfindungen, statistische Stichproben und komplexe Simulationen.

Besonders in Videospielen ist der Algorithmus des Zufallszahlengenerators allgegenwärtig. Selbst wenn Sie ein Level mehrfach spielen, wird der Ablauf bei jedem Versuch leicht variieren. Diese Unterschiede zeigen sich vielleicht nicht im grundlegenden Leveldesign, aber in der Anzahl und den Spawnpunkten der Gegner, in dynamischen Wetterveränderungen oder in den unerwarteten Hindernissen, auf die Sie stoßen. Genau dieser Zufallsfaktor macht das Spielen immer wieder spannend.

Der Unterschied zwischen einer zufälligen und einer nicht zufälligen Folge

Betrachten wir einmal folgende Zahlenfolge: 1 , 2 , 3 , 4 , 5. Ist diese wirklich zufällig?

Eine Zufallsvariable nimmt als Ergebnis eines Versuchs einen von mehreren möglichen Werten an. Das entscheidende Merkmal ist, dass Sie das Eintreffen eines bestimmten Wertes im Vorfeld unmöglich exakt vorhersagen können.

Angenommen, die oben genannten Zahlen wurden durch das Tippen auf der oberen Tastenreihe einer Tastatur erzeugt. In diesem Fall ist die Kombination keineswegs zufällig: Nach der 5 lässt sich die folgende Zahl, die 6, mit sehr hoher Wahrscheinlichkeit vorhersagen.

Eine Folge ist folglich nur dann wirklich zufällig, wenn absolut keine Abhängigkeit zwischen den einzelnen Symbolen besteht.

Die Grundbedingung für einen korrekten und fairen Zufallszahlengenerator ist die exakt gleiche Wahrscheinlichkeit für jede mögliche Zahl, die das System ausgeben kann. Das bedeutet, dass der Zufallsfaktor völlig isoliert betrachtet werden muss – es spielt absolut keine Rolle, welche Zahlen zuvor generiert wurden oder danach folgen.

Nehmen wir als Beispiel einen klassischen sechsseitigen Würfel. Beim ersten Wurf kann jede Zahl von 1 bis 6 mit exakt der gleichen Wahrscheinlichkeit fallen. Unabhängig vom Ergebnis dieses ersten Wurfs bleibt die Wahrscheinlichkeit für jede Zahl auch beim zweiten, beim hundertsten oder beim tausendsten Wurf unverändert.

Auch die Dezimalstellen der Zahl Pi scheinen sich nie zu wiederholen und wirken auf viele völlig zufällig. Wenn unser hypothetischer Generator nun die binäre Darstellung von Pi nutzt und an einem unbekannten Punkt beginnt, könnte er in vielen Szenarien unvorhersehbar wirken und sogar bestimmte Zufallstests bestehen. Für kryptografische Zwecke birgt die Nutzung von Pi jedoch enorme Risiken: Gelingt es einem Angreifer, das verwendete Segment von Pi zu identifizieren, kann er sowohl die vorhergehenden als auch die folgenden Zahlen exakt berechnen und so die gesamte Systemsicherheit kompromittieren.

Um solche Schwachstellen aufzudecken, hat das U.S. National Institute of Standards and Technology (NIST) das "Statistical Test Package for Random and Pseudorandom Number Generators for Cryptographic Applications" entwickelt. Dieses Paket umfasst 15 statistische Tests, die den Grad der Zufälligkeit von Bits messen, die von Hardware- oder Software-Generatoren erzeugt wurden.

Die Arten von Zufallszahlengeneratoren

Grundsätzlich unterscheidet man zwei Arten von Zufallszahlengeneratoren: Echte Zufallszahlengeneratoren (True Random Number Generators, TRNG) und Pseudozufallszahlengeneratoren (Pseudorandom Number Generators, PRNG). TRNGs nutzen physikalische Phänomene zur Zahlengenerierung, während PRNGs auf mathematischen Algorithmen basieren.

Ein echter Zufallszahlengenerator wird in der Regel hardwareseitig realisiert. Er nutzt winzige, unvorhersehbare physikalische Prozesse – die sogenannte Entropie – um Zufallszahlen zu erzeugen. Entropie lässt sich am besten als reines, ungefiltertes Chaos beschreiben.

Echte Zufallszahlengeneratoren nutzen physikalische Phänomene wie:

• Radioaktivität,
• thermisches Rauschen,
• elektromagnetisches Rauschen,
• Quantenmechanik und andere.

Ein TRNG (True RNG) ist der weltweite Standard für sicherheitskritische Systeme und hochgradige Verschlüsselungen.

Diese Generatoren sammeln Entropie aus ihren jeweiligen Quellen, um einen Startwert (Seed) zu generieren, der als Basis für die echten Zufallszahlen dient.

Pseudozufallszahlengeneratoren (PRNGs) kommen hingegen dort zum Einsatz, wo keine kritischen Sicherheitsanforderungen bestehen. Hier dient die Zufälligkeit vor allem dazu, Wiederholungen zu vermeiden und Anwendungen für den Nutzer dynamischer zu gestalten. Die Implementierung von PRNG-Technologie ist deutlich kostengünstiger und schneller, da sie keine spezielle Hardware erfordert und nahtlos in jeden Programmcode integriert werden kann. Obwohl die Ergebnisse durch einen Algorithmus bestimmt werden und nicht im strengen Sinne "echt zufällig" sind, eignen sie sich hervorragend für Computerspiele und herkömmliche Software.

Ein PRNG nutzt einen einzigen anfänglichen Startwert (Seed), aus dem sich die gesamte pseudozufällige Kette errechnet. Ein echter Zufallszahlengenerator hingegen erzeugt kontinuierlich frische, absolut unvorhersehbare Werte, indem er konstant neue Daten aus seinen Entropiequellen abgreift.

Die Erzeugung von Pseudozufallszahlen hat jedoch Schwachstellen. Sie funktioniert nur deshalb so gut, weil die Ergebnisse für das ungeschulte Auge zufällig wirken. Kennt man jedoch den Startwert (Seed) einer bestimmten PRNG-Sequenz, lassen sich alle folgenden Zahlen mühelos vorhersagen.

Speedrunner und ambitionierte Gamer machen sich diese Schwäche häufig zunutze – ein Vorgang, der als "RNG-Manipulation" bekannt ist. Sie zwingen das Spiel in vorhersehbare Muster, um Level in Rekordzeit abzuschließen. In Videospielen führt dies glücklicherweise zu keinen ernsthaften Problemen.

Es gibt jedoch Szenarien, in denen die Vorhersagbarkeit von Zufallszahlen katastrophale Folgen haben kann – etwa bei der Generierung von Sicherheitsschlüsseln.

Findet ein Angreifer den Startwert heraus, der zur Erstellung von RSA-Schlüsseln in TLS-Zertifikaten verwendet wurde, könnte er den gesamten verschlüsselten Netzwerkverkehr abfangen und entschlüsseln. Dadurch fallen ihm Passwörter, Bankdaten und andere sensible persönliche Informationen in die Hände.

In solch kritischen Systemen ist eine absolut sichere Methode zur Erzeugung von Zufallszahlen zwingend erforderlich: Hier führt kein Weg an einem echten Hardware-Zufallszahlengenerator (TRNG) vorbei.

Googles Generator

Google bietet ein eigenes, JavaScript-basiertes Tool zur Generierung von Zufallszahlen an. Dieser einfache, aber effektive Generator ist besonders praktisch für Gesellschaftsspiele oder schnelle Verlosungen. Sie finden das Tool ganz einfach, indem Sie in der Google-Suche den Begriff "Zufallszahlengenerator" eingeben.

Die lineare kongruente Methode

Einer der bekanntesten und am weitesten verbreiteten Algorithmen für Pseudozufallszahlengeneratoren ist die lineare kongruente Methode (Linear Congruential Generator, LCG). Sie wurde 1949 von Derrick Henry Lehmer entwickelt und wird für einfache Anwendungen genutzt, besitzt jedoch absolut keine kryptografische Stärke.

Um Zahlen nach dieser Methode zu generieren, müssen vier Basiswerte definiert werden:

m > 0, Modulo

0 ≤ a ≤ m, der Multiplikator

0 ≤ c ≤ m, das Inkrement

0 ≤ X₀ ≤ m, die Anfangszahl (Seed)

Die eigentliche Sequenz der Zufallszahlen wird dann mithilfe dieser Formel berechnet:

Xₙ₊₁ = (aXₙ + c) mod m

Es ist wichtig zu betonen, dass die Qualität der Zufallszahlen extrem stark von der Wahl dieser Parameter abhängt.

Nehmen wir als Beispiel folgendes Set:

X₀ = 3, a = 4, c = 5, m = 6

Das Ergebnis ist eine kurze, sich ständig wiederholende Sequenz:

3, 5, 1, 3, 5, 1

Dies sieht offensichtlich nicht nach einem echten Zufall aus.

Ändern wir die Parameter jedoch zu:

X₀ = 2, a = 85, c = 507, m = 1356

Dann wird die Streuung der Ergebnisse sofort deutlich unvorhersehbarer. Die Parameter für diesen Algorithmus müssen also mit enormer Sorgfalt gewählt werden:

2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365...

Obwohl die lineare kongruente Methode statistisch gesehen eine brauchbare pseudozufällige Zahlenfolge erzeugen kann, ist sie kryptografisch völlig wertlos. LCG-basierte Generatoren sind vorhersehbar und dürfen unter keinen Umständen für Verschlüsselungen verwendet werden.

Bereits 1977 wurden Generatoren, die auf der linearen kongruenten Methode basieren, von Jim Reeds geknackt; 1982 folgte Joan Boyar. Boyar gelang es darüber hinaus auch, quadratische und kubische Generatoren zu entschlüsseln. Damit war die Untauglichkeit kongruenter Methoden für die Kryptografie endgültig bewiesen. Für nicht-kryptografische Zwecke, wie etwa komplexe Computersimulationen, sind LCG-Generatoren jedoch nach wie vor äußerst nützlich. Sie sind ressourcenschonend, schnell und liefern in den meisten empirischen Tests gute statistische Ergebnisse.

Moderne Hardware-Zufallszahlengeneratoren

QRBG121

Dieser hardwarebasierte Zufallszahlengenerator nutzt den quantenphysikalischen Prozess der Photonenemission in Halbleitern. Dabei werden einzelne Photonen völlig unabhängig voneinander und streng nach dem Zufallsprinzip detektiert. Die zeitlichen Abstände zwischen der Erfassung dieser Photonen werden direkt in unvorhersehbare Bits übersetzt.

Lavalampen

Das Unternehmen Cloudflare nutzt an seinem Hauptsitz in San Francisco eine Wand voller "Lavalampen" als Zufallszahlengenerator. Eine solche Lampe besteht aus einem Glasgefäß, das mit klarem Öl und durchscheinendem Wachs (Paraffin) gefüllt ist. Wachs ist im kalten Zustand schwerer als Öl, steigt aber auf, sobald es durch eine Glühbirne am Boden erwärmt wird, da sich seine Dichte verringert.

Die chaotischen und unvorhersehbaren Bewegungen dieser Flüssigkeiten werden von mehreren Kameras gefilmt. Die daraus resultierenden Videobilder werden in digitale Zahlenfolgen umgewandelt, aus denen Cloudflare dann hochsichere Verschlüsselungsschlüssel generiert.

Die beiden anderen Cloudflare-Standorte nutzen alternative Methoden zur Entropiegewinnung: In London filmen Kameras die unvorhersehbaren Bewegungen eines Systems aus drei chaotischen Doppelpendeln. In Singapur hingegen erfasst ein Geigerzähler den radioaktiven Zerfall eines kleinen Stücks Uran. Uran dient hier als perfekte Datenquelle, da der genaue Zeitpunkt jedes einzelnen radioaktiven Zerfalls physikalisch absolut zufällig ist.

HotBits

HotBits ist ein faszinierender Online-Dienst, der echte Zufallszahlen frei zur Verfügung stellt. Diese Zahlen werden von einem Geigerzähler generiert, der die natürliche ionisierende Strahlung der Umgebung misst. Nutzer können auf der Website ein Anfrageformular ausfüllen, die gewünschte Menge an Zufallsbytes angeben und die bevorzugte Abrufmethode wählen. Ein wichtiges Sicherheitsmerkmal: Sobald die Zufallszahlen an den Nutzer übermittelt wurden, werden sie unwiderruflich aus dem HotBits-System gelöscht.

Vakuum-Quantenfluktuationen

Entgegen seinem Namen (vom lateinischen "vacuus" für leer) ist ein Vakuum auf subatomarer Ebene niemals völlig leer. Gemäß der Heisenbergschen Unschärferelation entstehen und vergehen im Vakuum unaufhörlich sogenannte virtuelle Teilchen.

Kanadische Physiker haben auf Basis dieser Vakuumfluktuationen einen extrem schnellen und strukturell eleganten Zufallszahlengenerator entwickelt. Das System besteht aus einem gepulsten Laser mit extrem hoher Frequenz, einem Medium mit hohem Brechungsindex (einem Diamanten) und einem hochsensiblen Detektor. Wenn die Laserimpulse den Diamanten durchdringen, verändert jeder Impuls seine Eigenschaften minimal, beeinflusst von den mikroskopischen Vakuumfluktuationen auf dem Weg der Photonen.

Diese winzigen Schwankungen erzeugen unvorhersehbare Spektrallinien im Streulicht. Da Vakuumfluktuationen die reinste Form des Zufalls darstellen, unterscheiden sich diese Linien bei jeder Messung auf absolut chaotische Weise.

Kohlenstoff-Nanoröhren-Generator

Dieser innovative Ansatz kombiniert extreme Kompaktheit mit der Erzeugung von thermischem Rauschen.

Forscher haben einen Zufallszahlengenerator aus einer statischen RAM-Speicherzelle (SRAM) entwickelt, die mit einer speziellen Tinte aus halbleitenden Kohlenstoff-Nanoröhren gedruckt wurde. Diese Speicherzelle nutzt natürliche Schwankungen des thermischen Rauschens, um kryptografisch sichere Zufallsbits zu erzeugen.

Der große Vorteil: Der Kohlenstoff-Nanoröhren-Generator kann direkt auf flexible Kunststoffoberflächen gedruckt werden. Dadurch lässt er sich problemlos in winzige elektronische Bauteile, tragbare Sensoren, smarte Kleidung oder sogar in Einwegetiketten integrieren.

Cubes und die Electronic Frontier Foundation (EFF)

Die Electronic Frontier Foundation (EFF) hat eine simple, aber hocheffektive Methode entwickelt, um extrem sichere Passwörter mithilfe eines rein physischen Zufallszahlengenerators zu erstellen: den klassischen Spielwürfeln. Diese Methode wird oft als "Diceware" bezeichnet.

Dabei werfen Sie beispielsweise fünf Würfel gleichzeitig und notieren die Augenzahlen von links nach rechts – das ergibt zum Beispiel die Zahlenfolge 63131. Anschließend suchen Sie diese Nummer in der offiziellen, langen Wortliste auf der EFF-Website. In diesem Fall entspricht die 63131 dem englischen Wort "Turbofan".

Diesen Vorgang wiederholen Sie mehrmals, beispielsweise fünfmal, um eine Passphrase aus fünf zufälligen Wörtern zu generieren (z. B. "turbofan purge unfitting try pruning"). Wer grundlegende Mnemotechniken beherrscht, kann sich solche scheinbar absurden Wortketten erstaunlich leicht einprägen, während sie für Computer praktisch unmöglich zu knacken sind.

Ein Quanten-Zufallszahlengenerator von einem Nokia Smartphone

Im Jahr 2014 bewiesen Forscher der Universität Genf, dass sich sogar alltägliche Hardware als Quanten-Zufallszahlengenerator (QRNG) nutzen lässt. Sie verwendeten dafür die Kamera eines handelsüblichen Nokia N9 Smartphones.

Das Prinzip war genial einfach: Die Smartphone-Kamera zählte die exakte Anzahl der Photonen, die auf jedes einzelne Pixel des Bildsensors trafen, während eine Standard-LED als Lichtquelle diente. Jedes Pixel der 8-Megapixel-Kamera erfasste in einem Bruchteil einer Sekunde rund 400 Photonen. Da die Lichtemission auf Quantenebene zufällig erfolgt, schwankte diese Zahl minimal. Diese Abweichungen der Photonenanzahl über alle Pixel hinweg wurden ausgelesen und in eine hochsichere, quantenmechanische Zufallszahlenfolge umgewandelt.