Innovation­game
My Personal Website

Design of the PRNG


A dedicated random number generator was developed to generate the secret keys for Humber.  The keys are generated by a multiple tandem pseudo-random number generator (MTNG) which comprises four tandem PRNGs.  Each tandem PRNG has an array of 256 elements.  The array has to be primed before the tandem PRNG can begin to generate number sequences.  A PRNG requires an initial random number (the seed) and all subsequent random numbers are produced by applying a predictable mathematical operation on the current value of the random number:

Xi+1 = P(Xi )
8

X0 is the seed, Xi is the ith value of the random number, Xi+1 its next value and P represents the mathematical operation. 

In order to identify the correct value of the seed, any attacker would need to test the assumed value against encrypted messages.  Clearly, if there is only one possible value of seed, it will immediately be discovered and the test will be a formality.  Increasing the number of possibilities, increases the time it will take to test all possible values.  Let us assume that a modern supercomputer with multi-parallel processing can check 232 values of seed in one second.  If the seed (and subsequently generated random numbers) were a 32 bit integer, it would take no more than one second to identify the correct value of the seed.  However, if it were a 64 bit integer, the same super computer would take about 136 years to check every possible value.  Almost all modern portable and transportable devices can manipulate 64-bit integers, so a 64-bit format was chosen as the basis for the seed and random numbers.

It is essential to use a suitable form of P(Xi) that produces a good random distribution and will generate all possible values such that 0 ≤ Xi <  T, where T is the basis (e.g.  264).  Hull and Dobell [1] describe a suitable function as

Xi+1 = aXi + b (mod T)
9

In order to produce all possible values without repetition, it is only necessary to satisfy a = 1 (mod 4) and b = 1.  The correlation, ρs, between Xn and Xn+s is given by

ρs  = 
1 - 6
bs

T
(1 -
bs

T
) 

as
+  e
10
Where
as = as(mod T)
 
bs = (1 + a + a2 + … + a(s-1))b
 
e | < as /T

If a is chosen so that a ≈ √T, the correlation ρ1 ≈ T -1/2.  By using a = 2n + m, the only operations required are one shift left of n places plus two additions.  This provides the fastest method of computing the next value of Xi.  If T = 22n with n > 1, then, by using and a = √T + 1, a good performance can be expected in response to statistical tests.  In this case the next value of Xi is calculated via:

Xi+1 = 4294967317Xi+ 1
11

4294967317 is 21 greater than 232, which, in turn, is the square root of 264, the basis for seed generation.  The integer multiplication process neglects any overflow values, so Xi is always a valid 64-bit number. 


[1]  T E Hull and A R Dobell Random Number Generators SIAM Review Vol4 No.  3 (July 1962)