Sign up ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

What is the reason behind the fact that the BBS generator only outputs the n least significant bits or the parity bit for each Xn it produces internally? That is, if it outputs the full Xn's that it produces, is there a way to differentiate it from a truly random function?

share|improve this question
"Blum Blum Shub"? Is that a random number generator, or a drowning Stooge? – phenry Oct 27 '09 at 2:07
@phenry: It is a random number generator: – Thilo Oct 27 '09 at 5:27

1 Answer 1

The usual answer to this type of question (why use only the lowest-order N bits?) is that it prevents leaking too much information about the internal state of the PRNG.

If you give your attacker your full X_n state at two consecutive states, they could easily(?) determine the modulus and thus calculate all future states of the PRNG.

That is, given the values a = X_n and b = X_(n+1), the attacker need only find the M such that b = a^2 mod M. As long as a^2 is larger than M, I think this should be easy to do. If M is larger than a^2, then b = a^2 and the attacker needs keep asking for numbers until the modulus comes into play.

share|improve this answer

Your Answer


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