# 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. Commented Aug 2, 2019 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. Commented Aug 2, 2019 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. Commented Aug 2, 2019 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. Commented Aug 2, 2019 at 13:02
• $x_i^{\,2}\bmod 2$ is correct, but the same as $x_i\bmod 2$, which is simpler, thus preferable.
– fgrieu
Commented Nov 21, 2023 at 17:46

## 2 Answers

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 roughly equal size. This is done just like for RSA. If you want a $$2n$$-bit modulus $$p\cdot q$$, you can choose $$p$$ and $$q$$ randomly in the range $$[2^{n-1},2^n)$$. Naturally you want $$p$$ and $$q$$ to be hard to predict, but the interval is so great that you can safely start your search at any random point within it without making it easier on an attacker. To make sure you don't get a modulus of $$2n-1$$ bits half the time, a common trick is to choose the primes in the range $$(\sqrt{2}\cdot 2^{n-1},2^n)$$ instead. This ensures that $$\lceil\log_2(p)\rceil=\lceil\log_2(q)\rceil$$, which simplifies programming ($$\sqrt{2}\approx 1.5$$, so you can just set the two most significant bits of each prime).

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, usually done by choosing safe primes (integer $$p$$ is a safe prime if $$p,\frac{p-1}{2} \in \mathbb{P}$$) as the period divides $$\lambda(\lambda(N))$$, risking short cycles if 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 per convention, $$\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 as it is provably reducible to the QRP, but the proof does not provide a meaningful level of provable security without an impractically large modulus. It is also very slow when used correctly because it must output only one bit at a time. The security "proof" is utterly useless to practitioners and is ignored by the cognoscenti. It ends up serving as nothing more than a trap to the naïve in their quixotic search for perfect security.

• @benrudgers 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. Commented Jul 31, 2019 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. Commented Aug 1, 2019 at 8:53
• @Occams_Trimmer Isn't that satisfied by ensuring $\gcd(\varphi(p),\varphi(q))$ is small? Commented Aug 2, 2019 at 5:07
• Yes, you're right. I missed that. Commented Aug 2, 2019 at 7:39
• It's in §8 of the paper, Theorem 8 to be precise. The length of the cycle divides $\lambda(\lambda(n))$ and therefore if it is smooth it could lead to short cycles. Commented Aug 5, 2019 at 8:03

I'm not understanding several things here. First, what does 'smooth' mean in this context ? It seems like this is repeated from BBS without defining it. "They must be strong primes, usually done by choosing safe primes (integer p is a safe prime if p,p−12∈P) as the period divides λ(λ(N)), risking short cycles if smooth."

Here is what I understand: when p,q are safe primes, then it's clear that given p=2.p1+1= 2(2.p2+1)+1 ibid for q, λ(λ(N)) = λ(lcm(\varphi(N))) = λ(lcm(p-1,q-1)) = λ(lcm(2.p1, 2.q1)) = λ(2.p1.q1) = λ(2.(2p2+1).(2q2+1)) .. = 2.p2.q2. So if the period divides λ(λ(N)) then it's a combination of the 3 factors, hopefully all of them. Can you elaborate on this if you know ?
The BBS paper confused me because in section 8 it basically proves that for safe primes the period is equal to λ(λ(N)) for 'some' quadratic residues, but then later in section 9 it shows how to calculate the period for one quadratic residue. Also, finally on condition 5 above, I've read somewhere that you don't want p and q to be too close, since that would allow a search 'around' the square root of N. Is there a minimum safe distance ?

• Hi, while a very pertinent ontribution, this is not really an answer. PYou can split it up into a few comments under the question (or existing answer) as appropriate so discussion can proceed. Commented Nov 21, 2023 at 18:33
• if you search on the site some of your other questions are asnwered, such as how close is too close for the two primes, etc. Commented Nov 21, 2023 at 18:34