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?

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

1 Answer 1

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.

$\endgroup$
2
  • $\begingroup$ One bit per cycle? For an algorithm that uses RSA key-sized numbers? $\endgroup$
    – Melab
    Commented Feb 7, 2015 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
    Commented Feb 7, 2015 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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