Logo
Logo
Innovation­game

Key Generation


The concept of a tandem PRNG was developed for Monte Carlo simulations of physical processes.  It has been tested over many years with a variety of problems [e.g.  2, 3].  A tandem PRNG gives a better statistical spread of random numbers than a simple PRNG and, as such, is well suited to cryptographic purposes.  A tandem PRNG requires two random streams from two seeds.  Before the tandem PRNG can generate random numbers it must be primed.  The first stream of random numbers is used to populate an array variable A such that

A(i) = X1i x2-56 + 128
12

where A(i) is the ith element of the array and X1 is the ith random number from the first stream. 

The Value of A(i) is always an integer in the range 0 to 255, corresponding to the values required for the register keys.  The addition of 128 is required because the processor treats the unsigned integer value of the seed as a signed integer between -263 and +263 - 1.  The priming process involves only one of the two seeds required to operate the tandem PRNG.  Once the array has been primed with all 256 values, the tandem PRNG operates by using one seed to select the array element to be used for the next random number and the second seed to generate a new value to be entered into the array in place of the one that has just been used.  Mathematically, the random number, ni, is given by:

The replacement value is given by:

In (13) and (14), X 1 represents the first random stream and X 2 the second.

When the MTNG is first started, a single seed stream, Xn, is generated by a simple PRNG from a fixed seed value (IV) and is allowed to cycle for a fixed number of operations, calculating a new 64-bit random number (Xi) every 11ns (about 93 million seed values per second).  The number of operations in each cycle depends on the value of Xi and the number of milliseconds indicated by the system clock at the beginning of the cycle.  At the end of the each cycle, the polarity of the random number is reversed switching to a new part of the Xn sequence that can only be predicted from the value of Xi at the end of the cycle. 


[2] L D Howe, D K Ross and A J Allen Molecular Flow in a Model Pore System in Dynamics in Small Confining Systems p23 (Eds J M Drake, J Klafter and R Kopelman) MRS EA-22 1990

[3]L D Howe Studies of Traffic Flow Phenomena Using the VEDENS Computer Code Physica A 246 (1997)