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. Ta, SRF -- Steve Furlong, Computer Condottiere Have GNU, will travel 518-374-4720 sfurlong@acmenet.net
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
On Tue, 3 Oct 2000, Kevin Elliott wrote:
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. --
Isn't that a misnomer though? If randomness is reinjected to prevent the system from falling into a period, then it won't be possible to generate the same sequence of bits twice -- so you can't use such a system for a PSEUDO-random generator, in applications like a stream cipher or whatever. Programs rely on the same sequence coming out of the same initial state with a PRNG -- otherwise things like stream ciphers can't be decrypted. What you describe above, I'd have termed an RNG - not a PRNG. Bear
On Tue, 3 Oct 2000, Kevin Elliott wrote:
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.
True, but the period can be made such that the last star in the universe will die and grow cold first. If you have for example a 256-byte internal state, and your PRNG is a full permutation (ie, eventually every possible state is on the path of the "cycle") you don't really need to worry about it. Bear
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
participants (4)
-
Bill Stewart -
Kevin Elliott -
Ray Dillinger -
Steve Furlong