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?
feedback
|
|
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. | ||||
|
feedback
|
