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, 2019 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, 2019 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, 2019 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, 2019 at 13:02

1 Answer 1

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 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.

$\endgroup$
7
  • $\begingroup$ @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. $\endgroup$
    – forest
    Jul 31, 2019 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$
    – ckamath
    Aug 1, 2019 at 8:53
  • $\begingroup$ @Occams_Trimmer Isn't that satisfied by ensuring $\gcd(\varphi(p),\varphi(q))$ is small? $\endgroup$
    – forest
    Aug 2, 2019 at 5:07
  • $\begingroup$ Yes, you're right. I missed that. $\endgroup$
    – ckamath
    Aug 2, 2019 at 7:39
  • 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$
    – ckamath
    Aug 5, 2019 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.