Tag Info

New answers tagged


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


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


Knowing $M$ is not enough to break Blum Blum Shub because the internal state of the random number generator, $x_i$, should never be revealed. Therefore, while you are correct that knowing the current state allows you to know the next (and all subsequent) states, a secure implementation of BBS should not reveal the internal state. For provable security, only ...

Top 50 recent answers are included