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@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639