Frequency-Test (Menü Analyse \ Zufallsanalyse)

Beim Aufruf dieses Menüeintrags öffnet sich der Dialog für den Frequency-Test.

Mit diesem statistischen Test wird für eine Bitfolge ein Merkmal der Gleichverteilung überprüft. Der Frequency-Test zählt in der Bitfolge die Anzahl der Nullen n0 und die Anzahl der Einsen n1 und vergleicht das Ergebnis mit dem Verhalten einer unabhängigen gleichverteilten Zufalls-Binärfolge. In der Literatur wird dieser Test auch als "Mono Bit-Test" bezeichnet. Die Teststatistik ist gegeben durch

X1 = (( n0- n1 ) ^ 2) / 2.

Wenn die Zahlen n0 und n1 aus einem zufälligen Intervall einer unabhängigen gleichverteilten Zufalls-Binärfolge stammen, dann ist X1 eine chi^2 – verteilte Zufallsvariable mit einem Freiheitsgrad, sofern n >= 10 (eine Länge von n > 10.000 ist empfohlen). Wenn n0 = n1 ist X1 = 0. Je größer der Wert von X1, desto mehr weichen die beobachteten und erwarteten Häufigkeiten der Nullen und Einsen voneinander ab.

Die Tabelle für die chi^2–Verteilung mit einem Freiheitsgrad liefert für das Signifikanzniveau 0,05 den Wert 3,8415. Das heißt, bei unabhängigen gleichverteilten Zufalls-Binärfolgen ist zu 95 Prozent der beobachtete Wert X1 kleiner als 3,8415.

Wenn der Frequency-Test, mit Parameter alpha = 0,05 ein Wert kleiner als 3,8415 bestimmt, dann hat die Folge den Test bestanden, andernfalls fällt die Folge bei diesem Test durch. Eventuell wird man sich dazu entscheiden, die Sequenz für den Wert X1 = 0 ebenfalls abzulehnen, denn: "Perfekte Werte machen sich verdächtig".

Für den praktischen Test wird eine Länge n größer als 10000 Bits empfohlen.

Es genügt nicht, den Frequency-Test nur einmal auf eine Teilfolge des Generators anzuwenden, da beispielsweise bei einem Signifikanzniveau von 0,05 in 5 von 100 Fällen auch ein "guter" Generator den Test nicht besteht. Daher sollte der Test mehrmals auf unterschiedliche Teilsequenzen angewendet werden, um anschließend die Verteilung der ermittelten Prüfgrößen wieder mit Hilfe einer chi^2-Teststatistik zu überprüfen.

In dem Frequency-Test Dialogfenster kann man Signifikanzniveau, Offset und Testlänge bestimmen.

Ein Frequency-Test Beispiel:

Der Frequency-Test wird an der kurzen 160 Bit-(=20 Bytes-) Binärfolge

s =
00010111 01101101 01111101 11110011 00101111
00001111 10100100 11001111 11000011 11010001
11010001 00101110 11010100 11000011 01010001
11010110 00110010 10001111 00000111 01000111

mit Signifikanzniveau alpha = 0,05 ausgeführt:

Die Anzahl von Nullen bzw. Einsen beträgt n0 = 74 bzw. n1 = 86. Die Teststatistik für

den Frequency-Test bestimmt die Prüfgröße

X1 = ( 74 – 86 ) ^ 2 / 160 = 0,9 .

Der kritische Bereich für X1 liegt bei einer chi^2-Verteilung mit einem Freiheitsgrad und einem Signifikanzniveau von alpha = 0,05 über 3,814.

Mit X1 = 0,9 < 3,814 besteht die Folge den Frequency-Test.


Literatur: Christian Schiestl, Pseudozufallszahlen in der Kryptographie, Klagenfurt, 1999.