Serial-Test (Menü Analyse \ Zufallsanalyse)

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

Dieser Test untersucht, ob Paare aufeinanderfolgender Zahlen gleichverteilt sind und prüft somit deren Unabhängigkeit voneinander.

Bei einer Binärfolge s wird bestimmt, ob die Wahrscheinlichkeit dafür, dass aufeinanderfolgende Elemente der Folge gleich oder unterschiedlich sind, in etwa gleich groß ist. Dies ist ein Indiz dafür, dass jedes Bit unabhängig von seinem Vorgängerbit ist. Bei Binärfolgen gibt es 4 verschiedene Paarungen: 00, 01, 10, 11. Die Anzahl jeder der vier Paarungen (Teilfolgen) in s soll annähernd der bei einer echten Zufallsfolge erwarteten Anzahl entsprechen. Da bei diesem Test stets zwei Bits auf einmal untersucht werden, wird der Test in der Literatur auch als Zwei-Bit-Test bezeichnet.

Seien n0 und n1 die Anzahl der Nullen bzw. der Einsen in s; und seien n00, n01, n10 und n11 die jeweilige Anzahl der Teilsequenzen 00, 01, 10, 11 in s. Da sich die Teilfolgen überlappen dürfen, gilt (mit n = Bitlänge von s):

n00 + n01 + n10 + n11 = n - 1

Die verwendete Teststatistik ist gegeben durch

X2 = [4 / (n –1)] * (n00^2 + n01^2 + n10^2 + n11^2) – (2 / n) * (n0^2 + n1^2) + 1,

wobei X2 annähernd einer chi^2 – Verteilung mit zwei Freiheitsgraden entspricht, vorausgesetzt n >= 21.

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

Ein Serial-Test-Beispiel:

Im folgenden wird an der kurzen Binärfolge

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

mit der Länge n = 160 (20 Byte) der klassische Serial-Test durchgeführt. Das Signifikanzniveau wird mit alpha = 0,05 festgelegt.

Die Anzahl der sich überlappenden Paare 00, 01, 10 und 11 in s beträgt

n00 = 35 n10 = 38
n01 = 39 n11 = 47

Die Prüfgröße für den Zwei-Bit-Test wird ermittelt durch

X2 = [4 / (160 –1)] * (35^2 + 39^2 + 38^2 + 47^2) – (2 / 160) * (74^2 + 86^2) + 1 = 1,081

Der Grenzwert für X2 ist bei einer chi^2 – Verteilung mit zwei Freiheitsgraden und einem Signifikanzniveau von alpha = 0,05 gegeben mit 5,991 .

Mit X2 = 1,081 <= 5,991 besteht die Folge s den Serial-Test.

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