# Blum Blum Shub Pseudo-Random Generator Requirements

I am trying to understand the Blum Blum Shub pseudo-random generator originally described in A Simple Unpredictable Pseudo-random Number Generator

As best I can tell the requirements are:

1. For any $$x_i$$, only $$x_i^2 \bmod 2$$ is used (only the least significant bit)
2. $$x_{i+1} = x_i^2 \bmod N$$
3. $$N = p\cdot q$$
4. $$p \ne q$$
5. $$p$$ and $$q$$ are equal length primes
6. $$p \equiv 3 \pmod 4$$
7. $$q \equiv 3 \pmod 4$$
8. $$\gcd(pq, (p-1)(q-1)) = 1$$

I don't plan to roll my own crypto. Just curious.

• I misunderstood requirement 5. I've corrected my answer, specifying an additional requirement. I've also edited your question so that it uses MathJax formatting. I hope you don't mind. – forest Aug 2 at 5:02
• @forest The factors from 5 are important and as relevant as 6 and 7. The edit loses relevant information from an engineering perspective. If engineering doesn’t matter then line 2 is sufficient on its own. – ben rudgers Aug 2 at 5:31
• You can revert the edit if you'd like, or add in the relevant information. For 6 and 7, I just switched to using MathJax for congruence relations. It has the same meaning as it did before. – forest Aug 2 at 5:34
• @forest My feedback on the edit is editorial, not philosophical. The MathJax is fine. It's just a change in form. The change in content removes an engineering criteria that makes Blum Blum Shub more useful. – ben rudgers Aug 2 at 13:02

Your understanding of the requirements are correct. To elaborate, the first requirement you specify can be explained as taking the parity of $$x_i$$. Also, the two primes are called Blum primes and the modulus is called a Blum integer, which means $$p,q \in \mathbb P$$, $$p \equiv q \equiv 3 \pmod 4$$, and $$N = p \cdot q$$.

There are a few other requirements, such as choosing a random $$p$$ and $$q$$ of approximately equal length (essentially the same requirements for generating RSA primes, modulo congruence relations). The initial seed, $$x_0$$, must also be sufficiently large and must be kept secret along with the primes. Finally, $$p$$ and $$q$$ are typically chosen such that $$\gcd(\varphi(p),\varphi(q))$$ is small in order to maximize cycle length. They must be strong primes as the cycle length divides $$\lambda(\lambda(N))$$, which leads to short cycles if it is smooth.

If you wish to calculate any $$x_i$$ value directly from $$x_0$$ without first calculating $$x_1 \cdots x_{i-1}$$, you can use Euler's theorem to do $$x_i = (x_0^{2^i \bmod \lambda(N)}) \bmod N$$. Because of $$\lambda$$, you need to keep $$p$$ and $$q$$.

As usual, $$\varphi$$ refers to the Euler totient function and $$\lambda$$ refers to the Carmichael totient function.

Note that BBS is not a good CSPRNG. It is interesting from an academic perspective, but it does not provide a practical level of security, especially with realistic modulus sizes. It is also very slow.

• Thank you. How can I tell if p and q are approximately equal length? – ben rudgers Jul 30 at 13:36
• @benrudgers If you want a $2n$-bit modulus $pq$, you choose $2^{n-1}\le p<2^n$ and $2^{n-1}\le q<2^n$. Naturally you want $p$ and $q$ to be random, but the interval is so great that you can safely start your prime search at any random point within it. Alternatively, make sure $\lceil\log_2(p)\rceil \approx \lceil\log_2(q)\rceil$. See here. – forest Jul 31 at 5:03
• Thanks. That is what I thought, but assumptions seem to be particularly hazardous when it comes to PRNG's. – ben rudgers Jul 31 at 14:09
• @benrudgers Indeed. In this case though I'd recommend you use a different PRNG. Blum Blum Shub is really only a tool for teaching how security reductions work. It's not a useful random number generator. – forest Jul 31 at 18:33
• While analysing the cycle length of the sequence, I believe they also assume that the primes are "strong" to ensure long cycles. – Occams_Trimmer Aug 1 at 8:53