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?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Because we can easily compute $x$ given $x^2 \mod p$ $\endgroup$– user13741Feb 12, 2015 at 6:05
-
1$\begingroup$ @user13741, but is the attacker ever given $x^2$? $\endgroup$– mikeazoFeb 12, 2015 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$– tyloFeb 12, 2015 at 17:03
-
$\begingroup$ @tylo, good call $\endgroup$– mikeazoFeb 12, 2015 at 17:57
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
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}$.
-
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$ Feb 12, 2015 at 15:25