# If Blum Blum Shub is modified to use a prime modulus, is it still secure?

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?

• Because we can easily compute $x$ given $x^2 \mod p$ – user13741 Feb 12 '15 at 6:05
• @user13741, but is the attacker ever given $x^2$? – mikeazo Feb 12 '15 at 12:18
• @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). – tylo Feb 12 '15 at 17:03
• @tylo, good call – mikeazo Feb 12 '15 at 17:57

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."
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}$.