PocketMagic

Einleitung

Sehr häufig müssen wir Zufallszahlen zu verschiedenen Zwecken im Intervall von einfachen Spielen zu Fortschritt-Verschlüsselungsalgorithmen erzeugen.
Viele C/C ++ Programmierer werden mit dem srand () / rand gut verwendet () Funktionen, aber einfach das Verwenden eines vorherbestimmten Codes, um die gegebenen Aufgaben zu erreichen, sind manchmal nicht genug.
Völlig hilft das Verstehen, wie eine Zufallszahl ist, wie es erzeugt werden kann, dem Bekommen der besten Lösung.

Mit meinen ersten Universitätsjahren anfangend, verwendete ich einen geradlinigen pseudozufälligen Generator, leicht, und ziemlich nützlich in vielen Anwendungen durchzuführen.
Ein Pseudozufallszahlengenerator (PRNG) ist ein Algorithmus, um eine Folge von Zahlen zu erzeugen, die den Eigenschaften von Zufallszahlen näher kommt. Die Folge ist darin nicht aufrichtig zufällig sie ist durch einen relativ kleinen Satz von Anfangswerten, genannt den Staat des PRNG völlig entschlossen. Lesen Sie mehr hier. Read more here.

Eine einfache Annäherung

Wollen wir a, b und c drei unveränderliche ganze Zahl denken. Wir planen, eine Reihe von Pseudozufallszahlen X0, X1..., Xn zu erzeugen. X0 = d annehmend, kann der Rest der Zahlen in einem wiederkehrenden Verwenden der Formel geschätzt werden: Assuming X0 = d, the rest of the numbers can be computed in a recurrent using the formula:
Xn+1 = (a*Xn + b) % c.

a, b, c und d sind die Anfangswerte, auch bekannt als der Staat des PRNG.

c beschränkt die resultierenden Werte auf den Zwischenraum 0.. c-1
a und b betreffen den geradlinigen Winkel.

Hier ist ein einfacher C Algorithmus, um die Formel besser zu illustrieren:

#include

wichtiger int ()
{
int a=71, b=19, c=256, d = 3;

int x [200], ich = 0;
x [0] = d;
für (i=1; ich<200;i++)
x [ich] = (a*x [i-1] + b) % c;

printf ("Die Pseudozufallszahlen are:\n");
für (i=0; ich<200;i++)
printf ("%d", x [ich]);

kehren Sie 1 zurück;
}

Sie können das Ergebnis im folgenden Image sehen:

Quellcode here:pnrg1.

Dem srand () und rand () zu ähneln, fungiert Sie werden alle dazu verwendet, ich muss das hervorheben sie verwenden auch einen PRNG. srand () "entsamt" den zufälligen Generator und praktisch alles, was tut, soll die Anfangswerte (der Staat von PRNG) setzen.
Sie können den Generator oben leicht anpassen, um wie srand () und rand () zu arbeiten:

#include

int = 71, b = 19, d = 0;

Leere mysrand (int Samen)
{
d = Samen;
}

int myrand (int Schwelle)
{
int x = d;
x = (a*x + b) %-Schwelle;
d = x;//gehen mit jedem Funktionsanruf vorwärts // advance with each function call
geben Sie x zurück;
}

leere Hauptsache ()
{
mysrand (122);
printf ("Pseudozufallszahl: %d\n", myrand (256));
printf ("Pseudozufallszahl: %d\n", myrand (256));

}

Ergebnis, wie geschildert, unten:

Der Quellcode hier: pnrg2

Sie werden schnell bemerken, dass der PRNG dieselbe Produktion jedes Mal erzeugt, wenn Sie den mysrand mit demselben Wert initialisieren:
mysrand (122)-> myrand (256) =233
Aber das ist dasselbe im Fall vom gebauten in srand () und rand () Funktion auch. Der Grund besteht darin, dass wir eine gute Quelle für die Verwirrung nicht haben. Sie können das überwinden, indem Sie verwenden: You can overcome this by using:
mysrand (GetTickCount ());
oder
mysrand (Cursorpos.x)
oder
mysrand (FreeRAMMemory ())
oder
mysrand (UserLastKeyPressed)
oder usw., die Initialisierungsfunktion mit einem zufälligen Ereignis verbindend.

Weitere Analyse

Über das Verwirrungsniveau dieses Generators sprechend, gibt es eine einfache Weise, eine Folge von Zahlen, in unserem Fall der X0..., Xn serie outputed durch den geradlinigen PRNG zu analysieren.
1. In einem einzelnen dimensionierten Raum, der durch die Achse der reellen Zahl und den entsprechenden Satz aller reellen Zahlen (R) vertreten ist, kann eine gegebene Zahl als eine einzelne Person entsprechend einem Punkt auf der Achse angesehen werden.
Für eg., sieh das folgende Bild:

Es vertritt einige reelle Zahlen auf der Achse. Man könnte fragen, was die Bedeutung der Zahl-1.13 ist. Die einfache Antwort ist:-1.13 ist die Entität, die auf der Achse an der gegebenen Position sitzt. Mehrere Eigenschaften können extrapoliert werden, und wir bekommen eine Bedeutung dessen, was-1.13, und am wichtigsten ist: Was wir kann, damit tun. The simple answer is: -1.13 is the entity that sits on the axis at the given position. Several properties can be extrapolated, and we get a meaning of what -1.13 is, and most important: what can we do with it.
2. Für ein gegebenes Paar von Zahlen können wir einen bidimensional Raum darstellen, wo das Paar einen Punkt in einem Kartesianischen System der Verweisung vertritt. Das Paar erhält eine Bedeutung, und wir können weiter das ausführlich behandeln, das Paar zu verschiedenen Zwecken verwendend. The pair receives a meaning, and we can further elaborate on that, using the pair for various purposes.

Auf eine ähnliche Weise, für einen gegebenen Satz von Zahlen (x0, x1..., xn), die zufällig und sinnlos zuerst scheinen, wollen wir nicht vergessen, dass in einem n-dimensional Raum der Satz von Zahlen eine sehr einfache und klare Bedeutung hat: Es vertritt einen Punkt.

Glücklicherweise für den PRNG'S sind die Dinge einfacher.
In Anbetracht einer Reihe von mit dem geradlinigen PRNG erzeugten Zahlen können sie ohne jede Bedeutung in einer Dimension vertreten werden: Sie würden "zufällige" Punkte auf der Zahl-Achse sein.
ABER wir können nach einem "Pfad" oder einer "Bedeutung" suchen, indem wir uns zu einem höheren Raum in diesem Fall zu zwei Dimensionen bewegen, und die durch den Punkt von Koordinaten gesetzten Pseudozahlen (Xn-1, Xn) vertreten.

Sieh die folgende Probe:
1-Die erste PRNG Probe habe ich angeschlagen, die folgenden Zahlen erzeugt:
3 83 24 72 11 32243120 91 80 67168.... usw.
Es ist sehr hart zu verstehen, was diese Zahlen bedeuten oder einen Zweck dieser Folge zu geben oder sogar das Muster zu verstehen, das diente, um sie zu erzeugen.

2-wollen Wir ein einfaches Programm schreiben, um in zwei Dimensionspaaren von Zahlen (Xn, Xn+1) als Punkte in einem Kartesianischen System grafisch zu illustrieren.

Die Punkte im Bild sind nichts anderes dann die 200 Pseudozufallszahlen (3 83 24 72 11 32243120 91 80 67168
171 8 75224 51 56155 16 6
4211152 59112 545700355 40 43 0 19
88123 48 99136203 96179184 27144 3 83 24187
240163 72 11 32243120 91 80 67
227 8 75224 51 56155 16 64211152 59112 35200
814135811 40 43 0 19 88123 48 99136203 9
6179184 27144 3 83 24 72 11 32243
120 91 80 67 8 75224 51 56155
16 64211152 59112 35 200 139 20
8195 40 43 0 19 88123 48 99136203 96179184 27144 3232
107192 83 24187240)

Interessanterweise, was zuerst Gesamtverwirrung schien, jetzt erinnert die richtige Ordnung eines Obstgartens mit Bäumen, die richtig in Reihen und Säulen an einem gegebenen Winkel in unserem durch die schwarzen Punkte vertretenen Image gepflanzt sind.
Bekommen Sie den Quellcode hier: pnrg3gui

Wenn Betrachtung der Folge in zwei Dimensionen nichts Nützliches zeigt, können wir uns weiter bewegen und die Darstellung in drei Dimensionen, Punkten von Koordinaten (Xn-1, Xn, Xn+1) und so weiter überprüfen.

Wie gezeigt, oben, an einem gegebenem Niveau, wird der "zufällige" Inhalt eine Bedeutung bekommen.

Hoffen Sie, dass das hilft,
Radu

Durch Radu Motisan

Am 17. Januar 2010 | Anhängsel: Großtat, Zahlen, zufällig | Kategorie: Forschung, Sicherheit, Software | Druck Dieser Posten | schicken Diesen Posten per E-Mail | Unterschreiben Anmerkungen | Erlaubnis eine Anmerkung | Trackback URL-ADRESSE Tags: exploit, numbers, random | Category: Research, Security, Software | Print This Post | Email This Post | Subscribe to comments | Leave a comment | Trackback URL  Print This Post | Email This Post | Subscribe to comments | Leave a comment | Trackback URL  Email This Post | Subscribe to comments | Leave a comment | Trackback URL