X square modulo N generator

The X square modulo N (X^2 mod N) generator is an algorithm for generating a sequence of apparently random whole numbers (X[i]) in accordance with the recursive calculation rule:

X[0] := secret seed value, with X[0]*X[0] > N

X[i+1] := X[i]*X[i] (mod N) for i = 0, 1, 2, 3, ...

whereby X[i] are whole numbers from the range 0,1,2, ..., N-1.

In CrypTool we observe only "coin throws" ("heads" are mapped to the 0 and "tails" to the 1). In the X^2 mod N generator, the coin throw 0 is therefore represented by the event [X[i] = 0] (mod 2) and the coin throw 1 by the event [X[i] = 1 (mod 2)] . The sequence of coin throws is saved as a binary file (a sequence of 8 coin throws produces one random ASCII character).

The parameter with the X^2 mod N generator is modulus N.

Select Individual Procedures \ Generate Random Numbers and activate the radio button X^2 (mod N) random number generator. You can now specify the parameters under "Choose generator-specific parameters...".

x2modnoptions.gif

Please note that the quality of the X^2 mod N generator depends critically on the choice of parameters. If one knows the prime factorisation of modulus N, then it is possible to calculate the square root modulo N of X[i+1] and one can crack the random number generator. For this reason one often uses large RSA moduli for modulus N where in practice the prime factorisation N = p * q cannot be determined with knowledge of N alone. RSA modulus N = p*q is a predefined parameter with the characteristic that p and q are Blum numbers. Such X^2 mod N generators are called Blum-Blum-Shub generators.

The quality of the output generated by the random number generator can be tested with the aid of the random tests, periodicity analysis, compressibility and the Vitany analysis implemented in CrypTool.