Symmetri Developer Blog

The Random class in the .NET framework is used to generate “random” numbers. I use quotations around the word “random” because the output of the function Random.Next() is actually what is known as “pseudo-random”; it is the output of a deterministic mathematical algorithm that “mimics” randomness. Specifically, it is an implementation of Knuth’s subtractive random number generator, which is an algorithm that performs incremental lookups on a large table of values and outputs the difference between selected numbers. The output is close enough to random for most practical purposes encountered in software development, with the exception of cryptography (for which purpose the .NET framework also includes the System.Security. Cryptography.RandomNumberGenerator class).

Recently I was confronted with an interesting question in the line of work: just how “random” is the Random class? Is there a way to quantify the “randomness” of a so-called random number generator (RNG)? One can imagine a linear scale of RNGs ranked by “randomness” - at one end would be entirely predictable, non-random generators (such as a routine that returns a constant value); and at the other end what we might call “true” random processes that occur in nature such as atomic decay¹. In between, all other RNGs that one can think of would lie somewhere along that scale. But how exactly can they be ranked and “randomness” quantified?

It turns out that there are several suggested ways of measuring randomness. They all start by taking a sample output from the RNG in question, and one that is of sufficiently large size (bit streams of about 12MB have been mentioned in the literature); and then subjecting that output file to tests. There are many different testing processes that have been proposed for the task. Below are a selected few:

1) compression - a simple test is to compress the sample output using commercial compression formats such as ZIP and then to compute the ratio of compressed to uncompressed size. This test is really only good at finding large biases in your RNG; i.e. if the compression is able to siginificantly reduce filesize, you should assume that the RNG is producing output with definitive patterns

2) a visual test of Monte-Carlo plot - by plotting the values of RNG output onto a two-dimensional array, any large scale patterns become apparent to the human eye. A great example can be found at RANDOM.ORG²

3) DIEHARD test - the DIEHARD series of tests was developed by Prof. George Marsaglia at Florida State University. It applies a number of statistical tests to the sample RNG output; the composite of their results can be used to make an overall pass/fail judgement. It is a well-regarded process that is used, for example, to certify the fairness of the operation of online gambling sites

4) test for FIPS 140-2 - FIPS 140-2 is a standard maintained by the National Institute of Science and Technology in the United States that concerns itself with the security of cryptographic providers. Section 4.7.1 outlines requirements for approved RNGs; they are based mainly around the idea of entropy, which very loosely speaking is a measure of the information content of a sequence

Exactly how far one wants to go in testing a RNG for randomness depends on the context. For commercial non-cryptographic applications, it is probably good enough to use the built in RNGs that come with software development platforms - such as the .NET Random class (a caveat is that the seeding process for the RNGs should use a source that incorporates some natural uncertainty - such as a combination of time, local machine state and user input). For stronger “randomness”, there are a number of implementations of RNGs floating around in the public domain that can be used (e.g. a popular one is the Mersenne Twister). RNGs with a very high “randomness” have to rely on external, physical sources of entropy such as atmospheric data or atomic decay, and are probably only warranted in very specialized scientific applications.

¹There remains the philosophical question of what is “truly” random; for example, do the quantum mechanical laws that govern atomic decay generate “output” that is the result of some as-yet undiscovered deterministic process? The answer is probably no, but it’s a question that exercises the minds of some of the world’s best physicists and philosophers.

²The demonstration shows the alarming large scale patterns inherent in the RNG that is the PHP rand() function - alarming because most developers think of functions like that as “true” random number generators