Ein Pseudozufallszahlengenerator (PRNG), auch bekannt als ein deterministischer zufälliger Bit-Generator (DRBG), sind ein Algorithmus, für eine Folge von Zahlen zu erzeugen, die den Eigenschaften von Zufallszahlen näher kommt. Die Folge ist darin nicht aufrichtig zufällig sie wird durch einen relativ kleinen Satz von Anfangswerten, genannt den Staat des PRNG völlig bestimmt, der einen aufrichtig zufälligen Samen einschließt. Obwohl Folgen, die am aufrichtig zufälligen näher sind, mit Hardware-Zufallszahlengeneratoren erzeugt werden können, sind Pseudozufallszahlen in der Praxis für ihre Geschwindigkeit bei der Zahl-Generation und ihre Reproduzierbarkeit wichtig, und sie sind so in Anwendungen wie Simulationen (z.B, physischer Systeme mit der Methode von Monte Carlo), in der Geheimschrift, und in der Verfahrensgeneration zentral. Gute statistische Eigenschaften sind eine Hauptvoraussetzung für die Produktion eines PRNG, und allgemeine Klassen von passenden Algorithmen schließen geradlinige congruential Generatoren ein, hat Generatoren von Fibonacci und geradlinige Feed-Back-Verschiebungsregister isoliert. Kryptografische Anwendungen verlangen, dass die Produktion auch unvorhersehbare und mehr wohl durchdachte Designs ist, die die Linearität von einfacheren Lösungen nicht erben, sind erforderlich. Neuere Beispiele von PRNGs mit starken Zufälligkeitsgarantien basieren auf rechenbetonten Härte-Annahmen, und schließen den Blum Blum Shub, Fortuna und die Algorithmen von Mersenne Twister ein.

Im Allgemeinen ist sorgfältige mathematische Analyse erforderlich, jedes Vertrauen zu haben, dass ein PRNG Zahlen erzeugt, die "genug zufällig" sind, um dem beabsichtigten Gebrauch anzupassen. John von Neumann hat über die Missdeutung eines PRNG als ein aufrichtig zufälliger Generator gewarnt und hat gescherzt, dass "Jeder, der arithmetische Methoden denkt, zufällige Ziffern zu erzeugen natürlich in einem Staat der Sünde ist." Robert R. Coveyou von Eiche-Kamm Nationales Laboratorium hat einmal einen Artikel betitelt, "Ist die Generation von Zufallszahlen zu wichtig, um verlassen zu werden, sich zu ereignen."

Periodizität

Ein PRNG kann von einem willkürlichen Startstaat mit einem Samen-Staat angefangen werden. Es wird immer dieselbe Folge, danach wenn initialisiert, mit diesem Staat erzeugen. Die Periode eines PRNG wird als das Maximum über alle Startstaaten der Länge des Präfixes ohne Wiederholungen der Folge definiert. Die Periode wird durch die Größe des Staates begrenzt, der in Bit gemessen ist. Jedoch, da sich die Länge der Periode potenziell mit jedem Bit des hinzugefügten 'Staates' verdoppelt, ist es leicht, PRNGs mit Perioden lange genug für viele praktische Anwendungen zu bauen.

Wenn ein innerer Staat eines PRNG n Bit enthält, kann seine Periode nicht mehr sein als 2 Ergebnisse und kann viel kürzer sein. Für einen PRNGs kann die Periode-Länge berechnet werden, ohne im Laufe der ganzen Periode spazieren zu gehen. Geradlinige Feed-Back-Verschiebungsregister (LFSRs) werden gewöhnlich gewählt, um Perioden genau 21 zu haben. Geradlinige congruential Generatoren haben Perioden, die durch das Factoring berechnet werden können. Mischungen (keine Beschränkungen) haben Perioden von ungefähr 2 durchschnittlich, gewöhnlich nach dem Wandern durch ein Nichtwiederholen Startfolge. Mischungen, die (Versetzungen) umkehrbar sind, haben Perioden von ungefähr 2 durchschnittlich, und die Periode wird immer den ursprünglichen inneren Staat einschließen (z.B. http://www.inference.phy.cam.ac.uk/mackay/itila/cycles.pdf). Obwohl PRNGs ihre Ergebnisse wiederholen wird, nachdem sie das Ende ihrer Periode erreichen, deutet ein wiederholtes Ergebnis nicht an, dass das Ende der Periode erreicht worden ist, da sein innerer Staat größer sein kann als seine Produktion; das ist mit PRNGs mit einer 1-Bit-Produktion besonders offensichtlich.

Die meisten pseudozufälligen Generator-Algorithmen erzeugen Folgen, die durch einigen von mehreren Tests gleichförmig verteilt werden. Es ist eine geöffnete Frage und ein zentraler zur Theorie und Praxis der Geheimschrift, ob es eine Weise gibt, die Produktion eines hochwertigen PRNG von aufrichtig Zufallsfolge zu unterscheiden, ohne den Algorithmus (En) verwendet und der Staat zu wissen, mit dem es initialisiert wurde. Die Sicherheit von den meisten kryptografischen Algorithmen und Protokollen mit PRNGs basiert in der Annahme, dass es unausführbar ist, Gebrauch eines passenden PRNG vom Gebrauch aufrichtig Zufallsfolge zu unterscheiden. Die einfachsten Beispiele dieser Abhängigkeit sind Strom-Ziffern, die (meistenteils) durch den exklusiven oder-ing der plaintext einer Nachricht mit der Produktion eines PRNG arbeiten, ciphertext erzeugend. Das Design kryptografisch entsprechenden PRNGs ist äußerst schwierig, weil sie zusätzlichen Kriterien (sieh unten) entsprechen müssen. Die Größe seiner Periode ist ein wichtiger Faktor in der kryptografischen Eignung eines PRNG, aber nicht der einzige.

Probleme mit deterministischen Generatoren

In der Praxis, die Produktion von vielen allgemeinen PRNGs stellen Kunsterzeugnisse aus, die sie veranlassen, statistischen Muster-Entdeckungstests zu fehlen. Diese schließen ein:

• Kürzer als erwartete Perioden für einige Samen-Staaten (können solche Samen-Staaten 'schwach' in diesem Zusammenhang genannt werden);
• Fehlen Sie von der Gleichförmigkeit des Vertriebs für große Beträge von erzeugten Zahlen;
• Korrelation von aufeinander folgenden Werten;
• Schlechter dimensionaler Vertrieb der Produktionsfolge;
• Die Entfernungen dazwischen, wo bestimmte Werte vorkommen, werden verschieden von denjenigen in einem Zufallsfolge-Vertrieb verteilt.

Durch fehlerhaften PRNGs ausgestellte Defekte erstrecken sich vom unerkennbaren (und unbekannt) zum sehr offensichtlichen. Ein Beispiel war der RANDU Zufallszahl-Algorithmus, der seit Jahrzehnten auf Großrechner-Computern verwendet ist. Es wurde ernstlich rissig gemacht, aber seine Unangemessenheit ist unentdeckt seit einer sehr langen Zeit gegangen. In vielen Feldern ist viel Forschungsarbeit dieser Periode, die sich auf die zufällige Auswahl oder auf Stil-Simulationen von Monte Carlo, oder auf andere Weisen verlassen hat, weniger zuverlässig, als es infolgedessen gewesen sein könnte.

Frühe Annäherungen

Ein früher computergestützter PRNG, der von John von Neumann 1946 angedeutet ist, ist als die Mittler-Quadratmethode bekannt. Der Algorithmus ist wie folgt: Nehmen Sie jede Zahl, Quadrat es, entfernen Sie die mittleren Ziffern der resultierenden Zahl als die "Zufallszahl", dann verwenden Sie diese Zahl als der Samen für die folgende Wiederholung. Zum Beispiel, Quadrieren, das die Nummer "1111" "1234321" nachgibt, der als "01234321", eine 8-stellige Zahl geschrieben werden kann, die das Quadrat einer 4-stelligen Zahl ist. Das gibt "2343" als die "zufällige" Zahl. Das Wiederholen dieses Verfahrens gibt "4896" als das folgende Ergebnis und so weiter. Von Neumann hat 10 Ziffer-Zahlen verwendet, aber der Prozess war dasselbe.

Ein Problem mit der "mittleren" Quadratmethode besteht darin, dass sich alle Folgen schließlich, einige sehr schnell, solcher als "0000" wiederholen. Von Neumann war davon bewusst, aber er hat die Annäherung genügend zu seinen Zwecken gefunden und wurde beunruhigt, dass mathematische "üble Lagen" einfach Fehler verbergen aber nicht sie entfernen würden.

Von Neumann hat unpassende Hardware-Zufallszahlengeneratoren beurteilt, weil, wenn sie die erzeugte Produktion nicht registriert haben, sie für Fehler nicht später geprüft werden konnten. Wenn sie wirklich ihre Produktion registrieren würden, würden sie die beschränkten Computererinnerungen verfügbar dann, und so die Fähigkeit des Computers erschöpfen, Zahlen zu lesen und zu schreiben. Wenn die Zahlen Karten geschrieben würden, würden sie sehr viel länger nehmen, um zu schreiben und zu lesen. Auf dem ENIAC Computer verwendete er, die "mittlere" Quadratmethode hat Zahlen an einer Rate ein Hundert Zeiten schneller erzeugt als das Lesen von Zahlen in von geschlagenen Karten.

Die Mittler-Quadratmethode ist durch mehr wohl durchdachte Generatoren seitdem verdrängt worden.

Mersenne Dreher

Die 1997-Erfindung des Mersenne Dreher-Algorithmus, durch Makoto Matsumoto und Takuji Nishimura, vermeidet viele der Probleme mit früheren Generatoren. Es hat die riesige Periode von 21 Wiederholungen (> 4.3), wird bewiesen, equidistributed in (bis zu) 623 Dimensionen (für 32-Bit-Werte) zu sein, und läuft schneller als andere statistisch angemessene Generatoren. Es wird jetzt der Zufallszahlengenerator der Wahl für statistische Simulationen und das generative Modellieren zunehmend.

SFMT, SIMD-orientierter Schneller Mersenne Dreher, eine Variante des Mersenne Drehers, ist schneller, selbst wenn er mit SIMD support.http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html nicht kompiliert wird

Der geborene Mersenne Dreher wird passend für den Gebrauch in allen kryptografischen Anwendungen nicht betrachtet. Eine Variante des Mersenne Drehers ist als eine kryptografische Ziffer vorgeschlagen worden. http://eprint.iacr.org/2005/165.pdf

Kryptografisch sichere Pseudozufallszahlengeneratoren

Ein PRNG passender für kryptografische Anwendungen wird kryptografisch sicher PRNG (CSPRNG) genannt. Eine Voraussetzung für einen CSPRNG ist, dass ein Gegner, der nicht den Samen weiß, nur unwesentlichen Vorteil im Unterscheiden der Produktionsfolge des Generators von einer Zufallsfolge hat. Mit anderen Worten, während ein PRNG nur erforderlich ist, bestimmte statistische Tests zu bestehen, muss ein CSPRNG alle statistischen Tests bestehen, die auf die polynomische Zeit mit der Größe des Samens eingeschränkt werden. Obwohl solches Eigentum nicht bewiesen werden kann, können starke Beweise durch das Reduzieren des CSPRNG auf ein Problem zur Verfügung gestellt werden, das, wie man annimmt, wie ganze Zahl factorization hart ist. Im Allgemeinen können Jahre der Rezension erforderlich sein, bevor ein Algorithmus als ein CSPRNG bescheinigt werden kann.

Einige Klassen von CSPRNGs schließen den folgenden ein:

• Strom-Ziffern
• Block-Ziffern, die im Schalter oder der Produktionsfeed-Back-Weise laufen.
• PRNGs, die spezifisch entworfen worden sind, um wie die Kryptografische Anwendung des Microsofts kryptografisch sicher zu sein, Schnittstelle-Funktion CryptGenRandom, der Schafgarbe-Algorithmus (vereinigt in Mac OS X und FreeBSD), und Fortuna Programmierend.
• Kombinations-PRNGs, die versuchen, mehrere PRNG primitive Algorithmen mit der Absicht zu verbinden, jede Nichtzufälligkeit zu entfernen.
• Sonderanfertigungen auf mathematischen Härte-Annahmen gestützt. Beispiele schließen Micali-Schnorr und den Algorithmus von Blum Blum Shub ein, die einen starken Sicherheitsbeweis zur Verfügung stellen. Solche Algorithmen sind im Vergleich zu traditionellen Aufbauten ziemlich langsam, und für viele Anwendungen unpraktisch.

BSI Einschätzungskriterien

Das deutsche Bundesamt für die Informationssicherheit (BSI) hat vier Kriterien für die Qualität von deterministischen Zufallszahlengeneratoren gegründet. Sie werden hier zusammengefasst:

• K1 — Eine Folge von Zufallszahlen mit einer niedrigen Wahrscheinlichkeit, identische Konsekutivelemente zu enthalten.
• K2 — Eine Folge von Zahlen, die von 'wahren zufälligen' Zahlen gemäß angegebenen statistischen Tests nicht zu unterscheidend ist. Die Tests sind der Monobit-Test (gleiche Anzahlen von und Nullen in der Folge), Schürstange-Test (ein spezielles Beispiel des chi-karierten Tests), führt Test durch (zählt die Frequenz von Läufen von verschiedenen Längen auf), longruns Test (Kontrollen ob dort besteht ein Lauf der Länge 34 oder größer in 20 000 Bit der Folge) — beide von BSI2 (AIS 20, v. 1, 1999) und FIPS (140-1, 1994), und der Autokorrelationstest. Hauptsächlich sind diese Voraussetzungen ein Test wie gut wenig Folge: Hat Nullen und ebenso häufig; nach einer Folge von n Nullen (oder), das folgende Bit ein (oder Null) mit der Wahrscheinlichkeit eine Hälfte; und jede ausgewählte Subfolge enthält keine Information über das folgende Element (E) in der Folge.
• K3 — Es sollte für jeden Angreifer (zu allen praktischen Zwecken) unmöglich sein, zu rechnen, oder, von jeder gegebenen Subfolge, irgendwelchen vorherigen oder zukünftigen Werten in der Folge, noch jedem inneren Staat des Generators sonst zu schätzen.
• K4 — Es sollte zu allen praktischen Zwecken zu einem Angreifer unmöglich sein, zu rechnen, oder von einem inneren Staat des Generators, irgendwelcher vorherigen Zahlen in der Folge oder irgendwelcher vorherigen inneren Generator-Staaten zu schätzen.

Für kryptografische Anwendungen sind nur Generatoren, die den K3 oder K4 Standard entsprechen, annehmbar.

Ungleichförmige Generatoren

Von einem ungleichförmigen Wahrscheinlichkeitsvertrieb ausgewählte Zahlen können mit einer Rechteckverteilung PRNG und eine Funktion erzeugt werden, die den zwei Vertrieb verbindet.

Erstens braucht man die kumulative Vertriebsfunktion des Zielvertriebs:

Bemerken Sie das. Mit einer Zufallszahl c von einer Rechteckverteilung als die Wahrscheinlichkeitsdichte, um "vorbeizugehen", bekommen wir

so dass

ist eine vom Vertrieb zufällig ausgewählte Zahl.

Zum Beispiel, das Gegenteil des kumulativen Vertriebs von Gaussian

mit einem idealen gleichförmigen PRNG mit der Reihe (0 1) weil würde Eingang eine Folge (positiv nur) Werte mit einem Vertrieb von Gaussian erzeugen; jedoch

• sie praktische Zahl-Darstellungen verwenden, müssen die unendlichen "Schwänze" des Vertriebs zu begrenzten Werten gestutzt sein.
• Wiederholende Wiederberechnung dessen sollte durch Mittel wie Zikkurat-Algorithmus für die schnellere Generation reduziert werden.

Ähnliche Rücksichten gelten für das Erzeugen anderen ungleichförmigen Vertriebs wie Rayleigh und Poisson.

Siehe auch

• Liste von Pseudozufallszahlengeneratoren
• Pseudozufällige binäre Folge
• Quasizufälliger
• Zufallszahlengenerator-Angriff
• Zufälligkeit

Referenzen

• Michael Luby, Pseudozufälligkeit und Kryptografische Anwendungen, Princeton Univ Presse, 1996. Eine endgültige Quelle von Techniken für nachweisbar Zufallsfolgen.
• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 2: Halbnumerische Algorithmen, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89684-2. Kapitel 3, Seiten 1-193. Umfassender Einschluss von statistischen Tests auf die Nichtzufälligkeit.
• R. Matthews Maximal Periodische Gegenstück-Meldung des Instituts für die Mathematik und seine Anwendungen 28 147-148 1992
• J. Viega, Praktische Zufallszahl-Generation in der Software, in Proc. 19. Jährliche Computersicherheitsanwendungskonferenz, Dez 2003.
• John von Neumann, "Verschiedene Techniken hat im Zusammenhang mit zufälligen Ziffern," in A.S. Householder, G.E. Forsythe, und H.H. Germond, Hrsg., Monte Carlo Method, Nationalem Büro von der Standardreihe der Angewandten Mathematik, 12 verwendet (Washington, D.C.: Amerikanische Regierungsdruckerei, 1951): 36-38.
• NIST Empfehlung für die Zufallszahl-Generation, die deterministische zufällige Bit-Generatoren verwendet

Links

• Kurzes Video auf Zufallszahlengeneratoren, die zufällige Samen und mittlere Quadratmethode erklären
• Das GNU Wissenschaftliche Bibliothek. Ein freier (GPL) C Bibliothek, die mehrere PRNG Algorithmen einschließt.
• Die Zufallszahlengenerator-Bibliothek von Tina. Ein freier (BSD Lizenz) Stand der Technik C ++ pseudozufällige Zahlengenerator-Bibliothek für folgende und parallele Simulationen von Monte Carlo.
• DieHarder: Ein freier (GPL) C Zufallszahl-Testgefolge.
• Forschungsrandomizer Ein freier Browser-basierter PRNG, der Javas "Math.random" Methode verwendet, Zahlen für die zufällige Anweisung und zufällige Stichprobenerhebung zu erzeugen.
• crng: Zufallszahlengeneratoren als Pythonschlange-Erweiterungstypen durchgeführter (RNGs) in C codiert.
• http://eeyore.wu-wien.ac.at/src/ prng: Eine Sammlung von Algorithmen, um Pseudozufallszahlen als eine Bibliothek von C-Funktionen zu erzeugen, die unter dem GPL veröffentlicht sind
• Fremder Attractors und TCP/IP Folge-Zahl-Analyse - eine Analyse der Kraft von PRNGs haben gepflegt, TCP/IP Folge-Zahlen durch verschiedene Betriebssysteme mit fremdem attractors zu schaffen. Das ist ein gutes praktisches Beispiel von Problemen in PRNGs und der in ihrer Durchführung möglichen Schwankung.
• Fremder Attractors und TCP/IP Folge-Zahl-Analyse - Ein Jahr Später - ein Anschlußartikel, der etwas von der Evolution von verschiedenen PRNG Algorithmen mit der Zeit demonstriert.
• Das Erzeugen von Zufallszahlen, die Zufallszahlen in Eingebetteten Systemen durch Eric Uner Erzeugen
• Analyse des Linux Zufallszahlengenerators durch Zvi Gutterman, Benny Pinkas und Tzachy Reinman
• Funktionalitätsklassen und Einschätzungsmethodik für deterministische Zufallszahlengeneratoren durch das Priv.-Dutzend von Dr Werner Schindler, Bundesamt für die Informationssicherheit