Autokorrelationstest (Menü Analyse \ Zufallstests)

Mit diesem statistischen Test wird für eine Bitfolge (Si) [i=1,2, ...] das Merkmal der Unabhängigkeit überprüft. Der Autokorrelationstest bestimmt für die Zahlen k = 1, 2, 3, ... die Korrelation zwischen der zu untersuchenden Bitfolge (Si) und der gleichen um k Bitpositionen verschobenen Bitfolge (S[i+k]).

Die Anzahl der übereinstimmenden Bitpositionen D(k) der Bitfolgen (Si) und (S[i+k]) wird für eine Teilfolge der Länge n durch die Formel bestimmt

D(k) = (S1 XOR S[1 + k]) + .... + (S[n-k+1] XOR Sn).

Die Teststatistik ist gegeben durch

X5 = 2 * [(D(k) – [(n – k) / 2]) / (n – k) ^ (1 / 2)].

Wenn die Folgenlänge n größer als 10 ist, dann ist für eine unabhängige, gleichverteilte Zufalls-Binärfolge die Variable X5 annähernd Standard-normalverteilt. Da sowohl kleine Werte für D(k) wie auch große Werte für D(k) unerwartet sind, ist ein zweiseitiger Test empfehlenswert.

Beispiel für einen Autokorrelationstest:

Der Autokorrelationstest 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:

Wir wählen als Verschiebung k = 8. Hier stimmt die Folge mit der um 8 Positionen verschobenen Kopie der Bitfolge an genau D(8) = 68 Stellen nicht überein. Die Teststatistik für den Autokorrelationstest ergibt somit als Prüfgröße

X5 = 2 * (68 – [(160 – 8) / 2) / (160 – 8) ^ (1 / 2) = -1.29777

Der Grenzwert für eine normalverteilte Prüfgröße X5 liegt bei einem Signifikanzniveau von alpha = 0.05 bei 1.6449.

Mit X5 = - 1.29777 <= 1.6449 besteht die Folge s den Autokorrelationstest.

In CrypTool wird der Autokorrelationstest auf Bytes statt auf Bits abgewandt.

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