4.2 – Statistische Tests

 

4.2.1 Golombs Kriterien für „Zufall”

Sei {\left\{ {{s_i}} \right\}_{i \geq 0}} eine Bitfolge mit der Periode N, sei n \in \mathbb{N} die Länge eines „runs” (Länge eines Blockes gleicher Bits). {\left\{ {{s_i}} \right\}_{i \geq 0}} ist eine PN (Pseudonoise)-Folge, wenn es die folgenden Kriterien erfüllt:

  1. Innerhalb einer Periode von s unterscheiden sich die Anzahlen von Nullen und Einsen maximal um 1.
  2. Der Anteil der „runs” der Länge n innerhalb einer Periode von s ist mindestens {2^{-n}}. Außerdem gibt es für jede Länge n nahezu gleich viele „blocks” (Reihe von positiven Bits) und „gaps” (Reihe von negativen Bits).
  3. Die Autokorrelationsfunktion {C_{SS}}\left( t \right) nimmt nur zwei Werte an:

    N \cdot {C_{SS}}\left( t \right) = \sum\limits_{i = 0}^{N-1} {\left( {2{s_i}-1} \right)\left( {2{s_{i+t}}-1} \right)} = \left\{ {\begin{array}{*{20}{c}} N & {falls\:t = 0} \\{k \in \mathbb{Z}} & {falls\:1 \leq t \leq N-1} \\ \end{array} } \right.

4.2.2 Verschiedene statistische Tests

NIST (Hrsg.): „A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications” (Stand: April 2010)

  • Frequency (Monobit) Test
  • Frequency Test within a Block
  • Runs Test
  • Tests for the Longest-Run-Of-Ones in a Block
  • Binary Matrix Rank Test
  • Discrete Fourier Transform (Spectral) Test
  • Non-overlapping Template Matching Test
  • Overlapping Template Matching Test
  • Maurer’s “Universal Statistical” Test
  • Linear Complexity Test
  • Serial Test
  • Approximate Entropy Test
  • Cumulative Sums (Cusums) Test
  • Random Excursions Test
  • Random Excursions Variant Test

Weitere Informationen zu diesen Tests unter:

http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf

Statistische Tests sind ein notwendiges, aber kein hinreichendes Kriterium für einen Pseudozufallsbitgenerator (PZBG)!

4.2.3 Kryptographisch sicherer Pseudozufallsbit-Generator

Ein Pseudozufallsbit-Generator erfüllt den Next Bit Test, wenn es keinen Algorithmus mit polynomialer Laufzeit gibt, der aus den ersten l Bit einer erzeugten Pseudozufallsbitfolge s das \left( {l+1} \right)-te Bit mit einer Wahrscheinlichkeit deutlich größer als 0.5 berechnen kann.

Einen solchen Pseudozufallsbit-Generator nennt man einen kryptographisch sicheren Pseudozufallsbit-Generator (Englisch: cryptographic secure pseudo random bit generator, CSPRBG).

Ähnliche Artikel

Kommentar verfassen