1
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?
2
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.
Chris Johnsen
Posted 2009-10-27T01:41:11.117
Reputation: 31 786
2"Blum Blum Shub"? Is that a random number generator, or a drowning Stooge? – phenry – 2009-10-27T02:07:52.133
1
@phenry: It is a random number generator: http://en.wikipedia.org/wiki/Blum_Blum_Shub
– Thilo – 2009-10-27T05:27:00.930