Blum Blum Shub Generator

As shown in [2] and [4], LCGs are vulnerable to attacks if they are used to generate keys in a cryptosystem or in similar situations because it is possible to recover the parameters of LCGs in polynomial time given several observed outputs.

Unlike all RNGs mentioned above, this generator has very strong cryptographic properties such as PT unpredictable (see Section 2.2) based on the unproven assumption that P$\neq$NP in computational complexity theory. Proposed in [3], BBS is a random bit generator with the following simple form

$$x_{n+1} = x_{n}^2 \mbox{ mod } M$$

where $M$ is the product of two large distinct primes, and the output is the least significant bit of $x_{n+1}$ or the parity of $x_{n+1}$. The main difficulty of predicting BBS's output lies in the intractability of ``quadratic residuosity'' problem , which is: Given a composite number $n$, find whether $x$ is a perfect square modulo $n$. It has been proven that this is as hard as cracking the RSA public-key cryptosystem which involves the factoring of a large composite.

However, BBS is not a permutation generator as the RNGs mentioned above. A $k$-permutation generator is a program which produces permutations of a set of $k$ distinct objects. Each of these permutations is called a $k$-permutation. A full-period RNG with period length $n$ is also an $n$-permutation generator since any $n$ consecutive outputs form an $n$-permutation. The period length of BBS is much lesses than $M$, therefore, it can not be adapted to produce uniform random variates between 1 and $M-1$. For example, use use $M=16873$, and hence the period is much lesser than 16873. Due to this reason, BBS failed all of the statistical tests we have conducted and is therefore not suitable for stochastic simulations. BBS also has a performance flaw since in practical use $M$ must be sufficiently large (like tens or even hundreds of digits) to provide resistance from being factorized in a short time.