Introduction
If you have tried to use Randomize
and Rnd
in your programs, you know what I mean. The odds are incredible, but still you are facing those same reappearing "random" numbers.
This is because languages like VB and several others have a built-in "random number table". VB's, and hence VBScript's, is a table consisting of 16,777,215 random numbers (this is, coincidentally, one of those magic numbers). Calling randomize()
places you at some spot in the table (this is typically based on time of day). Calling rnd()
returns that value and steps you to the next value in the list. If you run the program again without calling randomize
, rnd()
will give you the same value every time.
The Problem: Getting Good random numbers
Personally, I just got too tried of having to deal with the issues appearing from the use of Randomize
and Rnd
in my VB and my ASP applications and since necessity is the mother of all inventions, I created my own PRNG (Pseudo Random Number Generator).
The best Random Number Generators are hardware based. Since I am a software guy, I went for "an algorithm that mimics the generation of random numbers" or in other words a Pseudo Random Number Generator (PRNG).
My aim was to build a PRNG that:
- Is easier to use
- Avoids all those duplicate "random" numbers when using the
Randomize
and Rnd
methods,
- DOESN'T use or rely on
Randomize
and Rnd
(for anything),
- Doesn't rely on Internal Random Number tables,
- Produces acceptable randomness (see the test result below), and
- Gives me peace of mind.
The Issues
Issue 1: Seeds are crucially important to getting a good random number, and it is difficult to find good seeds. Typical seeds such as current time, number of clock ticks since reboot, process ID or user input, produce only a limited number of random bits.
Issue 2: Some protocols are such that they can "leak" some details of the PRNG state. Given the deterministic nature of the PRNG, this can compromise security unless reseeding is carried out appropriately. In other words: other people could figure out the random numbers you used.
Issue 3: When you are generating Random numbers - using your most complex algorithm-, things may look good and things might look random, but are they really??
Importance of Random Numbers
Random numbers are fundamental to the use of cryptographic mechanisms. The primary uses of random numbers are for key generation and to ensure message uniqueness, which protects against various replay attacks (since many random numbers are not so random as they appear, the chances of figuring out the keys are much better than the odds let you believe). Authentication mechanisms may use a challenge or nonce (a random number) to protect against replay attack.
Confidentiality mechanisms use secret or session keys (derived from a random number) to protect data during a secure exchange. Digital signature mechanisms require large private keys - typically generation of these keys starts with large random numbers (e.g. candidate prime numbers)
Usage
Ensure that you have registered the PRNGMIT.dll file.
Set RandomObj = Server.CreateObject("PRNGMIT.prng")
If Err.Number = -2147221005 Or Err.Number = -2147024770 Then
Response.Write "<font color=red>ActiveX Dll not installed!" & _
" Please copy PRNGMIT.dll to your "
Response.Write "permanent Directory and run ""regsvr32 PRNGMIT.dll"" and " & _
"reboot</font><BR>"
Else
Dim LowLimit
Dim HighLimit
LowLimit = 0
HighLimit = 10
Response.Write "Random number between 000 and 010: <B>"
Response.Write RandomObj.Rnd(Clng(LowLimit), _
Clng(HighLimit)) & "</B><BR>"
Response.Write "Random number between 000 and 100: <B>"
Response.Write RandomObj.Rnd(Clng(0), Clng(100)) & "</B><BR>"
Response.Write "Random number between -314 and 786: <B>"
Response.Write RandomObj.Rnd(Clng(-314), Clng(786)) & "</B><BR>"
End If
Batteries of statistical tests for Random Numbers
However complex the PRNG is (or the method you made), it remains deterministic in its nature (...Life is just full of patterns). Theoretically, the sequence of random numbers will cycle after a (large) period. It is crucial to check how good the method is you are using. To check this, there is a battery of tests.
For Batteries of Statistical Tests for Random Number Generators see The National Institute of Standards and Technology website.
ENT A Pseudorandom Number Sequence Test Program
See: http://www.fourmilab.ch/random/.
Using this ENT test program to measure the Randomness of our MEELIX PRNG returned the following results:
Entropy = 7.999403 bits per byte.
Optimum compression would reduce the size of this 11468800 byte file by 0 percent.
Chi square distribution for 11468800 samples is 9483.75, and randomly would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 127.4783 (127.5 = random). Monte Carlo value for Pi is 3.141356425 (error 0.01 percent). Serial correlation coefficient is 0.000090 (totally uncorrelated = 0.0).
The DIEHARD Test Suite
See: http://stat.fsu.edu/~geo/diehard.html.
Using this DIEHARD Test Suite to measure the Randomness of our MEELIX PRNG returned the following results.
The Quick and Dirty Test
This test is based on taking the average of many numbers. If there are no skews, it should give a nice average of 0.5000....etc. Due to rounding problems, you never get the perfect 0.500000000000000.
The result of runs of 25,000, 40,000 and 100,000 random numbers with our MEELIX PRNG are shown below:
25,000: 0.500025832288101
40,000: 0.499552333479141
100,000: 0.500056488310338
Min: 0.000007182771611 (this is the smallest number from our run)
Max: 0.999989915832831 (this is the largest number from our run)
Guarantees: None
I make no claim about my MEELIX PRNG whatsoever, nor that it generates good random numbers, nor that the source code works as it is supposed to do (whatever that may be).
In short: You may use and distribute this ActiveX DLL/code free of charge, but you may not charge for it or present it as your own work. This notice should be retained. All software/code is provided WITHOUT WARRANTY either expressed or implied. If you find any bugs in this code, please notify the author. This code is provided "AS-IS" - if it doesn't work, we accept no responsibility, nor do we give support (hey, it is FREE).
� Copyright 2001 Meelix Information Technology, All rights reserved.