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:
I don't plan to roll my own crypto. Just curious.
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.
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 ?
