Zufallsgenerator : Zahl vielen generieren

shrax

Stammuser
Hi,
ich möchte selber einen Zufallsgenerator in JavaScript programmieren.
Hierzu möchte ich den Algorithmus der hier beschrieben ist
Der Algorithmus funktioniert folgendermaßen1 :

Man beginne mit einer Zahl zwischen 0 und 1.
Man addiere zu dieser Zahl die Kreiszahl p (etwa 3,14159265...).
Das Ergebnis potenziere man mit 8 (umgangssprachlich: Das Ergebnis »hoch 8« nehmen).
Der Nachkommaanteil des Ergebnisses ist die nächste Zufallszahl.
Mit dem Nachkommateil starte man den Algorithmus erneut, um eine weitere Zufallszahl zu erhalten.
Quelle: Galileo Computing :: JavaScript und AJAX – 6 Zufall

nutzen.

Dazu brauche ich ja eine Zahl zwischen 0 und 1. Im Buch wird dies mit der aktuellen Zeit realisiert. Ich möchte - rein zur übung - versuchen wie z. B. bei TrueCrypt eine Zufallszahl per Mausbewegung zu erzeugen.

Hierzu würde ich per JavaScript einfach die Mausbewegungen abfangen und die koordinaten in irgendeiner form speichern.

Dann habe ich z.B.
x=3 y=7
x=102 y=1234
x=1212 y=1232
x=36434 y=123
Edit: Da ich keinen Bildschrim mit einer Auflösung von 36434 habe, sollte diese Zahl natürlich etwas kleiner sein ;)
x=323 y=193
als koordinaten abgefangen.

Wie könnte ich nun am besten aus den hier per Mausbewegung erstellten Werten eine Zahl zwischen 0 und 1 generieren, die ich als Startwert für das obige Beispiel nutzen könnte?
 
Zuletzt bearbeitet:

SchwarzeBeere

Moderator
Mitarbeiter
Für was steht dann xMAX und xMIN? Für die momentane höchste Koordinate ( obwohl danach noch mehr Koordinaten kommen), oder soll ich alle Koordinaten Speichern und am Schluss die höchste nehmen, oder ist damit die höchste mögliche der derzeitigen Auflösung gemeint?
Sorry, ich habe nochmal nachgedacht und den Beitrag verändert, deswegen ist das vorherige Bild nicht mehr aktuell.

x_max und x_min stehen für die Max und Min-Koordinaten des Bildschirms, d.h. rechts unten und links oben (vermutlich 0 oder 1).
 

Elderan

Moderator
Der Zufallsgenerator sieht doch ziehmlich eigenartig aus. Da gibt es andere deutlich schönere und wahrscheinlich auch sichere Verfahren.

Aber davon mal abgesehen:
Was du suchst ist eine Funktion f die eine Menge an (x,y)-Koordinaten auf das Intervall [0,1] möglichst gleichmäßig verteilt, wobei kleine Änderungen in der Eingabe den Ausgabewert stark verändern sollen.

Dort kommt einem schnell eine Hashfunktion in den Sinn, beispielsweise einfach:
sha1(3,7,102,1234,1212,1232,323,123)

Diesen Wert mappt man dann auf das Intervall [0,1]. Mathematisch würde man den Wert durch 2^160 teilen.

Oder, sofern in JavaScript möglich, nimmt man die ersten 53 Bit des Ergebnis und formt daraus direkt eine double-Zahl.


Edit:
@SchwarzeBeere:
Dein Verfahren ist leider denklich schlecht geeignet um einen Zufallsgenerator anhand der Mausbewegung sicher zu initialisieren.

Du berechnest ja den Mittelwert der gemessenen Koordinaten und normierst diesen auf den Bereich [0,1]. Das ist nicht zu empfehlen, weil:
1. Eine minimale Abänderung in der Messung der Koordinaten (z.B. bei der zweiten Messung weicht nur ein Wert um den Wert 1 ab) führt zu kaum einer Veränderung im Ergebnis. Bei einem sicheren Mapping auf [0,1] sollte das Ergebnis aber ein komplett unterschiedliches sein, selbest wenn nur 1 Wert von 1 Millionen Messungen abweicht.

2. Das Verfahren bildet keine Gleichverteilung auf das Intervall [0,1] ab. Werte um 0,5 werden mit einer erheblich höheren Wahrscheinlichkeit angenommen als Werte die dicht bei 0 oder bei 1 liegen.

3. Je länger die Maus (echt zufällig) bewegt wird, um so wahrscheinlicher wird der berechnete Wert dem Mittelpunkt der Auflösung entsprechen. Das bedeutet wenn die Leute besonders sichern gehen und lange die Maus wild bewegen, wird es für den Angreifer immer leichter die Initialisierung zu berechnen.
 
Zuletzt bearbeitet:

shrax

Stammuser
Hallo Elderan,

Der Zufallsgenerator sieht doch ziehmlich eigenartig aus. Da gibt es andere deutlich schönere und wahrscheinlich auch sichere Verfahren.
Könntest du mir hier ein Schlagwort nennen?


Diesen Wert mappt man dann auf das Intervall [0,1]. Mathematisch würde man den Wert durch 2^160 teilen.

Oder, sofern in JavaScript möglich, nimmt man die ersten 53 Bit des Ergebnis und formt daraus direkt eine double-Zahl.
Könntest du mir diese beiden Sätze noch etwas genauer erläutern?
"mappt" soll in dem Fall also Wert / 2^160 heißen oder
die ersten 53 Bit nehmen und daraus eine double-Zahl formen?

Warum
man den Wert durch 2^160 teilen.
? Hat das was mit der länge des Hashs zu tun? Müsste der Hash, der ja nicht nur aus zahlen besteht, erst in ein Zahlensystem umgerechnet werden?
nimmt man die ersten 53 Bit des Ergebnis
Warum die ersten 53 Bit?
 

SchwarzeBeere

Moderator
Mitarbeiter
Du berechnest ja den Mittelwert der gemessenen Koordinaten und normierst diesen auf den Bereich [0,1].
Richtig. In der Version, die shrax zitiert hat, hätte ich dann eher eine Normalverteilung erreicht, als eine Gleichverteilung. Ist es in der neuen Version, die ich danach aber noch gepostet habe, immernoch so? Den einzigen Nachteile sehe ich aktuell in der geringen Anzahl an Elementen in der Zielmenge, z.B. bei 100 Messungen und 1080p nur 108000 mögliche Werte für x.
 

Elderan

Moderator
Hallo Elderan,

Könntest du mir hier ein Schlagwort nennen?
In dem Paper von SchwarzeBeere sind doch einige verlinkt. Ansonsten sind hier auch noch ein paar Algorithmen genannt:
Cryptographically secure pseudorandom number generator - Wikipedia, the free encyclopedia

Oder für JavaScript speziell:
https://www.clipperz.com/security_privacy/crypto_algorithms/#prng

Könntest du mir diese beiden Sätze noch etwas genauer erläutern?
"mappt" soll in dem Fall also Wert / 2^160 heißen oder
die ersten 53 Bit nehmen und daraus eine double-Zahl formen?
Durch sha1(seed) erhälst du einen 160 Bit Output. Da du den Algorithmus ja mit einer Zahl zwischen 0 und 1 initialisieren musst, musst du diese 160 Bit irgendwie umrechnen auf eine Zahl zwischen 0 und 1.

Dazu hast du verschiedene Möglichkeiten:
Mathematische Methode: Die Zahl als Integer betrachten und dann durch 2^160 teilen.

Direkter Weg: Ein Gleitkommazahl vom Typ Double benutzt nur 53 Bit, d.h. alles darüber wird abgeschnitten. Sofern man Gleitkommazahlen in JavaScript direkt aus Bit-Inputs generieren kann, wäre dies die bevorzugte Methode.



Richtig. In der Version, die shrax zitiert hat, hätte ich dann eher eine Normalverteilung erreicht, als eine Gleichverteilung. Ist es in der neuen Version, die ich danach aber noch gepostet habe, immernoch so? Den einzigen Nachteile sehe ich aktuell in der geringen Anzahl an Elementen in der Zielmenge, z.B. bei 100 Messungen und 1080p nur 108000 mögliche Werte für x.
Ich habe nur die neue Methode betrachtet.

Angenommen man betrachtet die Messung nun nicht auf der Skala z.B. 1 bis 1024 sondern auf der Skala 0 bis 1 (Transformation ist verlustfrei möglich). Dann ist x_min = 0, x_max = 1.
Damit ist dann x_norm = x' / n = x_mean.

Bei y ebenso.

Du berechnest also weiterhin den Mittelwert der x und den Mittelwert der y Koordinate und mittelst dann diese beiden Werte. Wie erwähnt, eine kleine Änderung an einem x wird so gut wie keine Auswirkung haben.
 

shrax

Stammuser
Die Zahl als Integer betrachten und dann durch 2^160 teilen.
Was bedeutet betrachten?

Also d. h. sha1([...]Alle koordinaten)
= 3c19f85f1124c019a1fce71db758a811d826ebbb

Und dann? Den hash als Hex-Zahlen nehmen und in Dezimal umrechnen?
-> 548167072439062700000 / (2^160) Rechnen?


Oder den hash erst in Binär umrechnen? Bitte entschuldige wenn ich mich im moment hier etwas dumm anstelle.

Ansonsten: Wie wäre es vor die umgerechnete Dezimalzahl einfach eine 0. zu hängen?
 

Elderan

Moderator
Hallo,
naja sha1 gibt dir ein 20-Byte Array zurück. Dieses musst du nun in ein double im Bereich 0 bis 1 umwandeln.


Eine Möglichkeit wäre das Byte Array erst in einen Integer umzuwandeln und dann durch den entsprechenden Maximalwert zu teilen. In etwa so:
var intVal = (array[0] << 24) | (array[1] << 16) | (array[2] << 8) | (array[3]);

var doubleVal = intVal / 4294967296.0;

Wie JavaScript genau intern mit Datentypen umgeht weiß ich nicht, deswegen keine Angabe auf Richtigkeit.
 
Oben