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$
4
  • $\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 '19 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$ Aug 2 '19 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 '19 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$ Aug 2 '19 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, usually done by choosing safe primes (integer $p$ is a safe prime if $p,(p-1)/2 \in \mathbb{P}$) as the period divides $\lambda(\lambda(N))$, which results in 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 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$
12
  • $\begingroup$ Thank you. How can I tell if p and q are approximately equal length? $\endgroup$ Jul 30 '19 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 '19 at 5:03
  • $\begingroup$ Thanks. That is what I thought, but assumptions seem to be particularly hazardous when it comes to PRNG's. $\endgroup$ Jul 31 '19 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 '19 at 18:33
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 5 '19 at 8:03

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.