CDR: Re: one time pad and random num gen

[Kevin Elliott]

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 at mac.com>                             ICQ#23758827