Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

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

2 Answers 2

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.

share|improve this answer

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

share|improve this answer
    
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 ! –  Robert NACIRI Feb 12 at 15:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.