5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – forest Aug 2 at 5:02
  • $\begingroup$ @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. $\endgroup$ – ben rudgers Aug 2 at 5:31
  • 1
    $\begingroup$ 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. $\endgroup$ – forest Aug 2 at 5:34
  • $\begingroup$ @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. $\endgroup$ – ben rudgers Aug 2 at 13:02
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. How can I tell if p and q are approximately equal length? $\endgroup$ – ben rudgers Jul 30 at 13:36
  • 1
    $\begingroup$ @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. $\endgroup$ – forest Jul 31 at 5:03
  • $\begingroup$ Thanks. That is what I thought, but assumptions seem to be particularly hazardous when it comes to PRNG's. $\endgroup$ – ben rudgers Jul 31 at 14:09
  • $\begingroup$ @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. $\endgroup$ – forest Jul 31 at 18:33
  • $\begingroup$ While analysing the cycle length of the sequence, I believe they also assume that the primes are "strong" to ensure long cycles. $\endgroup$ – Occams_Trimmer Aug 1 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.