pqRNG - ein Pseudo-Zufallszahlengenerator mit voller Periodenlänge ohne Bias

[Karl-Uwe Frank]

Heute möchte ich einen neuen Pseudo-Zufallszahlengenerator vorstellen,
den ich in den letzten Wochen entwickelt habe. Konstruktive Kritik
oder Anregungen sind willkommen.

Mathematische Formel für pqRNG

Q[n] = ((Q[n-1] xor R) * P) mod M

Die volle Periodenlänge aller Integer-Werte zwischen 0 und 2**n ohne
Bias wird erreicht wenn folgende Bedingungen eingehalten werden

R mod 8 = 5
P mod 8 = 3

M = 2**n >= 8

Ein Vorteil dieses Pseudo-Zufallszahlengenerators ist, dass er mit 3
unterschiedlichen Zufalls- oder selektierten Werten für Q, P und R als
IV (Initialisationsvektoren) versorgt werden kann. Natürlich müssen
die Werte für R und P entsprechend angepasst werden, um die volle
Periodenlänge von 2**n zu erreichen. Bedingt durch die mathematische
Relation zwischen R und P wird die Anzahl maximal möglicher,
unterschiedlicher Pseudo-Zufallsreihen (2**n/4) definiert.

Hier ein kurzes Beispiel für eine Zahlenreihe mit voller Periodenlänge
von M

Start IV (pqRNG)
Q = 0, P = 3, R = 13, M = 16

7, 14, 9, 12, 3, 10, 5, 8, 15, 6, 1, 4, 11, 2, 13, 0

Das Ergebnis von pqRNG in 32bit Binärwerten im Integer Interval [0,
255] mit M = 2147483647 besteht sehr überzeugend und dauerhaft alle
empirischen und statistischen Test auf Zufälligkeit, als da wären
FIPS-140-1, Diehard Test Battery, Frequency-, Poker-, Runs-, Long-Runs
and Serial-Test, ebenso wie Monte Carlo Wert von Pi, Arithmetischer
Mittelwert, Serieller Korrelationskoeffizient und selbstverständlich
erzeugt er eine gute gleichmäßige Verteilung der Werte 0 und 1.

Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
betrachtet werden.

Weitere Informationen sind zu finden unter http://www.freecx.co.uk/pqRNG/

Cheers,
Karl-Uwe

---
Copyright (c) 2011, Karl-Uwe Frank
All rights reserved.

[Richard W. Könning]

Karl-Uwe Frank <karl....@freecx.co.uk> wrote:

>Heute möchte ich einen neuen Pseudo-Zufallszahlengenerator vorstellen,

>[...]

>
>Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
>betrachtet werden.

Wozu dann das Posting in dcsm? Physiker z.B. dürften eher was damit
anfangen können.
Ciao,
Richard
--
Dr. Richard Könning Heßstraße 63
Tel.: 089/5232488 80798 München

[Karl-Uwe Frank]

On Nov 4, 2:33 am, Richard W. Könning <Richard.Koenn...@t-online.de>
wrote:

> Karl-Uwe Frank <karl.fr...@freecx.co.uk> wrote:
> >Heute möchte ich einen neuen Pseudo-Zufallszahlengenerator vorstellen,
> >[...]
>
> >Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
> >betrachtet werden.
>
> Wozu dann das Posting in dcsm? Physiker z.B. dürften eher was damit
> anfangen können.
>

Der Algorithmus ist bisher noch nicht unter kryptographischen
Gesichtspunkten untersucht worden, weshalb er meines Erachtens
zunächst einmal als kryptographisch sicher betrachtet werden muss. Da
meine Intention aber die Entwicklung eines PRNG für kryptografische
Zwecke ist, habe ich hier gepostet.

Cheers,
Karl-Uwe

[Lars Gebauer]

* Karl-Uwe Frank:

> Der Algorithmus ist bisher noch nicht unter kryptographischen
> Gesichtspunkten untersucht worden, weshalb er meines Erachtens
> zunächst einmal als kryptographisch sicher betrachtet werden muss.

Äh?! - Nein!

Der Algorithmus gilt in diesem Fall als "nicht hinreichend untersucht"
weswegen er *nicht* als "stark" betrachtet werden *kann*. Das heißt, er
ist potentiell "schwach".

[Juergen P. Meier]

Karl-Uwe Frank <karl....@freecx.co.uk>:

> Der Algorithmus ist bisher noch nicht unter kryptographischen
> Gesichtspunkten untersucht worden, weshalb er meines Erachtens
> zunächst einmal als kryptographisch sicher betrachtet werden muss. Da

Falsch herum. Das genaue Gegenteil ist der Fall.

[Karl-Uwe Frank]

On Nov 4, 11:59 am, Lars Gebauer <lgeba...@arcor.de> wrote:
> * Karl-Uwe Frank:
>
> > Der Algorithmus ist bisher noch nicht unter kryptographischen
> > Gesichtspunkten untersucht worden, weshalb er meines Erachtens

> > zun chst einmal als kryptographisch sicher betrachtet werden muss.

>
> h?! - Nein!
>
> Der Algorithmus gilt in diesem Fall als "nicht hinreichend untersucht"

> weswegen er *nicht* als "stark" betrachtet werden *kann*. Das hei t, er
> ist potentiell "schwach".

Sorry, natürlich! ... es sollte auch lauten ==> "kryptographisch
*NICHT* sicher betrachtet werden muss" <==, wie Eingangs ja bereits
erwähnt. Beim Posten der ersten Antwort ist mir ein klassischer "Copy-
Paste"-Fehler unterlaufen. ;-)

[Karl-Uwe Frank]

On Nov 4, 1:48 pm, "Juergen P. Meier" <nospam-1...@jors.net> wrote:
> Karl-Uwe Frank <karl.fr...@freecx.co.uk>:

>
> > Der Algorithmus ist bisher noch nicht unter kryptographischen
> > Gesichtspunkten untersucht worden, weshalb er meines Erachtens

> > zun chst einmal als kryptographisch sicher betrachtet werden muss. Da

>
> Falsch herum. Das genaue Gegenteil ist der Fall.

Exakt so war es gemeint.

[Richard W. Könning]

Karl-Uwe Frank <karl....@freecx.co.uk> wrote:

>Heute möchte ich einen neuen Pseudo-Zufallszahlengenerator vorstellen,
>den ich in den letzten Wochen entwickelt habe. Konstruktive Kritik
>oder Anregungen sind willkommen.
>
>Mathematische Formel für pqRNG
>
> Q[n] = ((Q[n-1] xor R) * P) mod M
>

>[...]

>Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
>betrachtet werden.

Das Teil hat doch arge Ähnlichkeit zu linearen Kongruenzgeneratoren
(die als gebrochen gelten). Hierzu empfehle ich die Lektüre von
http://www.rfc-editor.org/rfc/rfc1750.txt, p. 6 ff. Dort wird für
allgemeinere Kongruenzgeneratoren auf "How to Predict Congruential
Generators, Journal of Algorithms, V. 13, N. 4, December 1992, H.
Krawczyk" verwiesen.

[Karl-Uwe Frank]

Richard W. Könning wrote:
> Karl-Uwe Frank <karl....@freecx.co.uk> wrote:
>

> >Heute m�chte ich einen neuen Pseudo-Zufallszahlengenerator vorstellen,

> >den ich in den letzten Wochen entwickelt habe. Konstruktive Kritik
> >oder Anregungen sind willkommen.
> >

> >Mathematische Formel f�r pqRNG

> >
> > Q[n] = ((Q[n-1] xor R) * P) mod M
> >
> >[...]
> >Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
> >betrachtet werden.
>

> Das Teil hat doch arge �hnlichkeit zu linearen Kongruenzgeneratoren
> (die als gebrochen gelten). Hierzu empfehle ich die Lekt�re von
> http://www.rfc-editor.org/rfc/rfc1750.txt, p. 6 ff. Dort wird f�r

> allgemeinere Kongruenzgeneratoren auf "How to Predict Congruential
> Generators, Journal of Algorithms, V. 13, N. 4, December 1992, H.
> Krawczyk" verwiesen.

Vielen Dank für diese Information. Und ja, hat eine gewisse
Ähnlichkeit zu linearen Kongruenzgeneratoren ist vorhanden. Allerdings
unterscheidet sich mein Algorithmus in Bezug auf die Möglichkeit ihn
mit 2 zufällig ausgewählten Zahlenwerten für P und R zu versorgen,
ohne das er in einen Bias gerät oder nicht die volle Periodenlänge von
M erreicht. Bei linearen Kongruenzgeneratoren müssen die Konstanten
sorgfältig ausgewählt werden um dies zu erreichen. Außerdem sind es ja
Konstanten und keine Variablen. Natürlich ist es gut vorstellbar, dass
ein solcher simpler Algorithmus, wie ich ihn hier vorgestellt habe,
sehr leicht gebrochen werden kann, also eine Abwandlung der im Artikel
beschriebenen Vorgehensweise auch bei meiner Formel zu besagtem Ziel
führen wird. Betrachtet werden sollte mein Algorithmus deshalb eher
als Ausgangspunkt für eine "verstärkte" Version, die solchen Angriffen
widerstehen wird. Eine entsprechende Weiterentwicklung habe ich
bereits begonnen.

Cheers,
Karl-Uwe

[Paul Ebermann]

Karl-Uwe Frank skribis:

> Heute möchte ich einen neuen Pseudo-Zufallszahlengenerator vorstellen,
> den ich in den letzten Wochen entwickelt habe. Konstruktive Kritik
> oder Anregungen sind willkommen.
>
> Mathematische Formel für pqRNG
>
> Q[n] = ((Q[n-1] xor R) * P) mod M
>
> Die volle Periodenlänge aller Integer-Werte zwischen 0 und 2**n ohne
> Bias wird erreicht wenn folgende Bedingungen eingehalten werden
>
> R mod 8 = 5
> P mod 8 = 3
>
> M = 2**n >= 8
>
> Ein Vorteil dieses Pseudo-Zufallszahlengenerators ist, dass er mit 3
> unterschiedlichen Zufalls- oder selektierten Werten für Q, P und R als
> IV (Initialisationsvektoren) versorgt werden kann. Natürlich müssen
> die Werte für R und P entsprechend angepasst werden, um die volle
> Periodenlänge von 2**n zu erreichen. Bedingt durch die mathematische
> Relation zwischen R und P wird die Anzahl maximal möglicher,
> unterschiedlicher Pseudo-Zufallsreihen (2**n/4) definiert.

Ist das 2^(n/4), oder (2^n)/4?

Ich hätte jetzt erst einmal auf 2^((n-3)+(n-3)) getippt (das sind die
möglichen Kombinationen von P und Q), wobei ich jetzt nicht untersucht
habe, ob einige davon die selbe Folge ergeben.

> Hier ein kurzes Beispiel für eine Zahlenreihe mit voller Periodenlänge
> von M
>
> Start IV (pqRNG)
> Q = 0, P = 3, R = 13, M = 16
>
> 7, 14, 9, 12, 3, 10, 5, 8, 15, 6, 1, 4, 11, 2, 13, 0

Die anderen möglichen Reihen für dieses M sind (alle mit Q=0 endend):

P = 3, R = 5:

15, 14, 1, 12, 11, 10, 13, 8, 7, 6, 9, 4, 3, 2, 5, 0

P = 11, R = 5:

7, 6, 1, 12, 3, 2, 13, 8, 15, 14, 9, 4, 11, 10, 5, 0

P = 11, R = 13

15, 6, 9, 12, 11, 2, 5, 8, 7, 14, 1, 4, 3, 10, 13, 0

Betrachte die Spalten hier.
Alle 8-en kommen genau eine halbe Periode vor/nach der jeweiligen 0, und
genau dazwischen kommen 4 und 12. Alle anderen Zahlen kommen immer in
jeweils genau zwei Zeilen in der selben Spalte vor (und jeweils mit dem
selben Partner, nämlich x XOR 8).

Das noch "zufällig" zu nennen ist nicht glaubwürdig.

> Das Ergebnis von pqRNG in 32bit Binärwerten im Integer Interval [0,
> 255] mit M = 2147483647

Huh. Dieses M ist als ungerade Zahl sicher keine Zweierpotenz (das ist
2^31-1, wenn ich das richtig sehe), und das Intervall [0, 255] ist auch
nicht groß genug für 32-bit Zahlen. Was genau hast du da getestet?

> besteht sehr überzeugend und dauerhaft alle
> empirischen und statistischen Test auf Zufälligkeit, als da wären
> FIPS-140-1, Diehard Test Battery, Frequency-, Poker-, Runs-, Long-Runs
> and Serial-Test, ebenso wie Monte Carlo Wert von Pi, Arithmetischer
> Mittelwert, Serieller Korrelationskoeffizient und selbstverständlich
> erzeugt er eine gute gleichmäßige Verteilung der Werte 0 und 1.

Hmm, in deinem obigen Beispiel kommen abwechselnd gerade und ungerade
Zahlen heraus. Wenn ich die Formel richtig verstehe, ist das sogar immer
so (auch bei größeren n). Wenn das keiner deiner Tests erfasst hat,
können die Tests nicht so toll sein.

> Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
> betrachtet werden.

Ja, und ich glaube nicht, dass das nur an mangelnder Analyse liegt.


Paul

[Karl-Uwe Frank]

On Nov 5, 3:49 pm, Paul Ebermann <Paul-Eberm...@gmx.de> wrote:
> Karl-Uwe Frank skribis:
>

[snip]

> > Bedingt durch die mathematische
> > Relation zwischen R und P wird die Anzahl maximal möglicher,
> > unterschiedlicher Pseudo-Zufallsreihen (2**n/4) definiert.
>
> Ist das 2^(n/4), oder (2^n)/4?
>
> Ich hätte jetzt erst einmal auf 2^((n-3)+(n-3)) getippt (das sind die
> möglichen Kombinationen von P und Q), wobei ich jetzt nicht untersucht
> habe, ob einige davon die selbe Folge ergeben.
>

"Maaartin G" hatte mich bereits drauf aufmerksam gemacht, dass ich den
falschen Wert angegeben hatte und die Anzahl maximal möglicher,
unterschiedlicher Pseudo-Zufallsreihen ja mit 2^(2n-6) definiert wird.
Auf der Homepage habe ich das bereits geändert, hier gibt es leider
keine "Edit"-Funktion.

> > Hier ein kurzes Beispiel für eine Zahlenreihe mit voller Periodenlänge
> > von M
>
> > Start IV (pqRNG)
> > Q = 0, P = 3, R = 13, M = 16
>
> > 7, 14, 9, 12, 3, 10, 5, 8, 15, 6, 1, 4, 11, 2, 13, 0
>
> Die anderen möglichen Reihen für dieses M sind (alle mit Q=0 endend):

Was logisch ist wenn ich mit Q=0 beginne, denn wenn die volle
Periodenlänge erreicht ist nimmt Q zwangsläufig wieder den Startwert
an.

> P = 3, R = 5:
>
> 15, 14, 1, 12, 11, 10, 13, 8, 7, 6, 9, 4, 3, 2, 5, 0
>
> P = 11, R = 5:
>
> 7, 6, 1, 12, 3, 2, 13, 8, 15, 14, 9, 4, 11, 10, 5, 0
>
> P = 11, R = 13
>
> 15, 6, 9, 12, 11, 2, 5, 8, 7, 14, 1, 4, 3, 10, 13, 0
>
> Betrachte die Spalten hier.
> Alle 8-en kommen genau eine halbe Periode vor/nach der jeweiligen 0, und
> genau dazwischen kommen 4 und 12. Alle anderen Zahlen kommen immer in
> jeweils genau zwei Zeilen in der selben Spalte vor (und jeweils mit dem
> selben Partner, nämlich x XOR 8).
>

Dies ist mir Anfangs bereits aufgefallen. Es gibt so betrachtet 4
immer gleiche Zahlenwerte an immer der gleichen Position in allen
2^(2n-6) möglichen Zahlenreihen. Einmal an Position ((2^n)/4)*1, dann
Position ((2^n)/4)*2 sowie Position ((2^n)/4)*3 und die zwangsläufige
Endposition der Periode bei ((2^n)/4)*4. Daher der Wert (2**n/4) ich
hatte ihn nur falsch ausgeschrieben und zugeordnet.

> Das noch "zufällig" zu nennen ist nicht glaubwürdig.
>

Völlig normal und zu erwarten, denn es sind ja auch Pseudo-
Zufallszahlen die hier erzeugt werden. Weiterhin ist es, in Anbetracht
der großen Anzahl möglicher Zahlenreihen unerheblich, da Q ja nicht
immer den Wert gleichen Startwert haben sollten.

> > Das Ergebnis von pqRNG in 32bit Binärwerten im Integer Interval [0,
> > 255] mit M = 2147483647
>
> Huh. Dieses M ist als ungerade Zahl sicher keine Zweierpotenz (das ist
> 2^31-1, wenn ich das richtig sehe), und das Intervall [0, 255] ist auch
> nicht groß genug für 32-bit Zahlen. Was genau hast du da getestet?

Dieses M ist zwangsläufig eine ungerade Zahl, wenn mit signed Int32
gerechnet wird.

Aus meiner Sicht ist Q nur ein Art "Träger", aus dem die benötigten
Informationen extrahiert werden. Wenn also Byte benötigt werden, dann
greift folgende Formel

Byte = Q >> 23 and 0xff

> > besteht sehr überzeugend und dauerhaft alle
> > empirischen und statistischen Test auf Zufälligkeit, als da wären
> > FIPS-140-1, Diehard Test Battery, Frequency-, Poker-, Runs-, Long-Runs
> > and Serial-Test, ebenso wie Monte Carlo Wert von Pi, Arithmetischer
> > Mittelwert, Serieller Korrelationskoeffizient und selbstverständlich
> > erzeugt er eine gute gleichmäßige Verteilung der Werte 0 und 1.
>
> Hmm, in deinem obigen Beispiel kommen abwechselnd gerade und ungerade
> Zahlen heraus. Wenn ich die Formel richtig verstehe, ist das sogar immer
> so (auch bei größeren n). Wenn das keiner deiner Tests erfasst hat,
> können die Tests nicht so toll sein.
>

Die Testergebnisse findest Du auf der Webseite. Die Tests wurden auf
Dateien mit jeweils 10 Mio. Byte durchgeführt. Die Programme sind dort
auch alle benannt und verlinkt.

> > Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
> > betrachtet werden.
>
> Ja, und ich glaube nicht, dass das nur an mangelnder Analyse liegt.
>

Er ist nicht kryptographisch sicher, da er nicht als solcher
konzipiert ist.

Karl-Uwe

[Paul Ebermann]

Karl-Uwe Frank skribis:

> On Nov 5, 3:49 pm, Paul Ebermann <Paul-Eberm...@gmx.de> wrote:
>> Karl-Uwe Frank skribis:

>>> Hier ein kurzes Beispiel für eine Zahlenreihe mit voller Periodenlänge
>>> von M
>>
>>> Start IV (pqRNG)
>>> Q = 0, P = 3, R = 13, M = 16
>>
>>> 7, 14, 9, 12, 3, 10, 5, 8, 15, 6, 1, 4, 11, 2, 13, 0
>>
>> Die anderen möglichen Reihen für dieses M sind (alle mit Q=0 endend):
> Was logisch ist wenn ich mit Q=0 beginne, denn wenn die volle
> Periodenlänge erreicht ist nimmt Q zwangsläufig wieder den Startwert
> an.

(Ja, der Klammer-Ausdruck war bloß, um klarzustellen, wie die Reihen
ausgerichtet wurden.)

>> P = 3, R = 5:
>>
>> 15, 14, 1, 12, 11, 10, 13, 8, 7, 6, 9, 4, 3, 2, 5, 0
>>
>> P = 11, R = 5:
>>
>> 7, 6, 1, 12, 3, 2, 13, 8, 15, 14, 9, 4, 11, 10, 5, 0
>>
>> P = 11, R = 13
>>
>> 15, 6, 9, 12, 11, 2, 5, 8, 7, 14, 1, 4, 3, 10, 13, 0
>>
>> Betrachte die Spalten hier.
>> Alle 8-en kommen genau eine halbe Periode vor/nach der jeweiligen 0, und
>> genau dazwischen kommen 4 und 12. Alle anderen Zahlen kommen immer in
>> jeweils genau zwei Zeilen in der selben Spalte vor (und jeweils mit dem
>> selben Partner, nämlich x XOR 8).
>
> Dies ist mir Anfangs bereits aufgefallen. Es gibt so betrachtet 4
> immer gleiche Zahlenwerte an immer der gleichen Position in allen
> 2^(2n-6) möglichen Zahlenreihen. Einmal an Position ((2^n)/4)*1, dann
> Position ((2^n)/4)*2 sowie Position ((2^n)/4)*3 und die zwangsläufige
> Endposition der Periode bei ((2^n)/4)*4. Daher der Wert (2**n/4) ich
> hatte ihn nur falsch ausgeschrieben und zugeordnet.
>
>> Das noch "zufällig" zu nennen ist nicht glaubwürdig.
>>
> Völlig normal und zu erwarten, denn es sind ja auch Pseudo-
> Zufallszahlen die hier erzeugt werden.

Hmm, bei Pseudo-Zufall erwarte ich, dass es so aussieht wie Zufall. Und
es sieht hier nicht wirklich so aus. Aber das mögen andere Leute anders
sehen.

> Weiterhin ist es, in Anbetracht
> der großen Anzahl möglicher Zahlenreihen unerheblich, da Q ja nicht
> immer den Wert gleichen Startwert haben sollten.

Den aktuellen Wert für Q kann man direkt aus der Ausgabe erhalten. Mit
zwei weiteren Werten (die im obigen Beispiel für n = 4 jeweils nur ein
Bit liefern, der Rest ist vorhersagbar) erhalten wir dann auch P und R.

Als Beispiel: Ich sehe eine Ausgabe von 7. Dann muss der nächste Wert
entweder 6 (für R = 5) oder 14 sein (für R = 13). Danach folgt dann
entweder 1 (für P = 11) oder 9 (für P = 3).
Danach kann man den Rest der Sequenz komplett vorhersagen.

Das gilt auch rückwärts: Vor der 7 müssen entweder 8 (für P ⊕ R = 2)
oder 0 (für P ⊕ R = 10) gekommen sein, davor 5 (für P = 11) oder 13 (für
P = 3).

>>> Das Ergebnis von pqRNG in 32bit Binärwerten im Integer Interval [0,
>>> 255] mit M = 2147483647
>>
>> Huh. Dieses M ist als ungerade Zahl sicher keine Zweierpotenz (das ist
>> 2^31-1, wenn ich das richtig sehe), und das Intervall [0, 255] ist auch
>> nicht groß genug für 32-bit Zahlen. Was genau hast du da getestet?
>
> Dieses M ist zwangsläufig eine ungerade Zahl, wenn mit signed Int32
> gerechnet wird.

Einfaches Rechnen mit 32-Bit Integer Werten (mit Abschneiden von
Übertrag-Bits) ist nicht das gleiche wie Rechnen modulo 2147483647,
sondern modulo 2^32.

Ich habe keine Ahnung, was du da wirklich implementiert und getestet hast.

M = 2147483647 passt jedenfalls nicht zur Beschreibung M = 2^n im
Algorithmus.

> Aus meiner Sicht ist Q nur ein Art "Träger", aus dem die benötigten
> Informationen extrahiert werden. Wenn also Byte benötigt werden, dann
> greift folgende Formel
>
> Byte = Q >> 23 and 0xff

Okay, du ignorierst also die unteren Bits und extrahierst 8 Bit aus dem
oberen Ende.
Das solltest du unbedingt mit in die Beschreibung des Algorithmus
hineinschreiben. (So kommt natürlich das "abwechselnd gerade und
ungerade" nicht mehr zum Tragen, und auch die Analyse, die ich oben für
n = 3 gemacht habe, geht nicht mehr ganz so einfach.)

>>> Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
>>> betrachtet werden.
>>
>> Ja, und ich glaube nicht, dass das nur an mangelnder Analyse liegt.
>
> Er ist nicht kryptographisch sicher, da er nicht als solcher
> konzipiert ist.

Das klang am Anfang anders, aber gut dass das klargestellt ist.

Für Simulationsexperimente mag dein PRNG ja nützlich sein.


Paul

[Karl-Uwe Frank]

On Nov 6, 7:48 pm, Paul Ebermann <Paul-Eberm...@gmx.de> wrote:
> Karl-Uwe Frank skribis:
>
> > On Nov 5, 3:49 pm, Paul Ebermann <Paul-Eberm...@gmx.de> wrote:
> >> Karl-Uwe Frank skribis:
> >>> Hier ein kurzes Beispiel für eine Zahlenreihe mit voller Periodenlänge
> >>> von M
>
> >>> Start IV (pqRNG)
> >>> Q = 0, P = 3, R = 13, M = 16
>
> >>> 7, 14, 9, 12, 3, 10, 5, 8, 15, 6, 1, 4, 11, 2, 13, 0
>
> >> Die anderen möglichen Reihen für dieses M sind (alle mit Q=0 endend):
> > Was logisch ist wenn ich mit Q=0 beginne, denn wenn die volle
> > Periodenlänge erreicht ist nimmt Q zwangsläufig wieder den Startwert
> > an.
>
> (Ja, der Klammer-Ausdruck war bloß, um klarzustellen, wie die Reihen
> ausgerichtet wurden.)
>

Ah, okay. Ich habe fest Laufweite für den Text eingestellt und daher
die Reihen sauber formatiert gesehen. Deshalb wohl das Missverständnis
mit der eingeklammerten Erläuterung.

[snip]

> >> Das noch "zufällig" zu nennen ist nicht glaubwürdig.
>
> > Völlig normal und zu erwarten, denn es sind ja auch Pseudo-
> > Zufallszahlen die hier erzeugt werden.
>
> Hmm, bei Pseudo-Zufall erwarte ich, dass es so aussieht wie Zufall. Und
> es sieht hier nicht wirklich so aus. Aber das mögen andere Leute anders
> sehen.

Na ja, also eine Zahlenreihe mit 16 unterschiedlichen Werten ist doch
wohl auch eher selten in der Realität anzutreffen wenn es um
Zufallszahlen geht. Bei größeren Wertebereichen sieht es schon sehr
schön zufällig aus.

> > Weiterhin ist es, in Anbetracht
> > der großen Anzahl möglicher Zahlenreihen unerheblich, da Q ja nicht
> > immer den Wert gleichen Startwert haben sollten.
>
> Den aktuellen Wert für Q kann man direkt aus der Ausgabe erhalten. Mit
> zwei weiteren Werten (die im obigen Beispiel für n = 4 jeweils nur ein
> Bit liefern, der Rest ist vorhersagbar) erhalten wir dann auch P und R.
>
> Als Beispiel: Ich sehe eine Ausgabe von 7. Dann muss der nächste Wert
> entweder 6 (für R = 5) oder 14 sein (für R = 13). Danach folgt dann
> entweder 1 (für P = 11) oder 9 (für P = 3).
> Danach kann man den Rest der Sequenz komplett vorhersagen.
>
> Das gilt auch rückwärts: Vor der 7 müssen entweder 8 (für P ⊕ R = 2)
> oder 0 (für P ⊕ R = 10) gekommen sein, davor 5 (für P = 11) oder 13 (für
> P = 3).

Das ist, wie ich finde, ein sehr gutes Beispiel dafür, wie man einen
LCG-ähnlichen PRNG "knacken" kann. Es stellt sich mir allerdings die
Frage, wie es aussieht, wenn M=2^31-1 ist? Kann dann immer noch so
leicht die ganze Sequenz errechnet werden? Theoretisch müsste es ja
möglich sein, da sich nur der Wertebereich vergrößert, die
Zahlenverhältnisse aber konstant bleiben.

> >>> Das Ergebnis von pqRNG in 32bit Binärwerten im Integer Interval [0,
> >>> 255] mit M = 2147483647
>
> >> Huh. Dieses M ist als ungerade Zahl sicher keine Zweierpotenz (das ist
> >> 2^31-1, wenn ich das richtig sehe), und das Intervall [0, 255] ist auch
> >> nicht groß genug für 32-bit Zahlen. Was genau hast du da getestet?
>
> > Dieses M ist zwangsläufig eine ungerade Zahl, wenn mit signed Int32
> > gerechnet wird.
>
> Einfaches Rechnen mit 32-Bit Integer Werten (mit Abschneiden von
> Übertrag-Bits) ist nicht das gleiche wie Rechnen modulo 2147483647,
> sondern modulo 2^32.
>
> Ich habe keine Ahnung, was du da wirklich implementiert und getestet hast.
>

Wie gesagt, bei signed Int32 kann ich keiner Variable 2^32 zuordnen,
daher 2^31-1. Trotzdem werden alle Integer jeweils einmal in einer
vollen Periode errechnet, was ich mehrfach ausprobiert habe. Den
Zähler als Int64 auf 2^32 setzen, Q, P und R als Int32 (Uint32 bietet
mein Compiler nicht an), dann M=0x7ffffff, alle Ergebnisse in mehrere
Dateien auf Platte schreiben, dann alles per MergeSort in eine
sortierte Datei und diese schichtweg seqenziell auf fehlende Werte und
Duplikate überprüfen. Es gab keine fehlenden Werte und keine Duplikate
in mehreren Testläufen mit unteschiedlichen Werten für Q, P und R. Bei
M=2^4, M=2^5, M=2^6, etc. ist das ja sehr einfach und schnell
nachzuprüfen.

> M = 2147483647 passt jedenfalls nicht zur Beschreibung M = 2^n im
> Algorithmus.
>

Wie gesagt, Int32 bietet mir keine andere Möglichkeit. Wähle ich für
Q, P und R Int64 und setze M=2^32 werden alle Werte von 0 bis 2^32
berechnet. Kann auch sehr einfach nachgeprüft werden.

Außerdem ist es doch wohl so, dass der Algorithmus, wenn er alle Werte
bei kleinem Modulo 2^n errechnet, dies auch bei größerem Modulo, z.B.
2^32 oder 2^64 tun wird. Das Verhältnis der Werte in der Formel
verändert sich ja nicht durch einen größeren Modulo, oder?

> > Aus meiner Sicht ist Q nur ein Art "Träger", aus dem die benötigten
> > Informationen extrahiert werden. Wenn also Byte benötigt werden, dann
> > greift folgende Formel
>
> > Byte = Q >> 23 and 0xff
>
> Okay, du ignorierst also die unteren Bits und extrahierst 8 Bit aus dem
> oberen Ende.

Ja, so seht es auch auf der Webseite bei den Testergebnissen, auch
wenn die Formel etwas anders geschrieben ist. Momentan favorisiere
ich
Byte = Q >> 24 , weil es eine weitere Rechenoperation erspart.

> Das solltest du unbedingt mit in die Beschreibung des Algorithmus
> hineinschreiben.

Das ist aber dann eine Einschränkung des Algorithmus, denn wie die
Werte von Q letztlich gehandhabt werden hängt doch von dem jeweiligen
Verwendungszweck ab. Bei Spielen werden sehr häufig nur Nullen und
Einsen benötigt, also berechne ich Byte = Q >> 30 & 0x1, bei anderen
Anwendungen werden Hex-Byte benötigt, dann gibt Byte = Q >> 24, bei
anderer Anwendung werden wieder andere Werte benötigt, die auf andere
Art aus Q gewonnen werden können. Da dies aber im Vorfeld unklar ist,
kann ich den Algorithmus nicht auf die eine oder andere Art festlegen.

> (So kommt natürlich das "abwechselnd gerade und
> ungerade" nicht mehr zum Tragen, und auch die Analyse, die ich oben für
> n = 3 gemacht habe, geht nicht mehr ganz so einfach.)
>

Es wäre schon interessant zu erfahren, ob und wie einfach man nur aus
der erzeugten Bytefolge auf die Werte für Q, P und R schließen kann.
Aber selbst wenn ich Dir nun 32 aufeinanderfolgende Werte von Q
benenne, denke ich, wird es Dir nicht so einfach fallen auf P und R zu
schließen, oder irre ich mich hier?

> >>> Anmerkung: Dieser PRNG kann nicht als kryptographisch sicher
> >>> betrachtet werden.
>
> >> Ja, und ich glaube nicht, dass das nur an mangelnder Analyse liegt.
>
> > Er ist nicht kryptographisch sicher, da er nicht als solcher
> > konzipiert ist.
>
> Das klang am Anfang anders, aber gut dass das klargestellt ist.
>

In der Anmerkung steht es ja, die Idee mit dem XOR war wohl etwas
vorschnell von mir gedacht, ist aber bereits entfernt.

> Für Simulationsexperimente mag dein PRNG ja nützlich sein.
>

Womit doch schon einmal eine sehr gute Einsatzmöglichkeit gefunden
wäre. :-)

Cheers,
Karl-Uwe

[Richard W. Könning]

Karl-Uwe Frank <karl....@freecx.co.uk> wrote:

>Richard W. Könning wrote:
>> Karl-Uwe Frank <karl....@freecx.co.uk> wrote:
>>

>> Das Teil hat doch arge ?hnlichkeit zu linearen Kongruenzgeneratoren
>> (die als gebrochen gelten). Hierzu empfehle ich die Lekt?re von
>> http://www.rfc-editor.org/rfc/rfc1750.txt, p. 6 ff. Dort wird f?r

>> allgemeinere Kongruenzgeneratoren auf "How to Predict Congruential
>> Generators, Journal of Algorithms, V. 13, N. 4, December 1992, H.
>> Krawczyk" verwiesen.

>Vielen Dank für diese Information. Und ja, hat eine gewisse
>Ähnlichkeit zu linearen Kongruenzgeneratoren ist vorhanden. Allerdings
>unterscheidet sich mein Algorithmus in Bezug auf die Möglichkeit ihn
>mit 2 zufällig ausgewählten Zahlenwerten für P und R zu versorgen,
>ohne das er in einen Bias gerät oder nicht die volle Periodenlänge von
>M erreicht. Bei linearen Kongruenzgeneratoren müssen die Konstanten
>sorgfältig ausgewählt werden um dies zu erreichen. Außerdem sind es ja

Die Statistik ist nicht das kryptographische Problem bei den linearen
Kongruenzgeneratoren.

>Konstanten und keine Variablen. Natürlich ist es gut vorstellbar, dass
>ein solcher simpler Algorithmus, wie ich ihn hier vorgestellt habe,
>sehr leicht gebrochen werden kann, also eine Abwandlung der im Artikel
>beschriebenen Vorgehensweise auch bei meiner Formel zu besagtem Ziel
>führen wird. Betrachtet werden sollte mein Algorithmus deshalb eher
>als Ausgangspunkt für eine "verstärkte" Version, die solchen Angriffen
>widerstehen wird. Eine entsprechende Weiterentwicklung habe ich
>bereits begonnen.

Ich verstehe nicht so recht, warum Du diesen Weg gehen willst. Es gibt
bessere Entwürfe für PRNG, die nicht schon von Anfang mit
grundlegenden Problemen zu kämpfen haben.

[Paul Ebermann]

Karl-Uwe Frank skribis:
> On Nov 6, 7:48 pm, Paul Ebermann <Paul-Eberm...@gmx.de> wrote:
>> Karl-Uwe Frank skribis:
>>> On Nov 5, 3:49 pm, Paul Ebermann <Paul-Eberm...@gmx.de> wrote:

>>>>> Das Ergebnis von pqRNG in 32bit Binärwerten im Integer Interval [0,
>>>>> 255] mit M = 2147483647
>>
>>>> Huh. Dieses M ist als ungerade Zahl sicher keine Zweierpotenz (das ist
>>>> 2^31-1, wenn ich das richtig sehe), und das Intervall [0, 255] ist auch
>>>> nicht groß genug für 32-bit Zahlen. Was genau hast du da getestet?
>>
>>> Dieses M ist zwangsläufig eine ungerade Zahl, wenn mit signed Int32
>>> gerechnet wird.
>>
>> Einfaches Rechnen mit 32-Bit Integer Werten (mit Abschneiden von
>> Übertrag-Bits) ist nicht das gleiche wie Rechnen modulo 2147483647,
>> sondern modulo 2^32.
>>

>> Ich habe keine Ahnung, was du da wirklich implementiert und getestet hast..

>
> Wie gesagt, bei signed Int32 kann ich keiner Variable 2^32 zuordnen,
> daher 2^31-1. Trotzdem werden alle Integer jeweils einmal in einer
> vollen Periode errechnet, was ich mehrfach ausprobiert habe.

Soll heißen, du bekommst alle 2^31 - 1 verschiedene Werte, oder 2^32?

> Den
> Zähler als Int64 auf 2^32 setzen, Q, P und R als Int32 (Uint32 bietet
> mein Compiler nicht an), dann M=0x7ffffff, alle Ergebnisse in mehrere
> Dateien auf Platte schreiben, dann alles per MergeSort in eine
> sortierte Datei und diese schichtweg seqenziell auf fehlende Werte und
> Duplikate überprüfen. Es gab keine fehlenden Werte und keine Duplikate

> in mehreren Testläufen mit unteschiedlichen Werten für Q, P und R..

Stop, du hast 2^32 verschiedene Werte im Bereich [0..2^31-1[?

>> M = 2147483647 passt jedenfalls nicht zur Beschreibung M = 2^n im
>> Algorithmus.
>>
> Wie gesagt, Int32 bietet mir keine andere Möglichkeit. Wähle ich für
> Q, P und R Int64 und setze M=2^32 werden alle Werte von 0 bis 2^32
> berechnet. Kann auch sehr einfach nachgeprüft werden.

Mit einem M, welches keine Zweierpotenz ist (sondern zum Beispiel eins
drunter, wie bei dir), sieht die Analyse des Algorithmus ganz anders aus
als für eine Zweierpotenz.

Probiere mal dein Mini-Beispiel mit M=15 statt M=16, du bekommst eine
deutlich andere Folge. Und natürlich auch keine Gleichverteilung aller
Bits (weil eben die Folge 1111 nicht mehr möglich ist).

Also, wenn du wirklich eine Gleichverteilung willst, nimm eine
Zweierpotenz, welche noch in deinen Zahlentyp hineinpasst (und wo dann
auch nach der Multiplikation das Ergebnis noch passt, je nachdem, wie
das in deiner Programmiersprache implementiert ist). Also etwa 2^30.

Alternativ, lass den mod-Teil weg und rechne direkt in int32. In Java
etwa ist int ein Typ, der automatisch modulo 2^32 rechnet (das spielt ja
nur bei der Multiplikation eine Rolle). (Du musst nur bei der Ausgabe
bzw. Extraktion der Bits aufpassen.)

Da du nicht sagst, in welcher Sprache du arbeitest, kann ich nicht
sagen, ob das da auch so funktioniert, aber das kann man ja nachlesen.

> Außerdem ist es doch wohl so, dass der Algorithmus, wenn er alle Werte
> bei kleinem Modulo 2^n errechnet, dies auch bei größerem Modulo, z.B.
> 2^32 oder 2^64 tun wird.

Hmm, wahrscheinlich.

> Das Verhältnis der Werte in der Formel
> verändert sich ja nicht durch einen größeren Modulo, oder?

Wie gesagt, dein 2^31-1 ist kein 2^n.

>>> Aus meiner Sicht ist Q nur ein Art "Träger", aus dem die benötigten
>>> Informationen extrahiert werden. Wenn also Byte benötigt werden, dann
>>> greift folgende Formel
>>
>>> Byte = Q >> 23 and 0xff
>>
>> Okay, du ignorierst also die unteren Bits und extrahierst 8 Bit aus dem
>> oberen Ende.
>
> Ja, so seht es auch auf der Webseite bei den Testergebnissen, auch
> wenn die Formel etwas anders geschrieben ist. Momentan favorisiere
> ich
> Byte = Q >> 24 , weil es eine weitere Rechenoperation erspart.

Aufpassen: Wenn du modulo 2^31-1 rechnest, ist das oberste Bit immer
Null, und alle anderen mit einer ganz kleinen Wahrscheinlichkeit
häufiger 0 als 1 (weil die "alles 1"-Folge nicht vorkommen kann). Es
kann natürlich sein, dass das durch Überläufe und signed-int-Verwendung
(also Bugs in der Implementierung) überdeckt wird.

>> Das solltest du unbedingt mit in die Beschreibung des Algorithmus
>> hineinschreiben.
> Das ist aber dann eine Einschränkung des Algorithmus, denn wie die
> Werte von Q letztlich gehandhabt werden hängt doch von dem jeweiligen
> Verwendungszweck ab. Bei Spielen werden sehr häufig nur Nullen und
> Einsen benötigt, also berechne ich Byte = Q >> 30 & 0x1, bei anderen
> Anwendungen werden Hex-Byte benötigt, dann gibt Byte = Q >> 24, bei
> anderer Anwendung werden wieder andere Werte benötigt, die auf andere
> Art aus Q gewonnen werden können. Da dies aber im Vorfeld unklar ist,
> kann ich den Algorithmus nicht auf die eine oder andere Art festlegen.

Die Tatsache ist, dass bestimmte Bits der Q-Folge unterschiedlich
"zufällig" sind. Wenn du etwa nur das letzte Bit (2^0) in unserer
Beispiel-Folge betrachten, ist das 10101010.... Das vorletzte Bit (2^1)
hat die Folge 1100110011...

Mit größeren n und Extraktion der höheren Bits statt der niedrigen
sollte das besser aussehen.

>> (So kommt natürlich das "abwechselnd gerade und
>> ungerade" nicht mehr zum Tragen, und auch die Analyse, die ich oben für
>> n = 3 gemacht habe, geht nicht mehr ganz so einfach.)
>>
> Es wäre schon interessant zu erfahren, ob und wie einfach man nur aus
> der erzeugten Bytefolge auf die Werte für Q, P und R schließen kann.
> Aber selbst wenn ich Dir nun 32 aufeinanderfolgende Werte von Q
> benenne, denke ich, wird es Dir nicht so einfach fallen auf P und R zu
> schließen, oder irre ich mich hier?

Ich denke, aus einem Abschnitt der Q-Folge selbst kann man recht gut auf
P und Q schließen - ich kann aber auf Anhieb nicht sagen, wie viele
Elemente man braucht. (Und das wird auch mod 2^n anders sein als mod 2^n
- 1.)

Aber das sehe ich mir nicht jetzt an, vielleicht morgen, spätestens
nächstes Wochenende.


Paul

[Karl-Uwe Frank]

Paul Ebermann wrote:
> Karl-Uwe Frank skribis:
>> On Nov 6, 7:48 pm, Paul Ebermann <Paul-Eberm...@gmx.de> wrote:
>>> Karl-Uwe Frank skribis:
>>>> On Nov 5, 3:49 pm, Paul Ebermann <Paul-Eberm...@gmx.de> wrote:

[snip]

>>
>> Wie gesagt, bei signed Int32 kann ich keiner Variable 2^32
>> zuordnen, daher 2^31-1. Trotzdem werden alle Integer jeweils einmal
>> in einer vollen Periode errechnet, was ich mehrfach ausprobiert
>> habe.
>
> Soll heißen, du bekommst alle 2^31 - 1 verschiedene Werte, oder
> 2^32?
>

Wenn ich die Null mit zähle und mich nur auf die positiven Werte
beschränke, erhalte ich z.B. bei 2^15-1 alle 32.768 Zahlenwerte als
Ergebnis. Ich wähle einfach einmal den 16-Bit Adressbereich, da sich
die Ergebnisse recht gut überschauen lassen.

>> Den Zähler als Int64 auf 2^32 setzen, Q, P und R als Int32 (Uint32
>> bietet mein Compiler nicht an), dann M=0x7ffffff, alle Ergebnisse
>> in mehrere Dateien auf Platte schreiben, dann alles per MergeSort
>> in eine sortierte Datei und diese schichtweg seqenziell auf
>> fehlende Werte und Duplikate überprüfen. Es gab keine fehlenden
>> Werte und keine Duplikate in mehreren Testläufen mit
>> unteschiedlichen Werten für Q, P und R..
>
> Stop, du hast 2^32 verschiedene Werte im Bereich [0..2^31-1[?
>
>>> M = 2147483647 passt jedenfalls nicht zur Beschreibung M = 2^n
>>> im Algorithmus.
>>>
>> Wie gesagt, Int32 bietet mir keine andere Möglichkeit. Wähle ich
>> für Q, P und R Int64 und setze M=2^32 werden alle Werte von 0 bis
>> 2^32 berechnet. Kann auch sehr einfach nachgeprüft werden.
>
> Mit einem M, welches keine Zweierpotenz ist (sondern zum Beispiel
> eins drunter, wie bei dir), sieht die Analyse des Algorithmus ganz
> anders aus als für eine Zweierpotenz.
>

Was noch zu eruieren wäre.

> Probiere mal dein Mini-Beispiel mit M=15 statt M=16, du bekommst
> eine deutlich andere Folge. Und natürlich auch keine Gleichverteilung
> aller Bits (weil eben die Folge 1111 nicht mehr möglich ist).

Modulo die nicht 2^n sind erzeugen unvollständige Ergebnisse, bezogen
auf die volle Period von n, zusammen mit viel zu kurzen
Periodenlängen, was ja nicht gewünscht ist.

> Also, wenn du wirklich eine Gleichverteilung willst, nimm eine
> Zweierpotenz, welche noch in deinen Zahlentyp hineinpasst (und wo
> dann auch nach der Multiplikation das Ergebnis noch passt, je
> nachdem, wie das in deiner Programmiersprache implementiert ist).
> Also etwa 2^30.
>
> Alternativ, lass den mod-Teil weg und rechne direkt in int32. In
> Java etwa ist int ein Typ, der automatisch modulo 2^32 rechnet (das
> spielt ja nur bei der Multiplikation eine Rolle). (Du musst nur bei
> der Ausgabe bzw. Extraktion der Bits aufpassen.)
>

Gut das Du dies ansprichst, denn es hatte mich nahezu in die
Verzweiflung betrieben, dass mit höherem Modulo plötzlich Zahlenwerte
in der Abfolge fehlten. Die Ergebnisse fielen in den negativen Bereich
und es wurden dafür Werte übersprungen. Zuerst hatte ich meine Formel
immer mit niedrigen Modulo zwischen 2^4 und 2^9 in JavaScript
getestet. Dort lagen die Ergebnisse gut sichtbar und immer vollständig
im positiven Bereich. Als ich es dann in einer anderen
Programmierumgebung mit Int16 und Int32 getestet habe traten besagte
Diskrepanzen auf. Also habe ich mich zunächst einmal auf Int16
beschränkt (UInt16 wird nicht angeboten) und versucht nur im positiven
Int16 Zahlenraum zu bleiben. Dabei trat zutage, dass ich die Formel
ohne Modulo-Berechnung ausführen muss, allerdings an ihre Stelle ein
"add 0xffff" zu setzen ist. Nun wurden alle positiven Werte von 0 bis
32.768 erzeugt, wenn M=0x7fff ist. Der nächste Versuch war dann auch
noch das "add 0xffff" aus der Formel zu streichen und nun wurden alle
Werte von -32.768 bis 32.767 (inkl. 0) erzeugt. Wieso das so ist kann
ich nicht sagen, akzeptiere aber das Ergebnis :-)

> Da du nicht sagst, in welcher Sprache du arbeitest, kann ich nicht
> sagen, ob das da auch so funktioniert, aber das kann man ja
> nachlesen.
>

Ich verwende momentan PureBasic, weil es Ressourcenschonende, sehr
schnelle, extrem kompakte Executables in Maschinencode erzeugt und
außerdem Plattformübergreifend ist, also für MacOSX, Linux und Windows
der gleiche SourceCode verwendet werden kann, dies erleichtert die
Tests erheblich.

>> Außerdem ist es doch wohl so, dass der Algorithmus, wenn er alle
>> Werte bei kleinem Modulo 2^n errechnet, dies auch bei größerem
>> Modulo, z.B. 2^32 oder 2^64 tun wird.
>
> Hmm, wahrscheinlich.
>
>> Das Verhältnis der Werte in der Formel verändert sich ja nicht
>> durch einen größeren Modulo, oder?
>
> Wie gesagt, dein 2^31-1 ist kein 2^n.
>

Siehe die Passage darüber (mod-Teil)

>>>> Aus meiner Sicht ist Q nur ein Art "Träger", aus dem die
>>>> benötigten Informationen extrahiert werden. Wenn also Byte
>>>> benötigt werden, dann greift folgende Formel
>>>
>>>> Byte = Q >> 23 and 0xff
>>>
>>> Okay, du ignorierst also die unteren Bits und extrahierst 8 Bit
>>> aus dem oberen Ende.
>>
>> Ja, so seht es auch auf der Webseite bei den Testergebnissen, auch
>> wenn die Formel etwas anders geschrieben ist. Momentan favorisiere
>> ich Byte = Q >> 24 , weil es eine weitere Rechenoperation erspart.
>
> Aufpassen: Wenn du modulo 2^31-1 rechnest, ist das oberste Bit immer
> Null, und alle anderen mit einer ganz kleinen Wahrscheinlichkeit
> häufiger 0 als 1 (weil die "alles 1"-Folge nicht vorkommen kann). Es
> kann natürlich sein, dass das durch Überläufe und
> signed-int-Verwendung (also Bugs in der Implementierung) überdeckt
> wird.
>

Vielen Dank für diesen Hinweis, ich werde mir es darauf hin einmal
näher absehen.

>>> Das solltest du unbedingt mit in die Beschreibung des
>>> Algorithmus hineinschreiben.
>> Das ist aber dann eine Einschränkung des Algorithmus, denn wie die
>> Werte von Q letztlich gehandhabt werden hängt doch von dem
>> jeweiligen Verwendungszweck ab. Bei Spielen werden sehr häufig nur
>> Nullen und Einsen benötigt, also berechne ich Byte = Q >> 30 & 0x1,
>> bei anderen Anwendungen werden Hex-Byte benötigt, dann gibt Byte =
>> Q >> 24, bei anderer Anwendung werden wieder andere Werte benötigt,
>> die auf andere Art aus Q gewonnen werden können. Da dies aber im
>> Vorfeld unklar ist, kann ich den Algorithmus nicht auf die eine
>> oder andere Art festlegen.
>
> Die Tatsache ist, dass bestimmte Bits der Q-Folge unterschiedlich
> "zufällig" sind. Wenn du etwa nur das letzte Bit (2^0) in unserer
> Beispiel-Folge betrachten, ist das 10101010.... Das vorletzte Bit
> (2^1) hat die Folge 1100110011...
>
> Mit größeren n und Extraktion der höheren Bits statt der niedrigen
> sollte das besser aussehen.
>

Was ich mir ebenfalls noch einmal genauer ansehen werde. Bisher habe
ich die Bit-Ebene nicht beachtet, sondern mein Augenmerk auf die
vollständige Erzeugung aller Integer in der Periode 2^n konzentriert
ohne in einen Bias zu geraten. Sicherlich bietet die Formel noch
einige Verbesserungsmöglichkeiten. An einer Erweiterung arbeite ich
bereits. Eventuell wird ja damit das Spektrum der "Zufälligkeit"
weiter erhöht.

>>> (So kommt natürlich das "abwechselnd gerade und ungerade" nicht
>>> mehr zum Tragen, und auch die Analyse, die ich oben für n = 3
>>> gemacht habe, geht nicht mehr ganz so einfach.)
>>>
>> Es wäre schon interessant zu erfahren, ob und wie einfach man nur
>> aus der erzeugten Bytefolge auf die Werte für Q, P und R schließen
>> kann. Aber selbst wenn ich Dir nun 32 aufeinanderfolgende Werte von
>> Q benenne, denke ich, wird es Dir nicht so einfach fallen auf P und
>> R zu schließen, oder irre ich mich hier?
>
> Ich denke, aus einem Abschnitt der Q-Folge selbst kann man recht gut
> auf P und Q schließen - ich kann aber auf Anhieb nicht sagen, wie
> viele Elemente man braucht. (Und das wird auch mod 2^n anders sein
> als mod 2^n - 1.)
>
> Aber das sehe ich mir nicht jetzt an, vielleicht morgen, spätestens
> nächstes Wochenende.

Vielen Dank schon einmal für deine guten Tips und mal sehen ob sich
die Sequenz so einfach "entschlüsseln" läßt, selbst bei 2^n-1.

Einen guten Start in die Woche und Cheers,
Karl-Uwe

[Karl-Uwe Frank]

On 07.11.11 03:17, Richard W. Könning wrote:
> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>
>> Richard W. Könning wrote:
>>> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>>>
>>> Das Teil hat doch arge ?hnlichkeit zu linearen Kongruenzgeneratoren
>>> (die als gebrochen gelten). Hierzu empfehle ich die Lekt?re von
>>> http://www.rfc-editor.org/rfc/rfc1750.txt, p. 6 ff. Dort wird f?r
>>> allgemeinere Kongruenzgeneratoren auf "How to Predict Congruential
>>> Generators, Journal of Algorithms, V. 13, N. 4, December 1992, H.
>>> Krawczyk" verwiesen.
>
>> Vielen Dank für diese Information. Und ja, hat eine gewisse
>> Ähnlichkeit zu linearen Kongruenzgeneratoren ist vorhanden. Allerdings
>> unterscheidet sich mein Algorithmus in Bezug auf die Möglichkeit ihn
>> mit 2 zufällig ausgewählten Zahlenwerten für P und R zu versorgen,
>> ohne das er in einen Bias gerät oder nicht die volle Periodenlänge von
>> M erreicht. Bei linearen Kongruenzgeneratoren müssen die Konstanten
>> sorgfältig ausgewählt werden um dies zu erreichen. Außerdem sind es ja
>
> Die Statistik ist nicht das kryptographische Problem bei den linearen
> Kongruenzgeneratoren.

Dem stimme ich zu, denn ihr Problem liegt wohl eher in ihrem stark
deterministischen Verhalten.

>> Konstanten und keine Variablen. Natürlich ist es gut vorstellbar, dass
>> ein solcher simpler Algorithmus, wie ich ihn hier vorgestellt habe,
>> sehr leicht gebrochen werden kann, also eine Abwandlung der im Artikel
>> beschriebenen Vorgehensweise auch bei meiner Formel zu besagtem Ziel
>> führen wird. Betrachtet werden sollte mein Algorithmus deshalb eher
>> als Ausgangspunkt für eine "verstärkte" Version, die solchen Angriffen
>> widerstehen wird. Eine entsprechende Weiterentwicklung habe ich
>> bereits begonnen.
>
> Ich verstehe nicht so recht, warum Du diesen Weg gehen willst. Es gibt
> bessere Entwürfe für PRNG, die nicht schon von Anfang mit
> grundlegenden Problemen zu kämpfen haben.

Nun ist es ja so das man sich fragen müßte, warum es ständig neue
Kochrezepte erdacht werden, wo doch Paul Bocuse schon aller guten
Kombinationen erdacht hat. Aber so ist das wohl im Leben - öfter mal
was Neues. ;-)

Zumindest wird mein PRNG in anderen Bereichen als die Kryptographie
von Nutzen sein, denn ganz so schlecht ist er ja nicht - und zu
erwähnen sei noch, dass ich ja gerade erst am Anfang stehe, wer weiß
was mir noch so alles in den Sinn kommt.

Cheers,
Karl-Uwe

[Richard W. Könning]

Karl-Uwe Frank <karl....@freecx.co.uk> wrote:

>On 07.11.11 03:17, Richard W. Könning wrote:
>> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>>
>>> Vielen Dank für diese Information. Und ja, hat eine gewisse
>>> Ähnlichkeit zu linearen Kongruenzgeneratoren ist vorhanden. Allerdings
>>> unterscheidet sich mein Algorithmus in Bezug auf die Möglichkeit ihn
>>> mit 2 zufällig ausgewählten Zahlenwerten für P und R zu versorgen,
>>> ohne das er in einen Bias gerät oder nicht die volle Periodenlänge von
>>> M erreicht. Bei linearen Kongruenzgeneratoren müssen die Konstanten
>>> sorgfältig ausgewählt werden um dies zu erreichen. Außerdem sind es ja
>>
>> Die Statistik ist nicht das kryptographische Problem bei den linearen
>> Kongruenzgeneratoren.
>
>Dem stimme ich zu, denn ihr Problem liegt wohl eher in ihrem stark
>deterministischen Verhalten.

Auch das ist nicht das Problem. So gut wie jeder PRNG ist
deterministisch. Zufall kommt nur durch Seeden mit entropiebehafteten
Daten rein. Das Problem ist die vergleichsweise Vorhersagbarkeit der
zukünftig produzierten Daten, wenn man auch nur Teile der
schonproduzierten kennt.

>> Ich verstehe nicht so recht, warum Du diesen Weg gehen willst. Es gibt
>> bessere Entwürfe für PRNG, die nicht schon von Anfang mit
>> grundlegenden Problemen zu kämpfen haben.
>
>Nun ist es ja so das man sich fragen müßte, warum es ständig neue
>Kochrezepte erdacht werden, wo doch Paul Bocuse schon aller guten
>Kombinationen erdacht hat. Aber so ist das wohl im Leben - öfter mal
>was Neues. ;-)

In der Kryptographie sieht man es eher andersrum. Wenn es keine
triftigen Gründe für etwas Neues gibt, dann bleibt man beim
Altbewährten.

[Karl-Uwe Frank]

On 07.11.11 23:15, Richard W. Könning wrote:
> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>
>> On 07.11.11 03:17, Richard W. Könning wrote:
>>> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>>>
>>>> Vielen Dank für diese Information. Und ja, hat eine gewisse
>>>> Ähnlichkeit zu linearen Kongruenzgeneratoren ist vorhanden. Allerdings
>>>> unterscheidet sich mein Algorithmus in Bezug auf die Möglichkeit ihn
>>>> mit 2 zufällig ausgewählten Zahlenwerten für P und R zu versorgen,
>>>> ohne das er in einen Bias gerät oder nicht die volle Periodenlänge von
>>>> M erreicht. Bei linearen Kongruenzgeneratoren müssen die Konstanten
>>>> sorgfältig ausgewählt werden um dies zu erreichen. Außerdem sind es ja
>>>
>>> Die Statistik ist nicht das kryptographische Problem bei den linearen
>>> Kongruenzgeneratoren.
>>
>> Dem stimme ich zu, denn ihr Problem liegt wohl eher in ihrem stark
>> deterministischen Verhalten.
>
> Auch das ist nicht das Problem. So gut wie jeder PRNG ist
> deterministisch. Zufall kommt nur durch Seeden mit entropiebehafteten
> Daten rein. Das Problem ist die vergleichsweise Vorhersagbarkeit der
> zukünftig produzierten Daten, wenn man auch nur Teile der
> schonproduzierten kennt.
>

Bei einem deterministischen PRNG, also klassischem LCG oder auch bei
meinem, nützt aus meiner Sicht selbst das Seeden mit entropiebehafteten
Daten nichts, denn das Seed bestimmt ja nur den "Einstiegspunkt" in die
Zahlensequenz die der PRNG erzeugt. Ich betrachte das immer als eine Art
"Zahlenstrahl", dessen Abfolge von 0 bis Periodenlänge durch die
Konstanten definiert wird. Dies ist bei einem klassischen LCG immer ein
einzelner, gleicher "Zahlenstrahl", dessen Ausgabe der
"Zufallsergebnisse" sich eben nur über die Stelle definiert, an der ich
mit meinem Seed "einsteige". Bei meinem PRNG sind es, bedingt durch die
Möglichkeit außer dem Seed auch die anderen Berechnungswerte frei zu
wählen, zumindest 2^(2n-6) "Zahlenstrahlen" bei denen das Seed den Punkt
des "Einstiegs" definiert. Wie einfach es ist aus einer gegebenen
Zahlenfolge die komplette Sequenz zu errechnen, also P und R wird sich
sicherlich noch herausstellen, denn letztlich hat auch mein PRNG
festgelegte "Zahlenstrahlen" die sich immer gleich von 0 bis 2^n
ausdehnen, bedingt durch die maximal möglichen Werte von P und R in M.

>>> Ich verstehe nicht so recht, warum Du diesen Weg gehen willst. Es gibt
>>> bessere Entwürfe für PRNG, die nicht schon von Anfang mit
>>> grundlegenden Problemen zu kämpfen haben.
>>
>> Nun ist es ja so das man sich fragen müßte, warum es ständig neue
>> Kochrezepte erdacht werden, wo doch Paul Bocuse schon aller guten
>> Kombinationen erdacht hat. Aber so ist das wohl im Leben - öfter mal
>> was Neues. ;-)
>
> In der Kryptographie sieht man es eher andersrum. Wenn es keine
> triftigen Gründe für etwas Neues gibt, dann bleibt man beim
> Altbewährten.

Natürlich ist das legitim und richtig. Trotzdem denke ich, dass es einen
Versuch wert ist sich weiterhin mit neuen Entwicklungen und Ideen
diesbezüglich zu befassen, eventuell wird am Ende ja tatsächlich ein
weiterer brauchbarer CSPRNG stehen.

--
Cheers,
Karl-Uwe

[Karl-Uwe Frank]

On 07.11.11 03:34, Paul Ebermann wrote:
> Karl-Uwe Frank skribis:
>> On Nov 6, 7:48 pm, Paul Ebermann<Paul-Eberm...@gmx.de> wrote:
>>> Karl-Uwe Frank skribis:
>>>> On Nov 5, 3:49 pm, Paul Ebermann<Paul-Eberm...@gmx.de> wrote:
>
>>>>>> Das Ergebnis von pqRNG in 32bit Binärwerten im Integer Interval [0,
>>>>>> 255] mit M = 2147483647
>>>
>>>>> Huh. Dieses M ist als ungerade Zahl sicher keine Zweierpotenz (das ist
>>>>> 2^31-1, wenn ich das richtig sehe), und das Intervall [0, 255] ist auch
>>>>> nicht groß genug für 32-bit Zahlen. Was genau hast du da getestet?
>>>
>>>> Dieses M ist zwangsläufig eine ungerade Zahl, wenn mit signed Int32
>>>> gerechnet wird.
>>>
>>> Einfaches Rechnen mit 32-Bit Integer Werten (mit Abschneiden von
>>> Übertrag-Bits) ist nicht das gleiche wie Rechnen modulo 2147483647,
>>> sondern modulo 2^32.
>>>
>>> Ich habe keine Ahnung, was du da wirklich implementiert und getestet hast..

Ich habe nun hier einen Sourcecode hinterlegt, mit dem alle 16-Bit
Integer berechnet und gegengeprüft werden können. Ebenfalls zwei
Textdateien mit Beispielergebnissen, einmal mit Modulo 32767 und dann
mit Modulo 65535. Es fehlt kein Wert und es ist auch keiner doppelt
vorhanden.

http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_32767_full_period.txt
http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_65535_full_period.txt
http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_full_cycle_2**16_test.pb

Das Listing ist letztlich auch nur ein einfaches Textfile mit der Endung
*.pb. Um es zu complieren kannst Du die Demo von PureBasic verwenden, zu
finden hier http://www.purebasic.com/german/index.php

Cheers,
Karl-Uwe

[Richard W. Könning]

Karl-Uwe Frank <karl....@freecx.co.uk> wrote:

>On 07.11.11 23:15, Richard W. Könning wrote:
>> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>>
>>> Dem stimme ich zu, denn ihr Problem liegt wohl eher in ihrem stark
>>> deterministischen Verhalten.
>>
>> Auch das ist nicht das Problem. So gut wie jeder PRNG ist
>> deterministisch. Zufall kommt nur durch Seeden mit entropiebehafteten
>> Daten rein. Das Problem ist die vergleichsweise Vorhersagbarkeit der
>> zukünftig produzierten Daten, wenn man auch nur Teile der
>> schonproduzierten kennt.
>>
>Bei einem deterministischen PRNG, also klassischem LCG oder auch bei
>meinem, nützt aus meiner Sicht selbst das Seeden mit entropiebehafteten
>Daten nichts, denn das Seed bestimmt ja nur den "Einstiegspunkt" in die
>Zahlensequenz die der PRNG erzeugt. Ich betrachte das immer als eine Art

Das ist auch bei kryptographisch starken PRNG nicht anders. Das
Problem beim (naiv verwendeten) Kongruenzgenerator ist, daß der
vollständige Zustand des PRNG entnommen wird. Man kann das natürlich
verbessern, indem man nicht die komplette Bitfolge der jeweiligen Zahl
verwendet, aber laut RFC 1750 ist selbst bei Entnahme von nur einem
Bit ein Rückschluß auf den Seed-Wert möglich, und das ist der
eigentliche Todesstoß.

>"Zahlenstrahl", dessen Abfolge von 0 bis Periodenlänge durch die
>Konstanten definiert wird. Dies ist bei einem klassischen LCG immer ein
>einzelner, gleicher "Zahlenstrahl", dessen Ausgabe der
>"Zufallsergebnisse" sich eben nur über die Stelle definiert, an der ich
>mit meinem Seed "einsteige". Bei meinem PRNG sind es, bedingt durch die
>Möglichkeit außer dem Seed auch die anderen Berechnungswerte frei zu
>wählen, zumindest 2^(2n-6) "Zahlenstrahlen" bei denen das Seed den Punkt
>des "Einstiegs" definiert. Wie einfach es ist aus einer gegebenen
>Zahlenfolge die komplette Sequenz zu errechnen, also P und R wird sich
>sicherlich noch herausstellen, denn letztlich hat auch mein PRNG
>festgelegte "Zahlenstrahlen" die sich immer gleich von 0 bis 2^n
>ausdehnen, bedingt durch die maximal möglichen Werte von P und R in M.
>

>> In der Kryptographie sieht man es eher andersrum. Wenn es keine
>> triftigen Gründe für etwas Neues gibt, dann bleibt man beim
>> Altbewährten.
>Natürlich ist das legitim und richtig. Trotzdem denke ich, dass es einen
>Versuch wert ist sich weiterhin mit neuen Entwicklungen und Ideen
>diesbezüglich zu befassen, eventuell wird am Ende ja tatsächlich ein
>weiterer brauchbarer CSPRNG stehen.

Wenn schon eine ganze Klasse von PRNG grundlegende Probleme hat, dann
sehe ich wenig Nutzen darin, in dieser Klasse weiterzusuchen.
Insbesondere wenn es PRNG gibt, die von den Konstruktionsprinzipien
her schon mal deutlich besser sind.

Eine gute Hash-Funktion ist das, was der Kryptographie im Augenblick
am ehesten fehlt, die kann man dann auch bei der PRNG-Konstruktion
verwenden.

[Karl-Uwe Frank]

On 08.11.11 04:24, Richard W. Könning wrote:
> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>
>> On 07.11.11 23:15, Richard W. Könning wrote:
>>> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>>>
>>>> Dem stimme ich zu, denn ihr Problem liegt wohl eher in ihrem stark
>>>> deterministischen Verhalten.
>>>
>>> Auch das ist nicht das Problem. So gut wie jeder PRNG ist
>>> deterministisch. Zufall kommt nur durch Seeden mit entropiebehafteten
>>> Daten rein. Das Problem ist die vergleichsweise Vorhersagbarkeit der
>>> zukünftig produzierten Daten, wenn man auch nur Teile der
>>> schonproduzierten kennt.
>>>
>> Bei einem deterministischen PRNG, also klassischem LCG oder auch bei
>> meinem, nützt aus meiner Sicht selbst das Seeden mit entropiebehafteten
>> Daten nichts, denn das Seed bestimmt ja nur den "Einstiegspunkt" in die
>> Zahlensequenz die der PRNG erzeugt. Ich betrachte das immer als eine Art
>
> Das ist auch bei kryptographisch starken PRNG nicht anders. Das
> Problem beim (naiv verwendeten) Kongruenzgenerator ist, daß der
> vollständige Zustand des PRNG entnommen wird. Man kann das natürlich
> verbessern, indem man nicht die komplette Bitfolge der jeweiligen Zahl
> verwendet, aber laut RFC 1750 ist selbst bei Entnahme von nur einem
> Bit ein Rückschluß auf den Seed-Wert möglich, und das ist der
> eigentliche Todesstoß.
>

Es ist essentiell nicht die komplette Bitfolge zu verwenden, sondern nur
jeweils ein Byte aus Q (respektive V) zu ziehen, um etwas zu erschweren
auf die komplette Sequenz zu schließen.

Im genannten Dokument wird es, meines Erachtens, ebenfalls
hervorgehoben, dass eine Aufschlüsselung der gesamten Sequenz nur dann
gelingt, wenn mindestens ein Bit aus einem kompletten Wert von V(n)
bekannt ist.

"For example, with the generators above, one can determine V(n+1) given
knowledge of V(n). In fact, it has been shown that with these
techniques, even if only one bit of the pseudo-random values is
released, the seed can be determined from short sequences."

Sicherlich mag es Bedarf für eine solche Hash-Funktion geben. Aber ist
es denn nicht so, dass bereits mit einer der vorhandenen Hash-Funktionen
in Kombination mit einem soliden PRNG ein guter CSPRNG erstellt werden kann?

Cheers,
Karl-Uwe

[Karl-Uwe Frank]

Soeben habe ich noch eine weitere Datei mit Testresultaten im Bereich
signed Int16 (-32768 bis +32767) hinterlegt sowie den passenden
Sourcecode dazu

http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_32767*2+1_full_period.txt

http://www.freecx.co.uk/pqRNG/test_sources/pqRNG_full_cycle_2**15-1_test.pb

#############

[Richard W. Könning]

Karl-Uwe Frank <karl....@freecx.co.uk> wrote:

>On 08.11.11 04:24, Richard W. Könning wrote:
>> Karl-Uwe Frank<karl....@freecx.co.uk> wrote:
>>
>> Das ist auch bei kryptographisch starken PRNG nicht anders. Das
>> Problem beim (naiv verwendeten) Kongruenzgenerator ist, daß der
>> vollständige Zustand des PRNG entnommen wird. Man kann das natürlich
>> verbessern, indem man nicht die komplette Bitfolge der jeweiligen Zahl
>> verwendet, aber laut RFC 1750 ist selbst bei Entnahme von nur einem
>> Bit ein Rückschluß auf den Seed-Wert möglich, und das ist der
>> eigentliche Todesstoß.
>>
>Es ist essentiell nicht die komplette Bitfolge zu verwenden, sondern nur
>jeweils ein Byte aus Q (respektive V) zu ziehen, um etwas zu erschweren
>auf die komplette Sequenz zu schließen.
>
>Im genannten Dokument wird es, meines Erachtens, ebenfalls
>hervorgehoben, dass eine Aufschlüsselung der gesamten Sequenz nur dann
>gelingt, wenn mindestens ein Bit aus einem kompletten Wert von V(n)
>bekannt ist.
>
>"For example, with the generators above, one can determine V(n+1) given
>knowledge of V(n). In fact, it has been shown that with these
>techniques, even if only one bit of the pseudo-random values is
>released, the seed can be determined from short sequences."

Wenn man jeden V(n)-Wert verwertet, dann kann man nicht weniger als
ein Bit verwerten, d.h. "even if only one bit..." heißt, daß selbst
diese Mindestentnahme-Menge ausreicht, den Seed zu bestimmen. Man kann
sich natürlich anschauen, was passiert, wenn man nur ein Bit von jedem
zweiten oder dritten V(n)-Wert verwertet, aber auch da bin ich
skeptisch. Wenn ein Verfahren schon so schnell Schwächen zeigt, dann
ist zu erwarten, daß durch kleine Änderungen keine wesentliche
Verbesserung erreicht wird. Ich betrachte Kongruenzgeneratoren als
untauglich für den Bau von kryptographisch starken PRNG.

>> Wenn schon eine ganze Klasse von PRNG grundlegende Probleme hat, dann
>> sehe ich wenig Nutzen darin, in dieser Klasse weiterzusuchen.
>> Insbesondere wenn es PRNG gibt, die von den Konstruktionsprinzipien
>> her schon mal deutlich besser sind.
>>
>> Eine gute Hash-Funktion ist das, was der Kryptographie im Augenblick
>> am ehesten fehlt, die kann man dann auch bei der PRNG-Konstruktion
>> verwenden.
>Sicherlich mag es Bedarf für eine solche Hash-Funktion geben. Aber ist
>es denn nicht so, dass bereits mit einer der vorhandenen Hash-Funktionen
>in Kombination mit einem soliden PRNG ein guter CSPRNG erstellt werden kann?

Die Hash-Funktion wird nicht mit einem PRNG kombiniert, sondern ein
PRNG wird auf der Basis eines Entropie-Pools gebaut, der mit Hilfe
dieser Hash-Funktion durchmischt wird. Die Entnahme von Zufallszahlen
erfolgt auch mit Hilfe der Hash-Funktion. Ausgenutzt wird, daß bei
einer guten Hash-Funktion der Hash-Wert keine Rückschlüsse auf die
gehashten Daten erlaubt und die Änderung eines einzelnen Input-Bits
ausreicht, um große Änderungen im Hash-Wert zu bewirken.

[Karl-Uwe Frank]

Was noch zu beweisen wäre. Mein nächster Algorithmus basierend auf pqRNG
steht kurz vor der Veröffentlichung, eine möglicherweise kryptographisch
sichere Variante ist ebenfalls bereits in Arbeit.

>>> Wenn schon eine ganze Klasse von PRNG grundlegende Probleme hat, dann
>>> sehe ich wenig Nutzen darin, in dieser Klasse weiterzusuchen.
>>> Insbesondere wenn es PRNG gibt, die von den Konstruktionsprinzipien
>>> her schon mal deutlich besser sind.
>>>
>>> Eine gute Hash-Funktion ist das, was der Kryptographie im Augenblick
>>> am ehesten fehlt, die kann man dann auch bei der PRNG-Konstruktion
>>> verwenden.
>> Sicherlich mag es Bedarf für eine solche Hash-Funktion geben. Aber ist
>> es denn nicht so, dass bereits mit einer der vorhandenen Hash-Funktionen
>> in Kombination mit einem soliden PRNG ein guter CSPRNG erstellt werden kann?
>
> Die Hash-Funktion wird nicht mit einem PRNG kombiniert, sondern ein
> PRNG wird auf der Basis eines Entropie-Pools gebaut, der mit Hilfe
> dieser Hash-Funktion durchmischt wird. Die Entnahme von Zufallszahlen
> erfolgt auch mit Hilfe der Hash-Funktion. Ausgenutzt wird, daß bei
> einer guten Hash-Funktion der Hash-Wert keine Rückschlüsse auf die
> gehashten Daten erlaubt und die Änderung eines einzelnen Input-Bits
> ausreicht, um große Änderungen im Hash-Wert zu bewirken.

Das ist sehr aufschluß- und hilfreich. Sehe ich es richtig, dass der
PRNG Zufallswerte erzeugt, die anschließend durch die Hash-Funktion
geschoben werden, um die daraus resultierenden, gehashten Bits für die
eigentliche Verschlüsselung zu verwenden?

Cheers,
Karl-Uwe

[Richard W. Könning]

Nein. Es werden entropiebehaftete Daten (also mit einem gewissen
Zufall behaftet) in einen Entropiepool eingebracht (z.B. per
exklusiv-Veroderung). Dieser Entropiepool wird dann mit Hilfe einer
Hashfunktion durchmischt, um die eingebrachte Entropie möglichst über
den ganzen Pool zu verteilen. Die Entnahme von Zufallsdaten erfolgt
wiederum per Hash-Funktion, um Rückschlüsse von den entnommenen Daten
auf den Pool-Inhalt möglichst zu unterbinden. Das ganze Konstrukt
zusammen ist der PRNG, wenn hinreichend viel Entropie eingebracht
wird, dann läßt man das P auch schon mal weg.

[Karl-Uwe Frank]

Dies ist die erweitere Version des Algorithmus von pqRNG mit der
Bezeichnung pqRNGr2

Q[n] = ((Q[n-1] xor R1) + (P * s) + (R2 + (P xor (s-1))) mod M
s = s + 2 + (s * 2^3)

Die volle Periodenlänge aller Integer-Werte zwischen 0 und 2^n ohne

Bias wird erreicht wenn folgende Bedingungen eingehalten werden

P mod 4 = 3
R1 mod 8 = 5 or R1 mod 8 = 7
R2 mod 8 = 5 or R2 mod 8 = 7
s mod 2 = 1
M = 2^n >= 16

Ein Sourcecode ist hinterlegt, mit dem alle 16-Bit Integer berechnet und
die Korrektheit der Formel gegengeprüft werden kann.

(http://freecx.co.uk/pqRNG/#pqRNGr2)

Cheers,
Karl-Uwe