Website: Walter Gregg

On this page: Main Content. Results. Theory. Flaw. Code. Ent.

A Deterministic True Random Number Generator?

Is it completely impossible to deterministically generate true random numbers, or is it only almost completely impossible? It seems that Rexx, at least on OS/2, can actually generate pretty good quality true random numbers by simply incrementing a counter over a variable interval. Through modulus arithmetic the resulting count can be reduced to a byte value between 0 and 255 inclusive and this can be output as a random character. The byte value can then be used to determine the next measurement interval, 10 to 265 millseconds, as well as the sleep interval needed to limit CPU usage to some 50%. My system's Rexx can only measure down to 10 milliseconds but even so on a slow 1 GHz system this scheme appears to produce some 200 decent quality true random characters a minute.

Results

How true is the randomness? I saved 3000 generated bytes to a file and checked it with John Walker's 'Ent'. The file had:

Subsequent runs didn't look too bad either; for example in one the 'Chi square distribution' value was exceeded 10% of the time instead of 50%, but that's still a bit surprisingly not bad. So it looks as if the values produced are at least a little bit random in actual fact.

Theory

How could this work at all? When a computer is counting over an interval, it's effectively digitizing time, which is an analog value. Digitization produces quantitization noise, and noise is randomness. It's also the case that the counting speed and interval both vary depending on clock speed and CPU availability. There's enough variation that when the count is reduced to the byte range 0-255, any of the values occur with roughly equal probability. Intuitively, there is a little bit of true randomness available to extract.

Flaw

In the first place, as I write this, it's April 1st. In the second place, we know it can't be this simple to produce true random numbers. If it was, everybody would be doing it. Nobody would go to the trouble of using the Entropy Gathering daemons (Perl, Rexx). Nobody would worry about the reliability of the Linux random devices. Mozilla based software wouldn't rummage around the file system at startup looking for entropy. Intel wouldn't include an on-board random number generator. People wouldn't sell, let alone buy, true random number generator plug-in cards.

There has to be a flaw. Why doesn't Ent see it? Legions of mathematicians, cryptographers, and computer scientists should be able to thoroughly debunk this script -- but can they do it in English that even I can understand? That is the question.

Rexx Script: Untrusted Random Number Generator

Ent

  1. J. Walker, Ent - Fourmilab (2008), available at www.fourmilab.ch /random/.
  2. J. Walker, Ent - Fourmilab:OS/2 Binary (Compiler W. Gregg Jan. 2003 from Oct. 1998 source), available at hobbes.nmsu.edu /h-viewer.php ?dir= /pub /os2 /apps /analysis &file =ent-os2.zip.

, A Deterministic True Random Number Generator? (Apr. 1, 2016) (available at . © W. Gregg 2016; CreativeCommons.org /licenses /by-nc-sa /4.0.

📧 Send Comment Walt.Gregg.Juneau.AK.US/contact
🏡 Home Page Walt.Gregg.Juneau.AK.US
  Global Statistics   gs.statcounter.com