# A Universal Statistical Test for Random Bit Generators

## Ueli Maurer

```
```A new statistical test for random bit generators is presented that is
universal in the sense that any significant deviation of the output
statistics from the statistics of a perfect random bit generator is
detected with high probability when the defective generator can be
modeled as an ergodic stationary source with finite memory. This is in
contrast to most presently used statistical tests which can detect only
one type of non-randomness, for example, a bias in the distribution of
0's and 1's or a correlation between consecutive bits. Moreover, the
new test, whose formulation was motivated by considering the universal
data compression algorithms of Elias and of Willems, measures the
entropy per output bit of a generator. This is shown to be the correct
quality measure for a random bit generator in cryptographic
applications. A generator is thus rejected with high probability if
and only if the cryptographic significance of a statistical defect is
above a specified threshold. The test is easy to implement and very
fast and thus well-suited for practical applications.