At 22:48 -0400 10/2/00, Steve Furlong wrote:
Bill Stewart wrote:
By contrast, if you've got a pseudo-random number generator, which uses some mathematical process to generate the numbers, knowing bits 1...I-1 tells you something about bits I...N, so if the message has structure to it, you can often exploit it.
Isn't a good definition of a cryptographically-strong PRNG that even if you know bits 1..I-1, you still don't know anything about bit I? (Unless you know the internal state of the PRNG, of course.) A c-strong PRNG shouldn't be susceptible to any currently known analyses.
Actually if you can pull that off you've got yourself a darn fine real random number generator- any PRNG has to have some period after which it will begin to recycle (assuming no other randomness in introduced into the system), in which case you just set i>the period and read off future states using current state +1 = current state - period + 1. Assuming I< the period then I believe you have a fairly good definition. A cryptographically strong PRNG would then be a PRNG with a very large period and some way of reinjecting randomness to guarantee the device never begins to recycle. -- "As nightfall does not come at once, neither does oppression. In both instances, there is a twilight when everything remains seemingly unchanged. And it is in such twilight that we all must be most aware of change in the air--however slight--lest we become unwitting victims of the darkness." -- Justice William O. Douglas ____________________________________________________________________ Kevin "The Cubbie" Elliott <mailto:kelliott@mac.com> ICQ#23758827