WikiDer > Pseudozufallsgenerator

EIN Pseudozufallsgenerator, (Englisch: Pseudozufallszahlengenerator (PRNG)), ist ein Algorithmus zum Erzeugen Pseudozufallszahlen, also eine Folge von scheinbar zufälligen Zahlen ohne jegliche Kohärenz. Dieses Verfahren wird auch als deterministischer Zufallsbitgenerator (DRBG) bezeichnet. Ein pseudozufälliger Zufallsgenerator wird verwendet, wenn Zahlen etwa unabhängig voneinander entfernt und es ist möglich, Zahlengruppen zu finden, die einer bestimmten Regel folgen (Gruppenverhalten).

Die Ausgabe, die der Pseudozufallsgenerator liefert, ist keineswegs zufällig, da sie vollständig von einer relativ kleinen Menge von Anfangswerten, dem sogenannten PRNG-Zustand, bestimmt wird. John von Neumann sagte dazu: "Jeder, der arithmetische Methoden zur Erzeugung von Zufallszahlen studiert, begeht natürlich eine Sünde." Obwohl Reihen eher wie echte sind zufällige Zahlen, die von Zufallszahlengeneratoren in Hardware erzeugt werden können, sind Pseudo-Zufallsgeneratoren nicht nur wegen ihrer Geschwindigkeit, sondern gerade wegen ihrer Reproduzierbarkeit interessant.

Pseudozufallsgeneratoren wurden entwickelt, da es zwar schwierig ist, "echte" Zufallszahlen zu erzeugen, in den meisten Situationen jedoch Pseudozufallszahlen anstelle von reellen Zufallszahlen benötigt werden. Pseudo-Zufallsgeneratoren sind für Computer einfach zu implementieren, sodass sie einfach und effektiv zu verwenden sind.

Pseudozufallszahlen sind wichtig in der Simulationspraxis (z. B. von physikalischen Systemen mit dem Monte-Carlo-Methode) und sind von zentraler Bedeutung für die Praxis der Kryptographie und Verfahrensgenerierung. Die meisten Pseudozufallsalgorithmen versuchen, eine Ausgabe zu erzeugen, die gleichmäßig verteilt ist. Viele Generatoren verwenden lineare Kongruenz. Andere sind inspiriert von der Fibonacci-Folge indem Sie zwei vorherige Werte hinzufügen oder verwenden Schieberegister bei dem das vorherige Ergebnis nach einer Zwischenverarbeitung eingefügt wird. Jüngste Beispiele für kryptografische Pseudozufallsgeneratoren sind Blum Blum Shub (BBS), Fortuna (PRNG), Yarrow und die Mersenne-Twister.

Eine sorgfältige mathematische Analyse ist erforderlich, um den Grad der Zufälligkeit einer Pseudozufallszahl zu bestimmen. Robert R. Coveyou vom Oak Ridge National Laboratory schrieb in einem Artikel: "Zufallszahlen zu generieren ist zu wichtig, um sie dem Zufall zu überlassen."

Historische Entwicklung von Pseudo-Zufallsgeneratoren

Die Entwicklung von Algorithmen zur Erzeugung von Pseudozufallszahlen ist mit der Entwicklung der Kryptographie. Die militärische und wirtschaftliche Bedeutung dieser Wissenschaft hat im Laufe der Geschichte viele Forschungen motiviert.

Verschlüsselungen Jahrhundert verwendet wurde, hing von der Geheimhaltung der verwendeten Methoden ab. Heutzutage sind diese Methoden nicht mehr praktikabel, da es viele statistische Theorien gibt, die aus den Ergebnissen den Generierungsalgorithmus ermitteln können. Zudem können Verschlüsselungstechnologien nicht mehr geheim gehalten werden. Im 1883 gab der niederländische Sprachwissenschaftler und Kryptograf Auguste Kerckhoffs eine Grundregel der modernen Kryptographie: Die Sicherheit eines kryptographischen Systems darf nicht von der Geheimhaltung des Verschlüsselungssystems abhängen, sondern nur von der Geheimhaltung der Schlüssel abhängen. Diese Regel, gepaart mit der Entwicklung von Nachrichtenverschlüsselungsalgorithmen, markiert den Beginn der Entstehung der Pseudozufallszahlengeneratoren.

Die Bedeutung von Pseudozufallsgeneratoren war jedoch begrenzt, da der physikalische Berechnungsweg für die erforderlichen langen, sich wiederholenden Berechnungen unbequem ist. Der Aufstieg von Pseudo-Zufallsgeneratoren begann wirklich von 1946, dann John von Neumann veröffentlichte seinen „Middle Square Generator“. In den folgenden Jahren war es die beliebteste und auch die schnellste Algorithmus das wurde verwendet. Im 1948 gefüttert Derrick Henry Lehmer lineare Kongruenzgeneratoren in, die in 1958 wurden von G.J. Mitchell und D. P. Moore. Sie wurden schließlich sehr populär und werden in den grundlegendsten Verschlüsselungsfunktionen verwendet.

Diese ersten Pseudo-Zufallsgeneratoren sind sehr beliebt, trotz ihrer relativ schlechten statistischen Eigenschaften und obwohl sie nicht den Bedürfnissen von Kryptographen entsprechen. In jüngerer Zeit wurden Algorithmen entwickelt, die gegenüber der statistischen Analyse stärker waren, wie z Mersenne Twister-Algorithmus (1997) oder die Methode von Fibonaccia.

Aber kein Pseudozufallsgenerator kann ein Ergebnis liefern, das wirklich frei von jeder statistischen Analyse ist. Hauptsächlich, weil theoretisch der Startwert selbst willkürlich sein sollte und der Algorithmus nicht verwendet werden kann, um sich selbst zu initialisieren. Daher müssen aktuelle kryptografische Generatoren einen Grad an Zufälligkeit hinzufügen, der nicht auf deterministische Weise erzeugt wird. Wir blicken jetzt in Richtung gemischter Generatoren. Sie müssen über einen Zufallszahlengenerierungsalgorithmus verfügen und in der Lage sein, beliebig in einer physikalischen Produktionsweise zu initialisieren.

Periodizität

Ein pseudozufälliger Zufallsgenerator kann aus jeder Ausgangssituation mit zugehörigem Ausgangszustand bzw. Startwert gestartet werden. Bei gleichen Startwerten wird immer die gleiche Zahlenfolge erzeugt. Die maximale Länge der Sequenz, bevor sie sich zu wiederholen beginnt, wird durch die Größe des Startwertes, gemessen in , bestimmt Bits. Da die Länge des Maximums Zeitspanne sich möglicherweise verdoppelt, wenn dem Startwert ein Bit hinzugefügt wird, ist es einfach, Pseudozufallszahlengeneratoren mit Perioden zu erstellen, die für viele praktische Anwendungen lang genug sind.

Wenn der Anfangswert eines pseudozufälligen Zufallsgenerators nein Bits darf die Periode nicht länger sein als ${Displaystil 2^{n}}$ einbiegen in. Linear-Feedback-Schieberegister (LFSRs) haben normalerweise Zeiträume von genauen ${Displaystil 2^{n}-1}$. Lineare Kongruenzgeneratoren haben Perioden, die berechnet werden können mit Faktorisierung. Mischungen beider Methoden haben durchschnittliche Perioden von etwa ${Displaystil 2^{n/2}}$. Mischungen, die reversibel sind (Permutationen) haben durchschnittliche Perioden ${Displaystil 2^{n-1}}$ und die Periode enthält immer den ursprünglichen Anfangszustand. Obwohl Pseudozufallszahlengeneratoren ihre Sequenz nach Erreichen des Endes einer Periode wiederholen, bedeutet ein wiederholtes Ergebnis nicht, dass das Ende der Periode erreicht wurde, da der Anfangszustand größer als der Ausgang sein kann. Dies zeigt sich insbesondere bei Pseudo-Zufallsgeneratoren mit einer Ausgabe von 1 Bit.

Die meisten Pseudozufallszahlengeneratoren erzeugen Zahlenfolgen, die gleichmäßig verteilt sein. Eine offene Frage, die für die Theorie und Praxis von Kryptographie ist, ob es eine Möglichkeit gibt, die Ausgabe eines hochwertigen Pseudo-Zufallsgenerators von einer wirklich zufälligen Sequenz zu unterscheiden, ohne zu wissen, welcher Algorithmus verwendet wurde und wie der Ausgangszustand war. Die Sicherheit der meisten kryptographischen Algorithmen und Protokolle, die Pseudozufallsgeneratoren verwenden, basiert auf der Annahme, dass es unmöglich ist, zwischen der Verwendung eines geeigneten Pseudozufallsgenerators und einer echten Zufallsfolge zu unterscheiden.

Probleme

Wird ein Pseudo-Zufallsgenerator auf einem deterministischen Computer ausgeführt, wird er automatisch zu einem deterministischen Algorithmus. Die Ausgabe unterliegt unweigerlich einer Eigenschaft, die in echter zufälliger Reihenfolge fehlt: der Periodizität. Ein aperiodischer Generator ist nicht unmöglich, benötigt aber mehr Speicher, um nicht in den gleichen Zustand zurückzukehren. Um dieses theoretische Hindernis zu umgehen, kann der Generator in einem bestimmten Zustand (dem Startwert) starten. Bei gleichbleibendem Startwert führt er jedoch immer zum gleichen Ergebnis – was unter Umständen als Vorteil angesehen werden kann, insbesondere in Bezug auf Reproduzierbarkeit. Zudem ist die Anzahl der verwendbaren Startwerte nicht unendlich und der Generator kann nur eine begrenzte Anzahl unterschiedlicher Zahlenreihen erzeugen.

Um die Qualität der Ausgabe zu verbessern, können wir "beliebige" Komponenten aus den Unvollkommenheiten des Systems einführen, wie z. B. die Zeit zwischen dem Einschalten des Computers und dem Zugriff auf die Festplatte. Diese Werte sind jedoch durch Intervalle begrenzt und/oder teilweise vorhersehbar. Das System ist immer noch pseudozufällig.

Die Länge der maximalen Zeitspanne bis zu einer Wiederholung erhöht sich jedes Mal ein wenig, wenn dem internen Zustand Bits hinzugefügt werden. Es ist einfach, Pseudozufallsgeneratoren mit längeren Perioden zu bauen, als ein Computer berechnen könnte. Zum Beispiel die Mersenne-Twister ein mathematisch nachgewiesener Zeitraum von ${Displaystil 2^{19937}-1}$, eine astronomische Zahl.

Es bleibt eine unbeantwortete Frage, ob man zwischen einer pseudozufälligen, algorithmisch generierten Zahl und einer perfekten Zufallszahl unterscheiden kann. Und dies sollte möglich sein, ohne den Startwert des Generators zu kennen. In der Kryptographie gehen die meisten Experten davon aus, dass dies mit der heutigen Rechenleistung nicht möglich ist. Dieses Prinzip wird verwendet mit Stream-Verschlüsselungsalgorithmen wie RC4, wo ein XOROperation kombiniert die Pseudozufallszahlen mit gegebenen Zahlen.

Grundsätzlich haben die meisten Generatoren mathematische Probleme, die mit statistischen Analysen erkannt werden können. Die Qualität der Ausgabe wird oft auf Kosten der Produktionsgeschwindigkeit erhöht. Bei der Auswahl eines Generators sollten diese Parameter berücksichtigt werden. Folgende Probleme können auftreten:

• Kürzerer Zeitraum mit bestimmten Startwerten (diese Startwerte werden als schwach bezeichnet);
• Die Generatorqualität variiert stark je nach Startwert;
• Unvollkommene Verteilung, fehlende Gleichmäßigkeit;
• Schlechte Dimensionsverteilung der Ordnung der Ausgabe;
• Oder das Gegenteil: perfekte Verteilung, perfekte Gleichmäßigkeit;
• Aufeinanderfolgende Werte sind nicht unabhängig;
• Bestimmte Teile der Ausgabe sind weniger zufällig (zum Beispiel ist Bit Nummer 8 oft 1).

Die Defekte reichen von signifikant bis fast unsichtbar. Dem seit vielen Jahrzehnten verwendeten RANDU-Algorithmus werden systematische Fehler nachgesagt und einige der erhaltenen Ergebnisse können nicht vollständig validiert werden. Manchmal ermöglicht eine praktische Anwendung, das Problem zu erkennen (zB eine physikalische Simulation mit völlig unerwarteten Ergebnissen). Aber es ist besser zu testen, bevor der Algorithmus verwendet wird, damit Fehler rechtzeitig entdeckt werden können.

Beispiele bekannter Algorithmen

Mittelquadratmethode

Die Middle-Square-Methode ist eine computerbasierte PNRG-Methode. Dieser war in 1946 durch John von Neumann erfunden. Die Methode funktioniert so: Beginnen Sie mit einer beliebigen Zahl, quadrieren Sie sie und nehmen Sie die mittleren Ziffern der resultierenden Zahl. Diese Zahl kann dann als Startwert für die nächste Iteration verwendet werden.

Beispiel

Nehmen Sie als Startwert die Zahl 1234.

1. Quadrieren gibt ${Displaystil 1234^{2}=1522756}$. Dies kann als 01522756 geschrieben werden, eine 8-stellige Zahl, die das Quadrat einer 4-stelligen Zahl ist.
2. Nehmen Sie die mittleren vier Ziffern: 5227. Dies ist der Startwert für die nächste Iteration.
3. ${displaystyle 5227^{2}=27321529}$. Der neue Startwert ist also 3215.

Von Neumann verwendete für diese Methode 10-stellige Zahlen, aber das Prinzip war das gleiche.

Ein Problem bei der Middle-Square-Methode besteht darin, dass die Qualität der Ausgabe vom Startwert abhängt. Zum Beispiel erzeugt die Zahl „0000“ immer die gleiche Sequenz und bildet eine Art absorbierenden Zustand oder Attraktor des Algorithmus. Von Neumann war sich dessen bewusst, befürchtete aber, dass mathematische Lösungen die Fehler nur verbergen, anstatt sie zu beseitigen.

Von Neumann verwendet seine Methode auf dem ENIAC Computer. Er erreichte eine Generation, die 200-mal schneller war als die Ergebnisse, die er beim Lesen von Zahlen mit Nummern erhielt Lochkarten. Generatoren, die auf diesem Material basieren, könnten laut Von Neumann nicht richtig funktionieren, weil sie die Ergebnisse nicht speichern und somit nicht überprüfen könnten. Wenn sie die erzeugte Ausgabe behalten würden, würden sie den begrenzten Computerspeicher und damit die Fähigkeit des Computers, Zahlen zu generieren und zu lesen, erschöpfen. Die Methode der mittleren Quadrate wurde durch das Aufkommen aufwendigerer Generatoren ersetzt, wie z Monte-Carlo-Simulation.

Fibonacci-Methode

Diese Methode basiert auf der Fibonaccia-Folge, modular der maximale gewünschte Wert:

${displaystyle X_{n}äquivalent (X_{n-1} X_{n-2}){ mod {m}};;{mbox{with}};X_{0};{mbox{en}};X_{ 1};{mbox{als Eingabe.}}}$

Sie können auch eine Variante verwenden:

${displaystyle X_{n}äquivalent (X_{n-1} X_{nk}){ mod {m}};;{mbox{with}};X_{1},...,X_{k-1}; {mbox{als Eingabe.}}}$

Die Qualität des Generators hängt vom Wert von ab ${displaystyle k}$ und die Startwerte. Dieser Generator ist sehr einfach zu implementieren und verbraucht wenig Ressourcen.

Lineare Kongruenzgeneratoren

Im 1948 eingeführt Derrick Henry Lehmerlineare Kongruenzgeneratoren in reduzierter Form (keine Wertsteigerung) ${Anzeigestil c}$). Lineare Kongruenzgeneratoren wurden verallgemeinert und weit verbreitet. Sie basieren auf einer einfachen rekursiven Formel:

${displaystyle X_{n 1}äquivalent (acdot X_{n} c){ mod {m}}}$

mit Startwert ${displaystyle X_{0}}$. Im Allgemeinen ist der Startwert eine Primzahl, aber die genauen Einschränkungen dafür hängen vom Algorithmus ab. Einige Startwerte können zu degenerierten Sequenzen führen.

Die Periode dieses Generators ist maximal ${displaystyle m}$. Der Zeitraum ist daher relativ kurz, weil ${displaystyle m}$ wird oft so gewählt, dass Wörter auf dem Computer nach ihrer Länge geordnet werden. Aber diese Methode hat einen Vorteil: Wir kennen die Kriterien für die Zahlen ${Anzeigestil a}$, ${Anzeigestil c}$ und ${displaystyle m}$, die eine maximale Dauer (entspricht ${displaystyle m}$) erhalten.

Mersenne-Twister

Das Mersenne-Twister ist in 1997 erfunden von Makoto Matsumoto und Takuji Nishimura und ist vor allem für seine Qualität bekannt. Mit einem Zeitraum von ${Displaystil 2^{19937}-1}$ Iterationen verteilt der Mersenne-Twister die Zahlen gleichmäßig über 623 Dimensionen (für 32-Bit-Zahlen) und erweist sich als schneller als die meisten schwächeren statistischen Methoden. Es ist jedoch möglich, die Leistung des Mersenne-Twisters zu analysieren und dann festzustellen, dass die Leistung nicht völlig zufällig ist. Bis heute sind die einzigen negativen Auswirkungen mit der Kryptographie verbunden, daher ist der Mersenne-Twister kein kryptographischer Generator.

Kryptographisch sichere Pseudo-Zufallsgeneratoren

Ein für kryptografische Anwendungen geeignetes PRNG wird als kryptografisch sicheres PRNG (CSPRNG) bezeichnet. Eine Voraussetzung für ein CSPRNG ist, dass jemand, der den Anfangszustand nicht kennt, nur einen vernachlässigbaren Vorteil bei der Unterscheidung der erzeugten Ausgabe von einigen Zufallszahlenfolgen hat. Mit anderen Worten, während ein PRNG nur bestimmte statistische Tests bestehen muss, muss ein CSPRNG alle statistischen Tests bestehen, die auf die folgenden beschränkt sind: Polynomzeit im Umfang des Ausgangszustandes. Obwohl eine solche Eigenschaft nicht nachgewiesen werden kann, kann das CSPRNG einem bekannten Komplexitätsproblem verfolgen (z. in Primfaktoren zerlegen). Im Allgemeinen können Jahre der Forschung erforderlich sein, bevor ein Algorithmus als CSPRNG zertifiziert werden kann.

Generatoren, die sicher genug sind:

• Schafgarbe
• Vermögen
• Blum Blum Shub (sicher aber langsam)
• ISAAC

Anwendungen

Die Pseudo-Zufallsgeneratoren sind in verschiedenen Bereichen von großer Bedeutung. Zum Beispiel beim Austausch von Informationen über drahtlose Netzwerke. Dies erfordert einen Mechanismus, der die Vertraulichkeit der ausgetauschten Gegenstände am besten gewährleisten kann. Ein weiteres Beispiel für eine Anwendung von Pseudozufallsgeneratoren ist Kryptosysteme. Kryptoanalyse ist ein aufstrebendes Feld und zeigt eine hohe Zuverlässigkeit der bei der Verschlüsselung verwendeten Methoden. Das einfachste Beispiel für diese Methoden ist Flussverschlüsselung, wobei Text bitweise (Wort für Wort) in Geheimtext ist umgerechnet. Dieses Verfahren ist bekannt für seine Geschwindigkeit und seine Wettbewerbsfähigkeit gegenüber anderen Verfahren, da es bei der Übertragung weniger fehleranfällig ist.

Pseudo-Zufallsgeneratoren finden ihre ursprüngliche Anwendung im Satellitenpositionierungssystem Globales Positionsbestimmungssystem (GPS). Ziel ist es, eine Entfernung zwischen zwei Geräten, nämlich einem GPS-Satelliten und dem Empfänger, zu messen. Diese Messung wird durchgeführt, indem auf jedem Gerät eine Pseudozufallssequenz mit der gleichen Rate erzeugt wird, vorausgesetzt, sie wird synchronisiert. Die Sequenz des Satelliten wird dann moduliert und an den Empfänger gesendet, der sie mit seiner eigenen Sequenz vergleicht. Zwischen den beiden Ketten besteht ein Zeitunterschied, und dieser Unterschied entspricht der Laufzeit der Informationen zwischen dem Satelliten und dem Empfänger. Es genügt, diesen Unterschied zu messen und mit der Geschwindigkeit von . zu multiplizieren Elektromagnetische Wellen in der Luft, um die gewünschte Distanz zu erreichen.

Siehe auch

• RC4 Algorithmus zur kryptografischen Stream-Verschlüsselung

Verweise

• Barker, E. und Kelsey, J., Empfehlung für die Generierung von Zufallszahlen unter Verwendung von deterministischen Zufallsbitgeneratoren. Nationales Institut für Standards und Technologie (2007).
• Luby, M., Pseudozufälligkeit und kryptographische Anwendungen. Princeton University Press (1996).
• Niederreiter, H., Zufallszahlengenerierung und Quasi-Monte-Carlo-Methoden, SIAM (1992).
• Peterson, I., The Jungles of Randomness: A Mathematical Safari. Wiley, NY, S. 178 (1998).