Testing and Validating RNG Implementations

Random number generator testing faces a fundamental challenge: truly random sequences and pseudorandom sequences from a good PRNG look identical to statistical tests. No finite-length test can prove a sequence is random — statistics can only detect non-randomness with some confidence. Testing validates that an RNG does not have obvious biases or patterns, but cannot prove cryptographic security. Cryptographic RNG testing has two distinct goals: (1) statistical quality — verifying output distribution looks uniform and independent; (2) cryptographic strength — verifying the DRBG algorithm is implemented correctly and the security claims hold. These require different test approaches.

NIST SP 800-22 provides 15 statistical tests for evaluating bit sequences. Tests include: Frequency (monobit) test — proportion of 1s should be close to 0.5. Block frequency test — frequency of 1s in each m-bit block. Runs test — number of uninterrupted runs of identical bits. Longest run test — length of the longest run of 1s. Binary matrix rank test — rank of binary matrices formed from the sequence. Spectral test (DFT) — detect periodic patterns. Overlapping template matching — count occurrences of specific patterns. Maurer's universal statistical test — compress the sequence, measure how much shorter it gets. Each test produces a p-value; p < 0.01 suggests non-randomness. Tests run on 1 million to 1 billion bits.