Zufallszahl in PHP / C++

[johny7]

Moin allerseits,

mich interessiert, wie Zufallszahlen per Computer geliefert werden. Ich programmiere z.B. mit PHP und rufe die Funktion rand() auf. Mit dieser Funktion wird vermutlich letzten Endes die Zufalls-Funktion in C aufgerufen. Aber wie entsteht sie dort? In einer elektronischen Schaltung z.B. kann man per Tastendruck eine neue Zufallszahl so bekommen: Während des Tastendrucks wird mit extrem hoher Frequenz in einem festgelegten Bereich hochgezählt und immer wieder von vorne. Das geht so schnell, dass während des kurzen Tastendrucks (der ja nicht unendlich kurz ist) ein für den Drückenden stets unbekannter Wert anliegt, so dass nach Loslassen ein "zufälliger" Wert geliefert wird.
Wie sieht es in Programmen aus?

Grüße, JN

[LX]

Es gibt im PC keine echten, sondern nur Pseudozufallszahlen.

Gruß, LX

[Timo]

Hi,

Es gibt im PC keine echten, sondern nur Pseudozufallszahlen.

pseudo hin oder her, ich bin der Meinung man kann sehr wohl Zufallszahlen am PC erzeugen ohne dass diese irgend jemand vorausberechnen könnte, da ist dein Beispiel mit der Münze noch vorhersehbarer wenn sie sogar noch auf der Hand liegt, was als "echter Zufall" gilt.

Timo

[suit]

pseudo hin oder her, ich bin der Meinung man kann sehr wohl Zufallszahlen am PC erzeugen ohne dass diese irgend jemand vorausberechnen könnte, da ist dein Beispiel mit der Münze noch vorhersehbarer wenn sie sogar noch auf der Hand liegt, was als "echter Zufall" gilt.

Ein Münzwurf ist genauso wie ein Würfelwurf oder jeder andere Zufall dann pseudozufällig, wenn die zur Berechnung notwendigen Faktoren (Wurfhöhe, Geschwindigkeit, Rotationsgeschwindigkeit, Windrichtung, Windgeschwindigkeit, Luftfeuchtigkeit, Gravitation, Auffanghöhe, Handbewegung beim Auffangen ...) bekannt sind. Wenn die Münze in der Hand ist und nicht geworfen wurde, ist der nachfolgende Wurf zufällig und nicht vorhersehbar - wenn die Münze bereits geworfen wurde und sich in der Luft befindet, ist das Resultat Pseudozufällig (wenn auch quasi unmöglich zu berechnen).

Es ist ist _unmöglich_ auf einem Computer Zufallszahlen zu erzeugen (das ist die harte Wahrheit) - du kannst lediglich die Berechnung so verschleiern, dass es nicht mehr nachvollziehbar ist. Zufall ist nur dann möglich, wenn die Berechnung an die Ausführungszeit gebunden ist und diese zufällig erfolgt (z.B. durch den willkürlichen Scriptaufruf eines Benutzers). Der Computer selbst kann hingegen unmöglich zufällige Werte liefern.

[Ingo]

Hi,

Es ist ist _unmöglich_ auf einem Computer Zufallszahlen zu erzeugen (das ist die harte Wahrheit) - du kannst lediglich die Berechnung so verschleiern, dass es nicht mehr nachvollziehbar ist. Zufall ist nur dann möglich, wenn die Berechnung an die Ausführungszeit gebunden ist und diese zufällig erfolgt (z.B. durch den willkürlichen Scriptaufruf eines Benutzers). Der Computer selbst kann hingegen unmöglich zufällige Werte liefern.

Genau das war mein Ansatz, die Ausführungszeit. Da bieten sich viele Optionen an, angefangen mit dem Prozessor (als naheliegendsde), dessen Ausführungen im Nanobereich bei jeder gleichen Ausführung unterschiedlich ist. Die Nanoschwankungen könnte man doch in einer Rechnung potenzieren und somit in den Schleifenablauf einbringen, was als Folge eine "echte Zufallszahl" liefern "muss".

Äh, wo meldet man sich für einen Nobelpreis an? ;-)

Ingo

[suit]

Die Nanoschwankungen könnte man doch in einer Rechnung potenzieren und somit in den Schleifenablauf einbringen, was als Folge eine "echte Zufallszahl" liefern "muss".

Nein, es liefert immer noch Pseudozufallzahlen - du verschleierst nur einen Faktor der Berechnung und verwirfst ihn wieder.

Hier etwas Lesestoff dazu: http://random.mat.sbg.ac.at/generators/.

[LX]

Äh, wo meldet man sich für einen Nobelpreis an? ;-)

Der Nobelpreis wird jedes Jahr von der Stockholm Universitetet (direkt gegenüber des Kungliga Slottet in Stockholm, dessen großer Saal auch für das Bankett zur Übergabe genutzt wird) vergeben - und man meldet sich nicht selbst an (das wäre überheblich und unfein), sondern wird von Kollegen nominiert, die von den eigenen Erkenntnissen überzeugt, vielleicht sogar begeistert sind.

Was jedoch Deine Idee für Pseudozufallszahlen betrifft: Du kannst zur Berechnung normalverteilter (Pseudo-)Zufalls-Werte normalerweise nur Einflüsse nehmen, die direkt aus dem Computer kommen, da dieser keine äußeren Einflüsse erfaßt. Das impliziert jedoch direkt, dass auch ein Angreifer, sofern er auf dem gleichen System ist, die gleichen Messungen anstellen und damit auf das gleiche Ergebnis kommen kann wie Du.

Außerdem wird die Ausführungszeit von einzelnen Script-Blöcken von nachvollziehbaren Faktoren bestimmt (CPU-Last, Speichernutzung, etc.). Die Abweichungen sind üblicherweise nicht so groß, dass der Unterschied einen nutzbaren Zufall ergeben würde.

Gruß, LX

[Christian Seiler]

Hallo,

Es ist ist _unmöglich_ auf einem Computer Zufallszahlen zu erzeugen (das ist die harte Wahrheit)

Nein, das stimmt so nicht ganz. Bestimmte physikalische Phänomene sind tatsächlich quantenmechanischen Zufallsprozessen unterworfen und bieten somit eine Quelle echten Zufalls. Es gibt da eigentlich drei praktikable Möglichkeiten: Radioaktiver Zerfall, Polarisation von Photonen und elektronisches Rauschen. All diese Dinge kann man zur Erzeugung von Zufallszahlen erzeugen. Es gibt z.B. spezielle Crypto-Beschleunigerkarten für Server, die auf der Photonenpolarisation basieren (die Radioaktivitätsvariante hat sich aus psychologischen Gründen nicht verkauft). Und auf einigen Mainboards (auch im Consumer-Bereich!) wird von einem Chip elektronisches Rauschen ausgewertet, was aber nicht ganz so ideal ist, weil das Rauschen teilweise auch durch zumindest vom Prinzip vorhersehbare Prozesse beeinflusst wird und außerdem lange nicht so hohe Datenraten liefert.

Rein *algorithmisch* kann man natürlich sowas nicht erzeugen - man braucht immer eine Schnittstelle zu bestimmter Hardware dafür.

Was jedoch auch auf Rechnern ohne derartige Hardware gemacht werden kann, ist folgendes: Das Timing diverser Ereignisse (Netzwerkinput, Tastatureingaben, etc.) enthält zwangsweise Abweichungen, die einfach nicht vorhersehbar sind. Natürlich muss man da sehr vorsichtig sein, wie man das genau auswertet (weil da sehr viele nicht-zufällige Elemente dabei sind), aber das liefert durchaus Ergebnisse, die selbst für kryptographischen Einsatz brauchbar genug sind. Ist halt relativ langsam weil man gerade wegen der nicht-zufälligen Elemente nur wenig Informationen über einen langen Zeitraum extrahieren kann. Unter Linux macht das der Systemkern teilweise (man kann ihn durch ein Programm namens "Entropy Gathering Daemon" auch unterstützen) und stellt unter /dev/random Zufallszahlen zur Verfügung - wenn man daraus liest, erhält man Zahlen, die nach kryptographischen Standards zufällig genug sind. Es gibt auch /dev/urandom, was für die allermeisten Anwendungsfälle gut genug ist, wo aber ein mit /dev/random geseedeter Pseudozufallszahlalgorithmus dahinter steckt. Unter Windows gibt's irgend eine API-Funktion, um sich vom Systemkern Entropie zu besorgen.

Viele Grüße,
Christian

[suit]

Wie sieht es in Programmen aus?

Nachdem weder in Programmlogiken, noch in mechanischen oder elektronischen Schaltungen (mit binärer Logik) "echter Zufall" möglich ist, gibts nur die Möglichkeit von Pseudozufallszahlen.

Hauptsächlich werden Zufallszahlen aus irrationalen Zahlen ermittelt, aber auch Methoden wie z.B. der Mersenne Twister sind sehr verbreitet.

Wenn ich richtig informiert bin, verwendet PHP < Version 4.2 ein auf irrationalen Zahlen basierendes arithmetisches Verfahren mit einem Seed als Startpunkt.

[Bademeister]

Hi suit,

Hauptsächlich werden Zufallszahlen aus irrationalen Zahlen ermittelt

wie darf man sich das denn vorstellen? Irrationale Zahlen gehoeren, ebenso wie der "echte Zufall", auch nicht gerade zu den Staerken von Computern.
Oder?

danke, viele Gruesse
der Bademeister

[suit]

wie darf man sich das denn vorstellen? Irrationale Zahlen gehoeren, ebenso wie der "echte Zufall", auch nicht gerade zu den Staerken von Computern.

Irrationale Zahlen haben auch keine zufällige Abfolge von Ziffern, die Abfolge ist berechenbar. Die wohl bekannteste irrationale Zahl ist die Wurzel aus 2 (etwa 1,4142135623730950488016887242096980785697).

Eine sehr simple Art und Weise ist Stellen mittels Seed zählen - wenn du also mit einem Seed von sagen wir 15 beginnst um aus der Wurzel 2 eine Zufallszahl zu ermitteln, zählst du einfach die Stellen weiter - die 15. Stelle nach dem Komma ist "5". Die "Zufallszahl" ist also 5, der nächste Seed berechnet sich aus dem alten Seed udn der "Zufallszahl", z.B. Seed + Zufallszahl = neuer Seed. 20 Stellen weiter ist dann die Zahl "7" zu finden, der nächste Seed wäre 27 usw.

Das obrige Beispiel ist übrigens sehr vereinfacht :)

Genau aus dem Grund ist es essentiell wichtig, dass der Seed geheimgehalten wird, wenn die Zufallszahl zur Erzeugung von Private-Keys oder Passwörtern eingesetzt wird, ansonsten könnte man "problemlos" die Zufallszahl nachberechnen (da sie eben nur Pseudozufällig sind), wenn man den Algorithmus kennt. Darum wird bei solchen Systemen idR. auch empfohlen zur Seederzeugung z.B. den aktuellen Timestamp in Microsekunden heranzuziehen.

[Bademeister]

Hi suit,

Irrationale Zahlen haben auch keine zufällige Abfolge von Ziffern, die Abfolge ist berechenbar.

Na ja, bei "den meisten" irrationalen Zahlen ist sie das nicht.

Eine sehr simple Art und Weise ist Stellen mittels Seed zählen - wenn du also mit einem Seed von sagen wir 15 beginnst um aus der Wurzel 2 eine Zufallszahl zu ermitteln, zählst du einfach die Stellen weiter - die 15. Stelle nach dem Komma ist "5".

Die "Zufallszahl" ist also 5, der nächste Seed berechnet sich aus dem alten Seed udn der "Zufallszahl", z.B. Seed + Zufallszahl = neuer Seed. 20 Stellen weiter ist dann die Zahl "7" zu finden, der nächste Seed wäre 27 usw.

Ok. Es ist allerdings keineswegs klar, ob das eine Gleichverteilung auf der Menge der moeglichen Zufallszahlen liefert. Ausserdem braucht man noch einen zufaelligen Seed. Den zu erzeugen, ist doch das Wesentliche beim Erzeugen von Zufallszahlen. Wenn man mal eine Pseudozufallszahl hat (den Seed), waehlt man mit dem obigen im Grunde nur noch ihre Darstellung.

viele Gruesse
der Bademeister

[suit]

Na ja, bei "den meisten" irrationalen Zahlen ist sie das nicht.

Die Fequenz oder die Häufigkeit der Ziffern ist natürlich nicht berechenbar, die Zahlen selbst aber schon (bis zu einer bestimmten Stellenanzahl versteht sich).

Ok. Es ist allerdings keineswegs klar, ob das eine Gleichverteilung auf der Menge der moeglichen Zufallszahlen liefert.

Siehe oben. Darum müssen natürlich die Ergebnisse entsprechend getestet werden, dafür gibts z.B den Chi-Quadrat-Test.

Ausserdem braucht man noch einen zufaelligen Seed. Den zu erzeugen, ist doch das Wesentliche beim Erzeugen von Zufallszahlen. Wenn man mal eine Pseudozufallszahl hat (den Seed), waehlt man mit dem obigen im Grunde nur noch ihre Darstellung.

Und genau das ist der Knackpunkt an der Sache, da der Seed ebenfalls zufällig sein muss, bleibt eben die Frage offen, wie man einen zufälligen Seed erzeugt? Meist ist das eben die Sufgabe des aktuellen Zeitstempels oder einer bereits zuvor erzeugten Zufallszahl die im System hinterlegt ist (z.B. aus /dev/random).

[Bademeister]

Hi,

Die Fequenz oder die Häufigkeit der Ziffern ist natürlich nicht berechenbar, die Zahlen selbst aber schon (bis zu einer bestimmten Stellenanzahl versteht sich).

Nein, im allgemeinen stimmt das nicht. Abgesehen davon, dass "die meisten" irrationalen nicht mal endlich beschreibbar sind, also nicht mal als Input eines Algorithmus in Frage kommen, sind auch beschreibbare Zahlen nicht immer berechenbar. Etwa diese Zahl hier ist ein Beispiel, bei dem es genau umgekehrt ist, als Du es beschrieben hast: Sie ist nicht berechenbar (d.h. nicht beliebig approximierbar), die Verteilung der Ziffern ist aber sehr wohl bekannt.

Ist ganz interessant, schweift aber natuerlich vom Thema ab. Es gibt natuerlich "geeignete irrationale Zahlen", die sehr wohl berechenbar sind.

[...] bleibt eben die Frage offen, wie man einen zufälligen Seed erzeugt? Meist ist das eben die Sufgabe des aktuellen Zeitstempels oder einer bereits zuvor erzeugten Zufallszahl die im System hinterlegt ist (z.B. aus /dev/random).

Ich hab auch mal gehoert, dass es gaengig ist, einen Seed aus den vorherigen Mausbewegungen zu erzeugen. Allerdings weiss ich nicht, in welchen Zusammenhang das "gaengig" ist (?). Eine Standard-PHP- bzw. C-Funktion hat auf etwas derartiges natuerlich keinen Zugriff, daher ist dies im Zusammenhang dieses Threads wohl kaum zielfuehrend.

viele Gruesse
der Bademeister

[suit]

Nein, im allgemeinen stimmt das nicht. Abgesehen davon, dass "die meisten" irrationalen nicht mal endlich beschreibbar sind, also nicht mal als Input eines Algorithmus in Frage kommen, sind auch beschreibbare Zahlen nicht immer berechenbar. Etwa diese Zahl hier ist ein Beispiel, bei dem es genau umgekehrt ist, als Du es beschrieben hast: Sie ist nicht berechenbar (d.h. nicht beliebig approximierbar), die Verteilung der Ziffern ist aber sehr wohl bekannt.

Ist ganz interessant, schweift aber natuerlich vom Thema ab.

Vom Thema abschweifen ist hier doch üblich.

Es gibt natuerlich "geeignete irrationale Zahlen", die sehr wohl berechenbar sind.

Aus dem Grund werden wohl für solche Dinge irrationale Zahlen gewählt, die geeignet sind - eine reelle Zahl wie etwa 1/3 verwendet wahrscheinlich eh keiner.

Die Antwort auf Frage, welche Grundlage PHP oder C zur Berechnung mittels rand() herranzieht, würde mich aber immer noch interessieren.

[Sven Rautenberg]

Moin!

Darum wird bei solchen Systemen idR. auch empfohlen zur Seederzeugung z.B. den aktuellen Timestamp in Microsekunden heranzuziehen.

Nicht wirklich... http://www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/

- Sven Rautenberg

[suit]

Nicht wirklich... http://www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/

Interessant zu lesen, dass das nicht so schlau ist (obwohls an allen Ecken und Enden empfohlen wird), war mir nicht klar.

Das Beispiel "The Art of Cross Application Attacks" ist allerdings etwas überholt, zur Erzeugung von Zufallswerten nutzt Wordpress mittlerweile (seit Version 2.5) verschiedene Schlüssel (die allerdings Geheimgehalten werden müssen). Diese sind mit beliebiger Länge frei wählbar - aussehen sollten die Dinger etwa so: http://api.wordpress.org/secret-key/1.1/

Was mir in dem Artikel aber fehlt ist die Lösung für das angesprochene Problem - wie erzeugt man einen Seed für rand() oder mt_rand(), ohne dabei selbst den Seed zu kennen (um ihn nicht Geheimhalten zu müssen).

[miku]

Die CT hat mal einen Bericht gehabt indem Zufallszahlen erzeugt wurden anhand von zwei Lavalampen die mit Kameras abgefilmt wurden und anschließend die Formen verglichen oder sowas.

Der Artikel ist hier , allerdings muss man dafür zahlen, aber ich hab gedacht für die die das Magazin grad rumliegen haben ist es interessant, die können dann kurz nachschauen.