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


/* make-random-bytes */
And there's no "house" to take it's rake, or hold the longest odds-
say 'A deterministic true random number generator?  No way.'
say
say 'Copr. walt.gregg.juneau.ak.us 2016; License: attribution'
say 'sharealike; Details: apache.org/licenses/LICENSE-2.0.'
say 'Absolutely no warranties, express or implied.'
say
say 'Argument 1: characters to generate.'
say 'Append 2>random.txt to capture random bytes to file.'
say
call RxFuncAdd 'SysSleep','RexxUtil','SysSleep'
x=time('r')
parse arg bytes
bytes=strip(bytes)
if datatype(bytes,'w')\ = 1 then signal oops
if bytes<1 then signal oops
interval=0.01
do i=1 to bytes
  call SysSleep interval /* Limit CPU load to about 50% */
  call getchar
  x=charout('stderr',result)
end
say
say bytes 'Bytes at' bytes / time('e') * 60 'per Minute'
exit 0
getchar: procedure expose interval
count=0
x=time('r')
do forever
  count=count+1
  if time('e')>interval then leave
end
dec=count//256
char=d2c(dec)
interval=(dec+10)/1000 /* Offset so min count is 10ms */
return char
oops:
say 'Specify how many doubtfully random bytes you want.'
exit 0

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.

 No Privacy