Zufallszahlengenerator: Wie generieren Computer Zufallszahlen?

Menschen wurden mit Zufallszahlen für Jahrtausende, so das Konzept ist nicht neu. Von der Lotterie im alten Babylon über Roulette-Tische in Monte Carlo bis hin zu Würfelspielen in Vegas ist es das Ziel, das Endergebnis dem Zufall zu überlassen.

Abgesehen vom Glücksspiel hat Zufälligkeit viele Verwendungsmöglichkeiten in Wissenschaft, Statistik, Kryptographie und vielem mehr. Die Verwendung von Würfeln, Münzen oder ähnlichen Medien als zufälliges Gerät hat jedoch seine Grenzen.

Aufgrund der mechanischen Natur dieser Techniken erfordert das Erzeugen großer Mengen von Zufallszahlen viel Zeit und Arbeit. Dank des menschlichen Einfallsreichtums stehen uns leistungsfähigere Werkzeuge und Methoden zur Verfügung.

Methoden zur Erzeugung von Zufallszahlen

Wahre Zufallszahlen

Freiform-Elektronikroboter schaut sich um

Betrachten wir zwei Hauptmethoden zur Erzeugung von Zufallszahlen. Die erste Methode istbasierend auf einem physikalischen Prozess und erntet die Quelle der Zufälligkeit aus einem physikalischen Phänomen, von dem erwartet wird , dass es zufällig ist .

Ein solches Phänomen findet außerhalb des Computers statt. Es wird gemessen und auf mögliche Verzerrungen aufgrund des Messprozesses eingestellt. Beispiele hierfür sind der radioaktive Zerfall, der photoelektrische Effekt, die kosmische Hintergrundstrahlung, das atmosphärische Rauschen (das wir in diesem Artikel verwenden werden) und vieles mehr.

Somit werden Zufallszahlen, die auf der Grundlage einer solchen Zufälligkeit erzeugt werden, als " wahre " Zufallszahlen bezeichnet.

Technisch gesehen besteht der Hardwareteil aus einem Gerät, das Energie von einer Form in eine andere umwandelt (z. B. Strahlung in ein elektrisches Signal), einem Verstärker und einem Analog-Digital-Wandler, um den Ausgang in eine digitale Zahl umzuwandeln.

Was sind Pseudozufallszahlen?

Binärer Hacker-Angriffscode.  Hergestellt mit Canon 5d Mark III und analogem Vintage-Objektiv, Leica APO Macro Elmarit-R 2.8 100 mm (Jahr: 1993)

Als Alternative zu "wahren" Zufallszahlen umfasst das zweite Verfahren zum Erzeugen von Zufallszahlen Rechenalgorithmen, die scheinbar zufällige Ergebnisse liefern können.

Warum scheinbar zufällig? Da das Ende erhaltenen Ergebnisse sind in der Tat vollständig von einem Anfangswert bestimmt , auch bekannt als der Samen Wert oder Schlüssel . Wenn Sie also den Schlüsselwert und die Funktionsweise des Algorithmus kennen, können Sie diese scheinbar zufälligen Ergebnisse reproduzieren.

Zufallszahlengeneratoren dieses Typs werden häufig als Pseudozufallszahlengeneratoren bezeichnet und geben daher Pseudozufallszahlen aus.

Obwohl dieser Generatortyp normalerweise keine Daten aus Quellen natürlich vorkommender Zufälligkeit sammelt, kann ein solches Sammeln von Schlüsseln bei Bedarf ermöglicht werden.

Vergleichen wir einige Aspekte von echten Zufallszahlengeneratoren oder TRNGs und Pseudozufallszahlengeneratoren oder PRNGs .

PRNGs sind schneller als TRNGs. Aufgrund ihrer deterministischen Natur sind sie nützlich, wenn Sie eine Folge von zufälligen Ereignissen wiedergeben müssen. Dies hilft zum Beispiel beim Testen von Code sehr.

Andererseits sind TRNGs nicht periodisch und funktionieren in sicherheitsrelevanten Rollen wie der Verschlüsselung besser.

Ein Punkt ist die Anzahl der Iterationen, die ein PRNG durchläuft, bevor es sich wiederholt. Wenn alle anderen Dinge gleich sind, würde ein PRNG mit einem längeren Zeitraum mehr Computerressourcen benötigen, um vorherzusagen und zu knacken.

Beispielalgorithmus für den Pseudozufallszahlengenerator

Ein Computer führt Code aus, der auf einer Reihe von Regeln basiert, die befolgt werden müssen. Für PRNGs im Allgemeinen drehen sich diese Regeln um Folgendes:

  1. Akzeptieren Sie eine anfängliche Eingabenummer, dh einen Startwert oder Schlüssel.
  2. Wenden Sie diesen Startwert in einer Folge von mathematischen Operationen an, um das Ergebnis zu generieren. Dieses Ergebnis ist die Zufallszahl.
  3. Verwenden Sie diese resultierende Zufallszahl als Startwert für die nächste Iteration.
  4. Wiederholen Sie den Vorgang, um die Zufälligkeit zu emulieren.

Schauen wir uns nun ein Beispiel an.

Der lineare Kongruenzgenerator

Dieser Generator erzeugt eine Reihe von Pseudozufallszahlen. Bei einem anfänglichen Startwert X 0 und ganzzahligen Parametern a als Multiplikator, b als Inkrement und m als Modul wird der Generator durch die lineare Beziehung definiert: X n ≡ (aX n-1 + b) mod m . Oder verwenden Sie eine programmierfreundlichere Syntax: X n = (a * X n-1 + b)% m .

Jedes dieser Mitglieder muss die folgenden Bedingungen erfüllen:

  • m> 0 (der Modul ist positiv),
  • 0 <a <m (der Multiplikator ist positiv, aber kleiner als der Modul),
  • 0b <m (dieInkrement ist nicht negativ, aber kleiner als der Modul) und
  • 0X 0 <m (der Keim ist nicht negativ, aber kleiner als der Modul).

Erstellen wir eine JavaScript-Funktion, die die Anfangswerte als Argumente verwendet und ein Array von Zufallszahlen einer bestimmten Länge zurückgibt:

 // x0=seed; a=multiplier; b=increment; m=modulus; n=desired array length; const linearRandomGenerator = (x0, a, b, m, n) => { const results = [] for (let i = 0; i < n; i++) { x0 = (a * x0 + b) % m results.push(x0) } return results } 

Der lineare Kongruenzgenerator ist einer der ältesten und bekanntesten PRNG-Algorithmen.

Zufallszahlengeneratoralgorithmen, die von Computern ausgeführt werden können, stammen bereits aus den 1940er und 50er Jahren (z. B. die Middle-Square-Methode und der Lehmer-Generator) und werden bis heute geschrieben (Xoroshiro128 +, Squares RNG und mehr). .

Ein Beispiel für einen Zufallszahlengenerator

Als ich mich entschied, diesen Artikel über das Einbetten eines Zufallszahlengenerators in eine Webseite zu schreiben, hatte ich die Wahl.

Ich hätte die JavaScript- Math.random()Funktion als Basis verwenden und eine Ausgabe in Pseudozufallszahlen generieren können, wie ich es in früheren Artikeln getan habe (siehe Multiplikationstabelle - Code Your Own Times Table).

In diesem Artikel selbst geht es jedoch darum, Zufallszahlen zu generieren. Deshalb habe ich mich entschlossen zu lernen, wie man "echte" zufällige Daten sammelt und meine Entdeckung mit Ihnen teilt.

Unten ist also der "wahre" Zufallszahlengenerator. Stellen Sie die Parameter ein und klicken Sie auf Generieren.

True Random Number Generator Binär Dezimal Hexadezimal Generieren Ergebnis:

The code fetches data from one of the APIs, courtesy of Random.org. This online resource has a plethora of useful, customizable tools and comes with excellent documentation to go with it.

The randomness comes from atmospheric noise. I was able to use asynchronous functions. That is a huge benefit going forward. The core function looks like this:

 // Generates a random number within user indicated interval const getRandom = async (min, max, base) => { const response = await  fetch("//www.random.org/integers/?num=1&min="+min+" &max="+max+"&col=1&base="+base+"&format=plain&rnd=new") return response.text() }

The parameters it takes allow a user to customize random number output. For example, min and max allow you to set lower and upper limits on generated output. And base determines if the output is printed as binary, decimal or hexadecimal.

Again, I chose this configuration but there are many more available at the source.

Wenn Sie auf die Schaltfläche Generieren klicken, wird die handleGenerate()Funktion aufgerufen. Es ruft wiederum die getRandom()asynchrone Funktion auf, verwaltet die Fehlerbehandlung und gibt die folgenden Ergebnisse aus:

 // Output handling const handleGenerate = () => { handleActive(generateButton) const base = binary.checked ? 2 : decimal.checked ? 10 : 16 if (!minimum.value || !maximum.value) { prompter.style.color = 'red' prompter.textContent = "Enter Min & Max values" } else { getRandom(minimum.value, maximum.value, base).then((data) => { resultValue.textContent = data prompter.textContent = "" }).catch((error) => { resultValue.textContent = 'ERROR' prompter.textContent = 'Connection error. Unable to generate'; }) handleRestart() } } 

Der Rest des Codes befasst sich mit der HTML-Struktur, dem Erscheinungsbild und dem Stil.

Der Code kann in diese Webseite eingebettet und verwendet werden. Ich habe es in Bestandteile zerlegt und mit detaillierten Kommentaren versehen. Es kann leicht geändert werden. Sie können die Funktionen und Stile auch nach Bedarf ändern.

Dies ist der Link zum GitHub-Repo des vollständigen Codes: //github.com/sandroarobeli/random-generator