Random-Algorithmus mit Seed-Möglichkeit

[Michael (Gast)]

Hallo zusammen,

Ich nutze zurzeit folgenden Algorithmus zur Erzeugung von 
Pseudo-Zufallszahlen:

static uint32_t do_random(uint32_t *ctx)
{
    /*
     * Compute x = (7^5 * x) mod (2^31 - 1)
     * wihout overflowing 31 bits:
     *      (2^31 - 1) = 127773 * (7^5) + 2836
     * From "Random number generators: good ones are hard to find",
     * Park and Miller, Communications of the ACM, vol. 31, no. 10,
     * October 1988, p. 1195.
     */
    uint32_t hi, lo, x;

    x = *ctx;
    /* Can't be initialized with 0, so use another value. */
    if (x == 0)
        x = 123459876L;
    hi = x / 127773L;
    lo = x % 127773L;
    x = 16807L * lo - 2836L * hi;
    if (x < 0)
        x += 0x7fffffffL;
    return ((*ctx = x) % ((uint32_t)RANDOM_MAX + 1));
}

Als Seed kann man den Inhalt des Speichers, auf den *ctx zeigt, 
verwenden. Dies ist schön und gut, funktioniert aber nur zu Beginn vor 
der ersten Ausführung. Logisch kommt während der Laufzeit nochmals 
derselbe Wert vor, wiederholt sich die Zahlenabfolge ab diesen Moment.

Das ist aber mistig, denn während des Betriebes hätte ich eigentlich 
viel bessere Seeds zur Verfügung, ich kann aber nicht für deren 
Eindeutigkeit garantieren (A/D-Messwerte, Zeiten vom 
Übertragungsprotokoll usw.)

Ich bräuchte daher einen anderen Algorithmus, der eine "seed"-Methode 
hat, die man beliebig oft aufrufen kann - auch mit identischen Werten - 
aber dennoch den Dateninhalt als zusätzliche Entropie verwenden kann und 
nicht zu identischen Zahlenfolgen führt.

Kennt jemand solch einen Algorithmus?

Vielen Dank!


Liebe Grüße,

Michael

[micha (Gast)]

Michael schrieb:
> Als Seed kann man den Inhalt des Speichers, auf den *ctx zeigt,
> verwenden. Dies ist schön und gut, funktioniert aber nur zu Beginn vor
> der ersten Ausführung.

Äh, wieso soll das nur einmal funktionieren?

[foobar (Gast)]

Bei PRNGs erwarten man, dass bei gleichem Seed die gleichen Folge kommt. 
Ich denke, du willst eher ein "add_entropy" haben um ihn mit "echten" 
Zufall zu füttern.  Ist bei nem PRNG mit ganzen 32bit State aber 
ziemlich sinnlos.

[Michael (Gast)]

foobar schrieb:
> Ich denke, du willst eher ein "add_entropy" haben um ihn mit "echten"
> Zufall zu füttern.  Ist bei nem PRNG mit ganzen 32bit State aber
> ziemlich sinnlos.

Korrekt. Ich bin ja nicht auf die 32 Bits beschränkt, ich wüsste bloß 
momentan nicht, wo ich solch einen Algorithmus herbekommen könnte.

[derElf (Gast)]

z.B. hier: https://de.wikipedia.org/wiki/Xorshift

[Michael (Gast)]

derElf schrieb:
> z.B. hier: https://de.wikipedia.org/wiki/Xorshift

Wo besitzt dieser Algorithmus solch eine "add_entropy"-Methode?

[derElf (Gast)]

Du kannst einfach deine Entropie bits mit den state variablen des 
Algorithmus per logischem XOR verknüpfen.

Für Kryptografie ist dieser Generator allerdings nicht geeignet (siehe 
Wiki Artikel)

[Michael (Gast)]

derElf schrieb:
> Du kannst einfach deine Entropie bits mit den state variablen des
> Algorithmus per logischem XOR verknüpfen.

Das ist aber nicht gut! Ich bräuchte irgendwie erst noch was, was aus 
meinen Daten geeignete Werte hierfür macht.

Angenommen ich habe zweimal den Messwert 1992, dann kann ich das zwar 
XOR-verknüpfen, habe dann aber nichts gewonnen.

Beispiel: Ich habe 1991, 1992, 1991, 1992 Ergebnis bleibt gleich
Beispiel: Ich habe 1991, 1991, 1992, 1992 Ergebnis bleibt gleich

Aber hier steckt doch auch schon Information drin (nämlich in der Anzahl 
der "doppelten" Werte bzw. deren Reihenfolge usw.

[foobar (Gast)]

> ich wüsste bloß momentan nicht, wo ich solch einen Algorithmus
> herbekommen könnte.

Der PRNG vom Linux-Kernel hat das.  Allerdings ist das nen solider PRNG 
(für Crypto geeignet) und entsprechend komplex.  Inkl Paranoidmodus: er 
merkt sich, wieviel Entropie er reinbekommen hat und wenn er mehr Bits 
rausgegeben hat als Entropie reingekommen ist, blockiert er und warte 
auf neue.  "man 4 random"

Das glibc hatte nen schönen PRNG, deutlich schneller als deiner und viel 
größere Periode.  Ob der schon was zum reinmischen hatte, weiß ich nicht 
mehr.

Wie derElf schon schrieb, du kannst zusätzlichen Zufall in dein ctx 
reinmischen - ich würde allerdings eine Addition vorziehen, mischt 
besser.

Btw, deine 1991, 1992 sind keine geeigneten Daten, evtl das unterste Bit 
...

[Michael (Gast)]

foobar schrieb:
> Der PRNG vom Linux-Kernel hat das.  Allerdings ist das nen solider PRNG
> (für Crypto geeignet) und entsprechend komplex.  Inkl Paranoidmodus: er
> merkt sich, wieviel Entropie er reinbekommen hat und wenn er mehr Bits
> rausgegeben hat als Entropie reingekommen ist, blockiert er und warte
> auf neue.  "man 4 random"

Okay, ich habe mir den Quellcode einmal angesehen, das ist für meinen 
Anwendungszweck zu komplex. Aber geht funktional natürlich in die 
Richtung.


> Das glibc hatte nen schönen PRNG, deutlich schneller als deiner und viel
> größere Periode.  Ob der schon was zum reinmischen hatte, weiß ich nicht
> mehr.

Scheinbar nicht, jedenfalls habe ich bei meiner Recherche nichts 
entsprechendes gefunden.

> Btw, deine 1991, 1992 sind keine geeigneten Daten, evtl das unterste Bit
> ...

Du, das Problem ist, dass ich nicht weiß, in welchen Bits wirklich 
sinnvoll nutzbare Daten enthalten sind. Es könnte genauso gut 5980, 5990 
usw. sein, da wäre das unterste Bit "nutzlos".

Ich brauche ja nichts kryptographisch brauchbares, sondern einfach nur 
etwas, was nicht erwartbare Perioden erzeugt. Ob jetzt jeder Wert auf 
lange Zeit gesehen wirklich exakt dieselbe Wahrscheinlichkeit hat, ist 
für meinen Anwendungszweck völlig unerheblich.

Meiner Meinung gibt es ja schon Konzepte um aus identischen 
Eingangsdaten unterschiedliche Ausgangsdaten zu erzeugen. Nehme ich zum 
Beispiel einen kyptographischen Hash (wie SHA) erhalte ich bei einer 
Null, einen anderen Wert als bei zwei Nullen oder drei Nullen.

Solch einen Ansatz bräuchte ich einmal auch für Nicht-Mathematiker 
verständlich. ;-)

Momentan nutze ich einfach 1 Kilobyte uninitialisiertes RAM nach dem 
Einschalten zur Erzeugung eines initialen Seed-Wertes (durch Rotieren 
und XOR) und lasse den Algorithmus dann laufen, da ich aber mehrere 
Zufallswerte pro Sekunde brauche und das Gerät mehrere Monate am Stück 
läuft, ist es nicht sinnvoll, da die Entropie in meinen 32 Bits 
Initialwert einfach irgendwann erschöpft sind. Und ich wollte halt die 
zeitlichen Abständen zwischen empfangenen Paketen, deren Prüfsummen und 
Längenangaben sowie Messwerte (A/D usw.) immer wieder in den "Seed" 
hineinstecken, aber bitte so intelligent, dass auch durch "unpassende" 
Werte (zwanzig Mal derselbe Wert zum Beispiel) die Entropie dadurch 
nicht schlechter wird.