Key Generation
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:
X_{0} is the seed, X_{i} is the ith value of the random number, X_{i+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 2^{32} 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(X_{i}) that produces a good random distribution and will generate all possible values such that 0 ≤ X_{i} < T, where T is the basis (e.g. 2^{64}). Hull and Dobell [1] describe a suitable function as
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 X_{n} and X_{n+s} is given by
ρ_{s} = | 1-6 | b_{s} | (1 - | b_{s} | ) | + e |
T | T | |||||
a_{s} |
Where | a_{s} = a^{s}(mod T) |
b^{s} = (1 + a + a^{2} + … + a^{(s-1)})b | |
|e |< a_{s} /T |
If a is chosen so that a ≈ √T, the correlation ρ_{1} ≈ T ^{-1/2}. By using a = 2^{n} + 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 X_{i}. If T = 2^{2n} 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 X_{i} is calculated via:
4294967317 is 21 greater than 2^{32}, which, in turn, is the square root of 2^{64}, the basis for seed generation. The integer multiplication process neglects any overflow values, so X_{i} 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)