CDR: Re: one time pad and random num gen

[Bill Stewart]

At 10:48 PM 10/2/00 -0400, 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.
>
>Perhaps that's just a theoretical definition, and no existant PRNGs come
>close. But I thought some good ones were out there.

The internal state of the PRNG is precisely the question.
In a PRNG-based cryptosystem, there are N bits of key,
and if you know them, you can crack the rest of the message.
There are a variety of attacks, including chosen plaintext,
chosen cyphertext, known plaintext, etc. that can tell you
different amounts of information about the key or message.
Some cryptosystems are quite strong, and make the work of guessing
the key based on known quantities too large to be solvable.
Others are quite weak, and mathematicians being the devious sorts
that they are, they can often find ways to exploit the weaknesses.

With a one-time pad, the state of the cryptosystem is as large
as the message itself - you've got one key bit applied independently
on each bit of message.  There is no state of the system that's
smaller than the message itself, and no way to tell if any bit 
you guess is valid or not, because there's one key bit that will
produce a 0 for it and one that produces a 1.


				Thanks! 
					Bill
Bill Stewart, bill.stewart at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639