# Why is knowing M not enough to break Blum Blum Shub?

In Blum Blum Shub, the generator is $x_{n+1}={x_n}^2 \mod M$ where $M=p \cdot q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, knowing $p$ and $q$ is enough to break the system. But if I know M, I can calculate the next number in the sequence, so there is no need to know the two factors. Why isn't that sufficient?

Update: Since I wasn't think all those times I read about BBS, just ignore the part about directly calculating the next number. Instead, why would knowing the period provide an attacker with any additional information?

• What makes you think $x_n$ is available to you? :) Feb 6 '15 at 14:01
• If the state of any PRNG (or DRBG in NIST's terms) is known then the numbers following that can be calculated until the PRNG is re-seeded with an unknown seed. That's what determinism means. Feb 7 '15 at 13:26
• Instead of changing your question like that, I'd suggest you ask another, separate question on here. Feb 7 '15 at 21:17

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.