1
$\begingroup$

The definition of the Blum Blum Shub cryptographically secure pseudorandom number generator is $x=x^2 \mod N$ where $N=p \times q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, the security comes from an attacker not knowing the factors of $N$, but why can't I simply use a single prime number?

$\endgroup$
  • 2
    $\begingroup$ Because we can easily compute $x$ given $x^2 \mod p$ $\endgroup$ – user13741 Feb 12 '15 at 6:05
  • 1
    $\begingroup$ @user13741, but is the attacker ever given $x^2$? $\endgroup$ – mikeazo Feb 12 '15 at 12:18
  • 2
    $\begingroup$ @mikeazo Yes, that is part of the definition of a CSPRNG. It should withstand "state compromise", s.t. in the case of learning the internal state (partially), it should be hard to compute the previous states. But when you are given some $x_i^2$, you can compute all the way backwards to all possibilities of $x_0$ (squaring is not injective, so there are multiple possibilities). $\endgroup$ – tylo Feb 12 '15 at 17:03
  • $\begingroup$ @tylo, good call $\endgroup$ – mikeazo Feb 12 '15 at 17:57
2
$\begingroup$

I suggest you read the paper about the generator, because that question is answered there: A Simple Unpredictable Pseudo-random Number Generator, Blum, Blum, Shoup, 1986

They don't have any formal expression of what is called "state compromise extension" there, but they already state in the section 6. The $1/p$ generator is predictable on page 6 exactly the case of using a prime modulus.

Their main point is: Yeah, it might look nice and have nice properties, but you can "calculate forward and backwards in the sequence with about $2|p|$ digits of information."

For more details I suggest reading the paper.

$\endgroup$
-1
$\begingroup$

Another reason is that the order of secret seed $x_0$ is a divisor of $p-1$. In the case with RSA modulus, the order is unknow and would contribute to the intractability of the problem. This assumption could gives an advantage to an attacker to build a distinguisher assuming that $x_i=x_0^{2^i}$.

$\endgroup$
  • 1
    $\begingroup$ Don't understand why someone has voted down, without giving more explanations. Assuming that every experimented one knows what are the mathematical features of BBS generator, it would be interesting to learn other clever reasons that the one (and not principal) I gave ! $\endgroup$ – Robert NACIRI Feb 12 '15 at 15:25

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.