PHP Echte Zufallszahl

[hemorieder]

Hey,

ich suche eine wirklich sichere und gleichmäßig verteilte Möglichkeit eine einstellige (also 4, 58, usw) Zufallszahl zwischen 1 und 100 generieren zu lassen.

rand() bietet keine ausgewogene Verteilung, mt_rand() ist zwar besser, aber nicht wirklich zufriedenstellend.

Daher hoffe ich auf ein paar Profis hier im Forum, die mir gute Hinweise geben können.

Lg

 

[asdfman]

Aus sci.crypt.random-numbers:

> Given a source of uniform integer random numbers P in range [0,n-1], how
> >does one best (most economically) obtain one P' in range [0,m-1] (m<n)
> >(and without using real arithmetics)?

1 Calculate k = n mod m.

2 Generate a random P in the range [0, n-1]

3 if P >= (n - k) go to 2

4 return P' = P mod m

Dazu eine gute Quelle für die Zufallszahlen nehmen. /dev/random oder so.

 

[hemorieder]

irgendwie steig ich da nicht durch

 

[TchiboMann]

Nuja, "echte" Zufallszahlen gibt es in PHP leider (immer noch) nicht. Dir bleibt im Grunde nur rand oder mt_rand. Normalerweise reicht das aber auch für die allermeisten zwecke aus.

 

[petap]

"echte" Zufallszahlen kann ein Computer gar nicht erzeugen. Ein Computer ist nunmal ein deterministisches System...

 

[asdfman]

irgendwie steig ich da nicht durch

Das Verfahren gibt dir eine Möglichkeit, wenn du eine Quelle für gleichmäßig verteilte Zufallszahlen im
Bereich [0, n-1] hast, daraus Zahlen in einem kleineren Bereich (Bei dir wohl 0-99) zu holen.
Du brauchst dafür immer noch eine gute Quelle für Zufallszahlen, die PHP standardmäßig zwar nicht bietet,
du kannst aber auf /dev/random ausweichen, das relativ gute Werte liefert.

Das Verfahren übersetzt auf Deutsch:

1. Berechne k = n mod m
n ist hier die Größe des Intervalls der Zufallszahlenquelle. Beispielsweise 2^32.
m ist die Größe des Intervalls, das du haben willst. (Bei 0-99 also 100).

2. Erzeuge eine zufällige Zahl P im Intervall 0-n

3. Ist P >= (n - k) wiederhole schritt 2

4. Deine Zufallszahl P' ist nun P mod m.

Ein Beispiel für Doofe, in dem das mal durchgespielt wird:
Man will eine Zufallszahl im Bereich 0-99 haben und die Zufallszahlenquelle liefert Werte von 0 bis 2^32-1

1. k = n mod m = 2^32-1 mod 100 = 4294967295 mod 100 = 95
2. P ist eine zufällige Zahl zwischen 0 und n, beispielsweise 4294967229
3. n - k = 4294967295 - 95 = 4294967200. P ist größer also nochmal Punkt 2
2. P ist nun 126536
3. P ist kleiner als n - k also weiter
4. P' = P mod m = 126536 mod 100 = 36

Eine Beispielimplementierung in C habe ich im Repository eines meiner Projekte. Das sollte sich leicht nach PHP portieren lassen:
http://trac.incertum.net/boskop/browser/trunk/src/rrand.c

srrand() gibt man entweder einen int als seed, oder einen Zeiger auf eine Datei, die als Zufallsquelle dient.
Bekommt es beides, nimmt es die Datei. rrand(x) gibt dann einen Wert im Intervall 0-x aus.

Hoffe, ich habe das nun erschöpfend erklärt.

 

[TchiboMann]

Wozu wird die funktion eigentlich gebraucht? Weil, eine Zufallsfunktion die ein "regelmäßiges" Ergebnis hat ist eigentlich keine Zufallsfunktion...

 

[asdfman]

Es geht um eine gleichmäßige Verteilung. Also, dass jedes Ergebnis die selbe Wahrscheinlichkeit hat.
Nicht, dass regelmäßig die selben Werte herauskommen, oder so.

 

[TchiboMann]

Dieselbe Wahrscheinlichkeit schließt eine Zufälligkeit jedoch aus, ist also - rein von der Logik her - völlig Sinnbefreit^^

Eine solche Funktion jedenfall hat PHP verständlicherweise nicht, da kämste nicht um eine Flickschusterei herum... Du müsstest dir irgendwo abspeichern, welche Zahl wie Häufig bisher "zufällig" ausgewählt wurde... rein Statistisch müsste ein Zahlenbereich von 0-99 alle 100 Durchgänge wiederholt werden, die ziffer 53 würde beim ersten durchgang also 1x angezeigt werden und müsste dann aus dem "pool" rausgekillt werden.

Theoretisch könnteste ein Array mit den Werten 0-99 erstellen, bei dem nach jedem Durchgang eine zufällig ausgewählte Zahl aus dem Array gekillt wird, somit stünde dir beispielsweise von 0-99 nur noch 99 Werte zur Auswahl.

Dieses Array könnteste serialisiert in einer Text-Datei oder in einer Datenbank speichern und vor jeder Zufallszahl-Auswahl neu laden. Wenn dann von 0-99 Werten nur noch einer übrig ist und dieser ausgewählt wurde, generierst du dir wieder ein array mit 0-99 Werten - und das Spiel beginnt von vorn.

Das würde jedenfalls dazu führen, das jede Zahl nach exakt 100 Zufallszahlwahlen genau N mal angezeigt wurde...

Der Nachteil ist einfach, dass man über kurz oder lang relativ exakt voraussagen kann, welche Zahl als nächstes erscheint.

 

[asdfman]

Dieselbe Wahrscheinlichkeit schließt eine Zufälligkeit jedoch aus, ist also - rein von der Logik her - völlig Sinnbefreit^^

Blödsinn. Ein Münzwurf ist auch zufällig. Trotzdem hat jede der beiden Seiten die selbe Wahrscheinlichkeit von 50% oben zu landen.

Würde man es dagegen so machen, wie du sagst, könnte man, wenn man die vorherigen Ergebnisse kennt, immer besser vorhersagen,
welcher Wert als nächstes käme. Und auch vorhersagen, welche Werte garantiert nicht mehr auftauchen werden. Eine Zufälligkeit wäre
also nicht mehr gegeben. Nach 99 verschiedenen "zufälligen" Zahlen, wäre es sogar absolut sicher, welche als nächstes kommt.

€dit:

Der Nachteil ist einfach, dass man über kurz oder lang relativ exakt voraussagen kann, welche Zahl als nächstes erscheint.

Ach hast ja sogar selbst gemerkt, dass das Quatsch ist, was du da gepostet hast. Wundert mich, dass du den Kram dann aber trotzdem
noch stehen gelassen hast. Wenn man voraussagen kann, welche Zahl als nächstes kommt, ist sie nämlich nicht mehr zufällig, sondern
eben deterministisch. Verstehste?

€2: Deine Ausführungen erinnern mich ein wenig an das hier...

 

[[funcoder]]

Was ich immer gern verwende ist neben der Random Funktion zusätzlich die UnixTime mit zu verwenden. Erhält man in PHP eh mit Time.

Dann am besten ein Schema überlegen wie man zur php generierten Zufallszahl noch die UnixTime dazurechnet etc...

Beispiel:
Wenn UnixTime ist ungerade Zahl Dann vorletze Zahl der UnixTime zur PHP generierten Zahl dazurechnen.

Das ganze lässtg sich natürlich endlos weiterführen. und ist jediglich ein Denkanstoss.

 

[asdfman]

Na der Timestamp ist aber immer bekannt. Also sorgt das nicht für zusätzliche Schwierigkeiten, die
Zahl vorherzusagen. Sorgt nur für zusätzlichen Rechenaufwand und macht die Software langsamer.

 

[[funcoder]]

Sicher ist der Timestamp bekannt. Aber das Schema mit dem die von PHP generierte Zufallszahl durch dein eigenes Schema verändert wird nicht. Bzw. ist diese Methode sicherlich schon einiges sicherer als die Standard Zufallszahl.


Um das ganze noch sicherer zu machen könnte man beispielsweise noch den timestamp mit 1,5 multiplizieren und dann 100 abziehen davon die Quadratwurzel berechnen und dann das Schema anwenden.

 

[asdfman]

Die ganzen Operationen, die du genannt hast, sind konstant und fügen dem Timestamp keine weitere Entropie
hinzu. Außerdem ist vor Allem die Berechnung der Quadratwurzel besondern Rechenintensiv und verlangsamt
das Programm unnötig.

/dev/random unter Linux ist eine anerkanntermaßen sehr gute Quelle für Zufallszahlen. Versuche, da selbst was
zu erfinden, ohne dass man da besonderes Wissen hat (zB. in dem man sich intensiv mit Tests für Zufallszahlen
beschäftigt hat), führen einen meist nicht weiter.

Eine konstante Operation am Timestamp ist jedenfalls auch ohne vorher das genaue Verfahren zu kennen, sehr
leicht herauszubekommen und ganz klar deterministisch. Also keine zusätzliche Quelle für Zufälligkeit.

€: Ich will hier nicht behaupten, besonderes Wissen darüber zu haben, wie man einen Zufallsgenerator am besten
zu entwerfen hat. Ich habe kein Mathematikstudium oder so hinter mir, in dem solche statistischen Methoden halt
dazu gehören.

Aber ein bisschen logisches Überlegen macht finde ich schon klar, dass deine Idee nichts bringt. Und genauso, wie
es in der Regel zum Scheitern verurteilt ist, sich selbst eine Verschlüsselungsmethode auszudenken, ohne dass man
sich intensiv mit der Materie beschäftigt hat, liegt die Sache bei Zufallsgeneratoren. Es gibt genug Leute, die wirklich
Ahnung davon haben. Die haben Dinge entwickelt, wie /dev/random oder andere Verfahren, wie Yarrow z.B.

Ich finde, auf diese Leute sollte man sich eher verlassen, als da selbst was zusammenzuschustern.

Eine kleine Bemerkung noch: Das Verfahren, das ich oben genannt habe, ist kein selbst ausgedachtes Verfahren zur
Erzeugung von Zufallszahlen, sondern nur eine Methode, wenn man bereits eine Quelle für Zufallszahlen hat, diese
in ein anderes Intervall zu transformieren und dabei eine gleichmäßige Verteilung der Zahlen zu erhalten. Ich habe
mir keinen eigenen Zufallszahlengenerator ausgedacht. Das würde ich mir auch definitiv nicht zutrauen.

€: Zum Thema "Nimm doch einfach den Timestamp als Quelle für Zufallszahlen", hier ein Link, der beschreibt, dass das
keine gute Idee ist:

http://www.heise.de/security/meldung/PHP-stuempert-bei-Zufallszahlen-967062.html

 

[[funcoder]]

/dev/random unter Linux ist eine anerkanntermaßen sehr gute Quelle für Zufallszahlen

Das ist sicherlich richtig nur unter PHP wird man darauf schlecht zugreifen können.

Berechnung der Quadratwurzel besondern Rechenintensiv

Naja die Operation auf aktuellen Server CPUs beansprucht geschätze 0,00 irgendwas Nanosekunden. Das ist sicherlich schon mal kein Argument wenn es um Sicherheit geht.

Letzendlich sollte das ganze auch nur als Idee/Vorschlag/Denkanstos gelten. Das mein Vorschlag nicht perfekt ist war mir klar. Ende

 

[asdfman]

Hey, sieh das nicht als Angriff gegen dich. Ich habs nur gut gemeint.
Und wegen PHP: Ich kenne die Sprache jetzt nicht richtig, aber man wird doch eine Datei öffnen können, um daraus Daten zu lesen. Mehr muss man ja bei /dev/random nicht tun.
Wenn das wirklich nicht geht, würde ich als Quelle für Zufallszahlen zum Beispiel oben genannten Yarrow-Algorithmus empfehlen. Der ist von Experten entwickelt worden und man
kann darauf vertrauen, dass er für seinen Zweck gut geeignet ist.

 

[ice-breaker]

klar geht es asdfman

mt_rand() von PHP ist der Mersenne Twister, dessen Periode sehr hoch ist, also wenn die Zufallszahlen dir nicht genügen, kannst du nur noch mit echten Zufallszahlen arbeiten, da gibts PCI-Karten ab mehreren tausend Euro, viel Spaß dabei.

 

[TchiboMann]

Auhmann asdfman... ICH laber wenigstens nich oberschlaumeierhaft herum sondern liefere LÖSUNGSWEGE, die auch NACHVOLLZIEHBAR sind - und bewirken, dass ein bestimmter Zahlenraum zuverlässig verteilt durchgelaufen werden kann. Es ist mit PHP eben NICHT ohne Weiteres möglich gleichmäßig verteilte Zufallszahlen aus einem bestimmeten Zahlenraum zu generieren, und es ist auch NICHT möglich mit PHP mal eben einfach so auf /dev/random zurückzugreifen, denn du vergisst, dass diese Möglichkeit zugleich auch ein Sicherheitsrisiko wär (wer auf dev/random zugreifen kann, kann auch auf andre Systemdateien zugreifen) - und schon gar nicht auf jedem xbeliebigen, gut konfiguriertem Webspace möglich sein darf.

Außerdem gehts explizit um gleichmäßig verteilte Zufallszahlen aus einem sehr kleinen Zahlenbereich - ergo ist die Erratbarkeit wohl recht irrelevant, denn wer einen solch kleinen Zahlenraum wählt, muss mit einer Wahrscheinlichkeit von 1:100 damit rechnen, dass jemand die nächste Zahl korrekt errät. Und da jede Zahl mit der gleichen Wahrscheinlichkeit angezeigt werden soll, brauchste vielleicht 100 Durchgänge beobachten und kannst irgendwann die exakte Zahl vorraussagen (oder vorausberechnen). Wo Wahrscheinlichkeiten ins Spiel kommen, gibt es einfach keinen echten Zufall mehr. Was meinste bitte, wie extremst unsicher dann Sessions wären - bzw. fast schon sind (siehe Heise-Artikel).

Ah, und dein Münzenbeispiel stinkt ein wenig, die Chance steht 1:3 und nicht 1:2 - du darfst nicht vergessen, dass die Münze theoretisch auch auf dem Rand stehen bleiben könnte. Und die Wahrscheinlichkeit, dass du richtig "rätst", ist verflucht hoch bei dem Beispiel, weil du nur 3 Möglichkeiten hast, wovon eine unwahrscheinlich (aber nicht unmöglich!) ist. Du hast damit eine extremst hohe Wahrscheinlichkeit, dass du richtig rätst - wie immer, wenn eine Wahrscheinlichkeit und/oder nur leicht veränderliche Daten genutzt werden.

 

[ice-breaker]

Und da jede Zahl mit der gleichen Wahrscheinlichkeit angezeigt werden soll, brauchste vielleicht 100 Durchgänge beobachten und kannst irgendwann die exakte Zahl vorraussagen (oder vorausberechnen).

damit setzt du aber eine extrem kleine Periodenlänge voraus, was total unrealistisch ist.

 

[TchiboMann]

War auch nur beispielhaft, jedenfalls isses möglich über eine feste Wahrscheinlichkeit und einen begrenzten Raum etwas vorherzusagen. Wenn die Wahrscheinlichkeit wegfällt, fällt auch die Vorhersage weg. Dann kannste nur noch raten und Glück haben.