1
$\begingroup$

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?

|improve this question
$\endgroup$
  • 3
    $\begingroup$ What makes you think $x_n$ is available to you? :) $\endgroup$ – Thomas Feb 6 '15 at 14:01
  • $\begingroup$ 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. $\endgroup$ – Maarten - reinstate Monica♦ Feb 7 '15 at 13:26
  • $\begingroup$ Instead of changing your question like that, I'd suggest you ask another, separate question on here. $\endgroup$ – mikeazo Feb 7 '15 at 21:17
2
$\begingroup$

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 one bit should be revealed at each iteration. That said, you shouldn't be using BBS in practical applications at all.

|improve this answer
$\endgroup$
  • $\begingroup$ One bit per cycle? For an algorithm that uses RSA key-sized numbers? $\endgroup$ – Melab Feb 7 '15 at 19:35
  • 1
    $\begingroup$ @Melab: Yepp, that's correct. The security proof of Blum Blum Shub only holds with this small numbers. If you use BBS, you want this security proof, otherwise there would be much faster alternatives. The second link in this answer shows the reason for this. $\endgroup$ – Nova Feb 7 '15 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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