Ein einfacher kombinierter PRNG basiert auf Permutation-Polynomen mod 2**n

17/09/2016 - 23:41 von Mok-Kong Shen | Report spam
Wenn ein Permutation-Polynom mod 2**n als PRNG verwendet wird, sind
bekanntlich die niederwertigen Bits der Sequenz der erhaltenen
Binàrworte statistisch ziemlich schlecht, wogegen die höherwertigen
Bits, für nicht zu kleine Werte von n, sehr befriedigend sind.
Umfangreiche Tests bis zu n%6 zeigen, daß in der Regel nur die
niederen 22 Bits schlecht sind. Dieses empirische Ergebnis steht im
guten Einklang mit einem neulichen rigorosen theoretischen Resultat
von Emil Lerner in seiner PhD Forschungsarbeit, welches zeigt, daß die
höherwertigen Bits von solchen Polynomen sehr gleichmàßig verteilt sind.

Der Grundgedanke des vorliegenden Schemas zur Generierung von pseudo-
zufàlligen Bits besesteht darin, zwei PRNGs basiert auf Permutation-
Polynomen zu verwenden, wobei der Output von dem zweiten PRNG um n/2
Bits rotiert und mit dem Output vom ersten PRNG durch xor kombiniert
wird. Teststatistiken für n2 zeigen, daß dieses Vorgehen richtig
ist, obwohl es dabei noch eine Werte zu finden sind, die außerhalb des
gewünchten Konfidenzsintervalls [7.178, 7.189] liegen, was eine Folge
davon ist, daß für n2 in den Outputs der beiden beteiligten PRNGs
mehr als die Hàlfte der Bits schlecht sind und es daher nicht erwartet
werden kann, daß der große Defekt vollstàndig kompensiert wird. Für
größere Werte von n, z.B. nd, existiert die erwàhnte Ursache der
Schwierigkeit nicht mehr und die Teststatistiken aller Bits des mit xor
kombinierten Outputs sind vollkommen zufriedenstellend.

Implementierung des Schemas ist ganz unkompliziert. Ein Code in Python
befindet sich in: http://s13.zetaboards.com/Crypto/topic/7355166/1/.

M. K. Shen
 

Lesen sie die antworten

#1 Mok-Kong Shen
25/09/2016 - 23:39 | Warnen spam
Eine neue Version 3.1 ist veröffentlicht.

M. K. Shen

Ähnliche fragen