PRNG (Pseudo Random Number Generator)

• Download control + demo page - 37.2 Kb

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:

1. Is easier to use
2. Avoids all those duplicate "random" numbers when using the Randomize and Rnd methods,
3. DOESN'T use or rely on Randomize and Rnd (for anything),
4. Doesn't rely on Internal Random Number tables,
5. Produces acceptable randomness (see the test result below), and
6. 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
    '=== QDNS.dll is not properly installed ================

    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
    '=======================================================================

    '===  Purpose: Generate a Random Number within the given limit

    '===  Note:    RND expects LowLimit and HighLimit to be of type LONG.

    '===           In VBScript everything is a Variant, PRNGMIT is 

    '===           strongly typed, so

    '===           ALWAYS Convert -CLng()- your Values in your ASP Pages. 

    '========================================================================

    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.