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

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

 
discard

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