This document is intended to lead into a document introducing a stream cipher.
This stream cipher needs a supply of highly random bits,
delivered as rapidly as possible.
This document may also be of interest to
anyone needing a supply of random bits
for simulation or gaming purposes.
The two most common types of PRNG, differ only in the iterative equation they use :-
[A] Xn+1 = (a.Xn + c) mod m
[B] Xn+1 = G.Xn mod m
Other PRNG's exist - see 'Knuth' (full reference below).
This document discusses type [B] only.
------------
[Some documents on this site are referred to repeatedly below. The link to my page of references is :- refs.html - includes ISBN numbers should you wish to purchase any of them.
The references of particular relevance in this document are :-
Ref [11] "The Art of Computer Programming, Vol 2,
Seminumerical Algorithms" by Knuth.
(Below I refer to this as 'Knuth')
Ref [16] "Handbook of Applied Cryptography"
by A.J. Menezes, P.C. van Oorschot, S.A. Vanstone.
(Below I refer to this as 'Menezes')
The 'Knuth' book is aimed at random numbers for simulation or games use; the 'Menezes' book at cryptography. The target application for this document is the use of PRNG's for the high speed encryption of high flowrate, high volume, low or moderate value files such as video and data-bases etc.
[Such files are in a fundamentally weak security position - high security can only be obtained at significant expense.
Furthermore, with high security, the speed of file encryption and decryption will likely provide a poor user experience.
For files of this type, minor leakage of information is probably a more practical project objective than high security.]
The generators discussed below are all of high statistical quality and can be used with confidence in simulation or games playing.
------------
With a type [B] PRNG, 'm' should ideally be a prime, and when this is done 'G' should ideally be a generator of the multiplicative group of the prime. These ideals make the operation of the type [B] PRNG multiplication in a Finite Field. This is the only form of PRNG discussed within.
[A note for readers unfamiliar with Finite Field arithmetic :-
(a) Finite Fields have a 'finite' number of members.
(b) Multiplication of any 2 members of the multiplicative group of a Field form a product which is also a member of the multiplicative group.
Suppose two group members are selected at random the first as a multiplier and the second as a 'seed'; if they are multiplied together and then this 1st product multiplied by the multiplier to get a 2nd product ... over and over. Eventually the running product will return to the seed.
(This is a consequence of statements (a) and (b) above. New products cannot appear indefinitely - eventually a product will recur, as a consequence of the finiteness of the group. Hence eventually a 'cycle' will form.)
(Logically, it might be thought possible for a non-cyclic preliminary sequence of products to be formed before a cycle develops. This behaviour does not occur with multiplication in a Finite Field - the 'seed' (i.e. starting value) is always an element of the cycle.)
The number of steps needed to complete a cycle is a property of Field members (multipliers) known as the 'multiplicative order' of the member. This property varies from member to member, but it's value can only be from a small set of values - more comments below.
A generator is a member of a Field whose multiplicative order is a maximum.]
For a type [B] PRNG, the Finite Field multiplicative group is :-
Multiplicative group members = {1, 2, ... (p-2), (p-1)}
Order of this group (= #members) = (p-1) [for 'p' a prime].
[Note that 'zero' is not an element of this group.
If Xn ever became zero,
the output of the type [B] PRNG would be zero thereafter.
It may be necessary to insert defensive measures
into your code if this problem could occur
(engineered by a malicious user, perhaps).]
Once correctly set up,
i.e. X0 is an element of the multiplicative group,
and 'G' is a generator
a type [B] PRNG will never return a value of zero
and cycles through every element of the multiplicative group
(each of the (p-1) elements returned just once).
Then starts over ...
[Groups with this behaviour are known as 'cyclic groups'.]
Finding a generator of the multiplicative group.
One way to increase confidence in sensitive simulation exercises is to repeat the work with a different PRNG. Other than using a new 'seed', the simplest way to do this is to keep the Safe prime unchanged, find a new generator and repeat the work.
Any textbook will present algorithms to do this (e.g. 'Menezes' algo 4.80). On inspection of algo 4.80 a difficulty is immediately apparent - a factorization of the multiplicative group order (p-1) is required.
Factorizing is, in general, a tough problem. However, by selecting certain types of prime (e.g. Safe primes), this problem can be eliminated :-
Safe primes (a.k.a. Sophie Germain primes - she proved that
Fermat's last theorem was correct for these primes) are defined as :-
Safe prime ps = 2.q + 1
[with both 'ps' and 'q' prime].
Clearly, for ps, the multiplicative group order is 2.q
- and the factorization of (ps - 1) is self evident.
[There may not be an infinite number of Safe primes
- there may be a 'last one'.
Below I present a 2048 bit Safe prime
- hence there are certainly plenty for present purposes!]
Removing the factorization stage considerably eases the difficulty of finding a generator for a Safe prime.
Consider, now, the number of generators available with a Safe prime :-
'Ref 12' page 34 Proposition II.1.2 states :-
--------
Every Finite Field has a generator.
If 'g' is a generator then gj is also a generator
if and only if GCD (j, (p-1)) = 1
In particular, there are PHI (p - 1) different generators.
--------
[PHI(x) being Euler's totient function
- it is the number of elements in {1, 2, ... x}
which are relatively prime to 'x'.
e.g. PHI(prime) = (prime-1).
[The 'x' in the set of elements appears superfluous,
(since GCD(x, x) = x always)
but is conventionally included to get PHI(1)=1
- an odd statement needed in some theorems.]
Recall that PHI() is multiplicative.
[i.e. if N = p.q.r... (simple primes with exponents)
then PHI(N) = PHI(p).PHI(q).PHI(r)...
(provided the {p,q,r...} are all mutually prime)].
--------
Hence #Safe prime generators =
PHI(ps) = PHI(q).PHI(2) = (q-1).1 = (q-1)
This means that, for a Safe prime, very nearly half
of the members of the multiplicative group are generators.
Textbooks prove that elements of the multiplicative
group of a Safe prime have orders from set {1, 2, q, 2q} only
- with a generator having order 2q.
For project planning purposes, it can be assumed that half the group members, when using a Safe prime, are generators. In other words, if a random group element is selected and it's status as a generator tested with 'failure' resulting, then the element can be incremented and the test repeated. This process will quickly find a generator.
Note that use of group member '1' as generator 'G' (for rhetorical purposes only - '1' is never a generator!) is unacceptable here since the output sequence {X0, X0 ...} results. (1 always has an order of '1'.)
Group member '2' (this might be a generator) is also unacceptable - half the calls will result in
Xn+1 = 2.Xn (no 'mod ps' step being done) - just a bitshift with unacceptable serial correlations.
Similarly 4, 8, 16 ... should be rejected.
These cases illustrate the fact that merely testing generator status alone will be inadequate.)
The following procedure has a high probability of deriving a good new generator :-
(A) Use the processor Time Stamp Counter as a source of random bits to start the process.
This can be done using opcode RDTSC.
[An introduction to the use of RDTSC can be found in Speed Testing.]
Only the last 25-30 bits or so of the TSC can be considered random; hence :-
(B) Expand the RDTSC output by using it as X0 and cycling it through a PRNG - the last byte of the RDTSC output might do as a loop counter for this step.
(C) Then use the PRNG to fill a suitably sized array to hold the generator initial value.
(D) Test - increment - test ... until a generator is found.
All my statistical test results summarized later were obtained from high quality generators set up as above. Degradation of statistical performance might occur otherwise.
[Small bitsize generators should be avoided. The only benefit from a small 'G' is that the execution time for Menezes algo 4.80 is reduced a little - but this benefit in no way compensates for loss in quality.
(Note that it provides no PRNG operational speed gain.)]
[Non-generators used as 'G' with a Safe prime in PRNG [B] should probably be avoided - their statistical characteristics cannot be guaranteed, short of heavy testing.
Two elements that MUST be avoided are '1' mentioned above, and another of order 2, namely (ps - 1).
For this element, the PRNG output will toggle between 2 values {X0, (ps - X0), X0, ...} - hopelessly non-random.
Other non-generators will have order 'q' - i.e. not maximal but fairly large.]
In summary, when a Safe prime is being used, testing the status of of a random group element for use as a generator is straightforward and there are plenty of them - in short, finding a new generator, when required, is very easy and fast.
Getting the best speed from the PRNG.
To obtain best performance for the generators discussed, I cycle the PRNG's in the 'Montgomery domain'. This is much more important when Stream ciphers are the target application than for simulation work. Hence, I discuss speed in my stream cipher document.
The stream cipher speed is slower than the PRNG's in this document since some additional components are used.
Statistical Tests for the generators above.
[Two books are referred to in this section :-
"Handbook of Mathematical Functions"
by M. Abramowitz and Irene Stegun
Dover, ISBN 0-486-61272-4
I refer to this as 'A&S'.
"New Cambridge Statistical Tables (2nd edition)"
by Lindley and Scott
Cambridge University Press, ISBN 0-521-48485-5
I refer to this as 'CST'.]
There are a great many tests that can be applied to the output of PRNG's and more appear all the time - a sentence that implies that some chink in the statistical performance of a PRNG may go undetected unless all known tests are employed!
'Knuth' discusses the Chi-Square (Section 3.3.1 pg 42) and the Kolmogorov-Smirnov (Section 3.3.1 pg 48) tests in some depth.
The Chi-Square test is applicable when integral values are to be tested (i.e. applies directly to a PRNG output).
'Knuth' also presents 8 empirical tests (Section 3.3.2 pg 61).
[The Kolmogorov-Smirnov (KS) test applies when values are believed to be from a continuous probability distribution. It would be possible to use this test directly by 'cast'ing the PRNG output into either a 'float' or a 'double', normalizing the 'float' by division by 2n to produce a uniform (floating point) random number in the range [0.0 ... 1.0), then applying KS. Such a test would be weak, since only the leading dozen or so bits of each value would have significant impact.
(This problem might be avoided by splitting each 64 bits of PRNG output into 4# 16 bit chunks, and proceeding on the lines discussed using the chunks.)]
'Menezes' discusses "Five basic tests" - a Frequency test, a Serial test, a Poker test, a Runs test, and an Autocorrelation test.
Later he discusses Maurer's universal statistical test (Algorithm 5.33) of which he says "... it is able to detect any one of a very general class of possible defects ... This class includes the five defects that are detectable by ... [the 5 tests just listed]."
It does require a very large sample of the PRNG output, but on a modern PC this is not a serious problem.
This means that the Maurer test is both very sensitive and saves a good deal of time writing test software.
In this document, I restrict myself to Chi-Square and Maurer testing.
The Chi-Square test generates a single statistic whose probability distribution depends on 'the degrees of freedom' (DOF) of the test.
If the DOF is small (< 25), the probability curve of the statistic is a function of an integral and a Gamma function. [All statistical tables (including 'CST') tabulate this probability curve for small DOFs.]
However, for larger DOF's, the probability curve approximates a Normal (a.k.a. Gaussian) curve.
[See the top of pg 37 in 'CST' for a formula to derive a value, from Chi-Square output, which can be used to find the probability desired via the Normal curve.]
My tests were done on bytes with 256 different values and a DOF 1 less at 255. For such a large DOF, the 'CST' approximation is fine.
The Normal distribution can itself be approximated by using formulae in 'A&S' section 26.2.18 or 26.2.19. The latter has an error bound < 1.5*10-7 and the former an error bound < 2.5*10-4. I used the less accurate formula since it's error bound is good enough for this task.
The Maurer test generates a statistic that should fit a Normal probability curve with a specified mean and variance. The mean is large (5 < mean < 16) in relation to the variance (a factor of perhaps 104 times < mean) i.e. the Normal probability curve is close to a delta function.
This makes the test very sensitive.
[It also means that 'double's should be used in the test, rather than 'float's, to avoid round off problems.]
The 'A&S' Normal approximation, from above, can be used again here.
The KS test generates 2 statistics - Kn+ and Kn- ('n' the number of samples). Both these must follow a probability distribution given in Knuth's Table 2, pg 51. This probability curve is calculated by the evaluation of a series (see Knuth eqn 26, pg 57).
However, an approximate probability at the bottom of Table 2 (applies when n > 30) suffices.
This test can be applied to the outputs of either the Chi-Square or Maurer tests. In this document I apply it to the Chi-Square output. In the associated Stream cipher document, I apply it to the Maurer test output.
Results from Statistical Testing.
From the theory above I developed a set of PRNGs :-
MG_64, MG_128, MG_256, MG_512, MG_1024 and MG_2048.
[The code here is MG = "multiplicative PRNG" and the number is the bitsize of the Safe prime and generator.]
All these PRNGs use 64-bit code (with some 64-bit assembler modules) - this gives a speed gain of around '4' relative to 32-bit code.
[In what follows all probabilities are cumulative probabilities - I use code 'Pr' for these.
For such probabilities the ideal value is generally 0.5.]
As mentioned above, I 'work' these PRNGs using the Montgomery 'modding' technique.
I also leave them all permanently in the Montgomery domain (no 'mapping out' - just using Montgomery domain values directly as the output). This yields a further speed gain of about 3 for MG_64; and about 25% for MG_2048.
Typical test results.
CHI-SQUARE followed by KS TESTING OF MG_64 :-
Test = Byte testing using all 64 bits as continuous stream.
NCONTAINERS=256, EXPECTED_BIN=16, N_CSQ_MEASUREMENTS=1024
run 0 :- Pr for Kn+ = 0.603, Pr for Kn- = 0.649
run 1 :- Pr for Kn+ = 0.611, Pr for Kn- = 0.268
run 2 :- Pr for Kn+ = 0.998, Pr for Kn- = 0.242
run 3 :- Pr for Kn+ = 0.744, Pr for Kn- = 0.551
run 4 :- Pr for Kn+ = 0.0046, Pr for Kn- = 0.959
run 5 :- Pr for Kn+ = 0.0113, Pr for Kn- = 0.815
run 6 :- Pr for Kn+ = 0.919, Pr for Kn- = 0.408
run 7 :- Pr for Kn+ = 0.018, Pr for Kn- = 0.865
run 8 :- Pr for Kn+ = 0.475, Pr for Kn- = 0.774
run 9 :- Pr for Kn+ = 0.844, Pr for Kn- = 0.393
run 10 :- Pr for Kn+ = 0.747, Pr for Kn- = 0.523
run 11 :- Pr for Kn+ = 0.091, Pr for Kn- = 0.546
run 12 :- Pr for Kn+ = 0.394, Pr for Kn- = 0.633
run 13 :- Pr for Kn+ = 0.764, Pr for Kn- = 0.148
run 14 :- Pr for Kn+ = 0.876, Pr for Kn- = 0.143
run 15 :- Pr for Kn+ = 0.611, Pr for Kn- = 0.567
Ave Kn+ Pr value = 0.682
Ave Kn- Pr value = 0.646
---------------------
MAURER TESTING OF MG_128 :-
Test = All 128 bits as continuous stream.
NTRIALS=16 [New generator for each trial.]
L-bit blocksize = 6 Average Pr = 0.436
L-bit blocksize = 7 Average Pr = 0.470
L-bit blocksize = 8 Average Pr = 0.599
L-bit blocksize = 9 Average Pr = 0.439
L-bit blocksize = 10 Average Pr = 0.460
L-bit blocksize = 11 Average Pr = 0.497
L-bit blocksize = 12 Average Pr = 0.538
L-bit blocksize = 13 Average Pr = 0.562
L-bit blocksize = 14 Average Pr = 0.665
L-bit blocksize = 15 Average Pr = 0.493
L-bit blocksize = 16 Average Pr = 0.464
---------------------
All the results above are satisfactory.
[I will not present other test results - they are too voluminous.]
The KS test statistics from the Chi-Square tests contain a few values such as '0.0113' and '0.998' which by themselves might be considered failures; but what matters is the behaviour of the population of results. If the population is of at least moderate size, there will always be outliers - indeed if there were not that would be suspicious. However, the number of outliers is a little large.
The average KS statistics at the base of the table are a little large. This behaviour persists when the tests are repeated. However, the deviation from the 'ideal' is moderate.
The Maurer test results are very good.
All of the MG PRNGs have been tested, each in several different ways.
As well as the whole of the PRNG output (as above), I have extracted both the least and most significant bytes of the least significant 64 bit word, concatenated these and tested the resulting sequence - all with satisfactory results.
[Below I present some Safe primes. These primes have several of their most significant bits set. This is necessary to avoid biased leading bits being output by the PRNG. This technique has to be adopted to avoid non-random leading bits.]
I have also used a small number of Safe primes in the PRNGs and repeated the tests - again with satisfactory results. So far, I have not come across an MG type PRNG that could be considered unsatisfactory.
It would appear that any reader needing to set up a good quality PRNG might just follow the suggestions above and cut down on testing - or even skip it.
Next, some values are presented to assist with the setting up of PRNG's on the lines above.
[UL_64 is #defined as "unsigned long long" in my code.
i.e. an unsigned 64 bit integer.]
[The primes below have 'all set bit' sections at their head.
This technique ensures that the PRNG most significant byte
will have negligible bias among its 256 possible values.
This is ideal when the PRNG is intended for simulation
and similar tasks and all PRNG output bits are being used.
For cryptographic purposes when only a fraction of bits
from the least significant end are being used, this
technique is of less value.]
Safe Prime =
UL_64 P[1] = {0xFFFFFFFFDA188043} ;
generator =
UL_64 gen[1] = {0xA54BE31BFE8FC033} ;
Safe Prime =
UL_64 P[2] = {0xFFFFFFFF9ABD3BEF, 0xF8FB554F9465351F} ;
generator =
UL_64 gen[2] = {0x6F7739B61C3CC216, 0x420A080875C5F8F7} ;
Safe Prime =
UL_64 P[4] =
{0xFFFFFFFFD5AEFEAA, 0xBBB62461BF0024EB, 0xA2A9024C00A76890, 0x2EF9134B6987EAD7} ;
generator =
UL_64 gen[4] =
{0x7C442C8AB9C68D25, 0x484BD5555D2767A1, 0xA43F675D3F014320, 0x428E9F2B52AC1E19} ;
Safe Prime =
UL_64 P[8] =
{0xFFFFFFFF053AD522, 0xC8AD7DB23DB514C4, 0x88721748E61A4BC1, 0x019E9D9089B46003,
0x4D0148BBBD9C8586, 0x15883E3A8C880366, 0x820CC2BCCC953B98, 0x63E4E2658D5842C3} ;
generator =
UL_64 gen[8] =
{0xC386941B73432DAF, 0xB24E9AEC76B4777A, 0xCFEA5B551E2C31FD, 0x3EA2B173224FA3FA,
0xE507643037B75D66, 0x902E7D5C3B6F61F4, 0xDCD149BB4093B928, 0x9803D97584C1FF56} ;
Safe Prime =
UL_64 P[16] =
{0xFFFFFFFF05C5904E, 0x9D82B74961E99259, 0xDCB30B063D4A09DC, 0x9B277A0EDD83CF3D,
0x0A7D3DDCB5311310, 0x916C666AEAB6AA51, 0xEBEE4F258B02A86F, 0xBBE7D8B6F7FF601F,
0xE3BE67147C403974, 0x0E71F962B1739B15, 0xA9731200D26C8C8A, 0x1DDAEE985F29F72D,
0x20F9A6B65BCE8974, 0x0E13F74E99627748, 0x1E5D454EF7BA48BA, 0x56BF5860BE04A75F} ;
generator =
UL_64 gen[16] =
{0x0EFAC8FF41C79381, 0x8E7FF6800F2AFC3B, 0x09F10ED066BAE33B, 0x58008F3D1A7385A8,
0x1D3A4EF9BF79081F, 0x341D9E03144A56D9, 0x695BEE94F43CDA2B, 0xBC37E5B602A9744F,
0x60F0F7BFE57E4E02, 0xFCB60038B5392F0B, 0x456C095C7BCF1F2A, 0x8950CE218F7EC766,
0xC5301412A36B3E67, 0xECB702163F8CA64C, 0xAC6C5A36B2A05C55, 0xB32A55C745601E11} ;
Safe Prime =
UL_64 P[32] =
{0xFFFFFFFFF892E765, 0xB5A328A9E6254F41, 0x15B6F1A7E439D5D2, 0xB151C095D4B52122,
0x762DEA31D65D568A, 0x3E837BFEB83BB8C8, 0x03A023E992278305, 0x3BBDA84F0A8F08D4,
0x582371C30034765E, 0x413DB9B8B0CF1E91, 0x11684906E77E9CD8, 0x8206A5BD95F8C950,
0x4DDEAC83AA5B51E7, 0xC37BF42D89D16A80, 0xAB6125E2476F7ED2, 0xFDD2A7B66C340124,
0x316398C03B70A999, 0x6E2D524E3C51C80E, 0x1BD118B2058B489F, 0xF382DCB45E934C10,
0x920EBCF26061C795, 0xB24046A80DCF4508, 0x7801AF6ECFC8CF72, 0xA6070CBF7DD67E77,
0x9691C1B855F5AAB4, 0xB2A64B84514095B5, 0x8D1A45F51258506E, 0x2CD7E33C5C771C74,
0x0868E6F0E96C05E3, 0x1F6367F6F32A15FE, 0x2F91D18B7458ABF9, 0xDAA1CE60519C44B3} ;
generator =
UL_64 gen[32] =
{0xF2CD67DF81D2A70D, 0x8BA9997DF20A2012, 0x751A5865255C4E46, 0x7F0F3115FD2F4A0F,
0x3E065516A777A6F8, 0x27F24BCF4B4EFFDF, 0xEE8D2F938CFD2F8B, 0x30906330E439709B,
0x3109BBA6264EF6A8, 0xA1945AC0DB43FB71, 0x221CCFD296E7B72E, 0xC56BB10CF4D9DA60,
0x9FE528426C6096B1, 0xDABE56A164F5E678, 0x5EC074E3893174A3, 0x64D1FB6A528A8486,
0xF11CC2C92096ABE3, 0xF854949972DC377D, 0x7B87B68937CDD715, 0xC5B03CCFAF334391,
0xC9481DA234650F89, 0x48E50F7FBBC389CB, 0xAFD71EA8566F6FC6, 0xCFF513FCB14C20DF,
0x878507B84BC63FE6, 0xE611552128127C71, 0xA469A1AFECC7D846, 0x3BD0DE7271979102,
0xFA1D136770F9EA74, 0x679858A784F1DCF9, 0x6673089284AEB57E, 0x245CEC52574C17ED} ;