Take the 2-minute tour ×
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
2  
"Blum Blum Shub"? Is that a random number generator, or a drowning Stooge? –  phenry Oct 27 '09 at 2:07
1  
@phenry: It is a random number generator: en.wikipedia.org/wiki/Blum_Blum_Shub –  Thilo Oct 27 '09 at 5:27
add comment

1 Answer

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
add comment

Your Answer

 
discard

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