"Philip Stubbs" <philip@???> wrote:
> 2008/5/16 Peter Alefounder <p_alefounder@???>:
> > Even if you could not show that the numbers were random (whatever
> > that might mean to a mathematician), if it was impossible to
> > predict the sequence, wouldn't that be good enough for practical
> > cryptographic applications? Chris Oattes' definition seems to me
> > to be sufficient. Could a non-random but non-predictable (with
> > probability > 1/10 per decimal digit) sequence exist?
>
> This got me thinking. The problem is not just whether the next digit
> can be predicted, but if there can be any long term cycles that could
> start to show.
>
> For example, given a ten digit number, it may be possible to say that
> it, on it's own, is random. Given 100 10 digit numbers, a pattern
> could exist that would not show up within one number, but would allow
> the 101'st sequence to be determined.
But as soon as you can do that, the sequence ceases to be random and
becomes predictable. I think Chris Oattes' definition still stands:
you just need something that will generate a sufficiently long
sequence. As Hugo says,
> they're called cryptographically strong pseudo-random number
> sequences. :)
>
> The important thing in the generation of PRNs is hiding the
> internal state of the generator. All PRNGs maintain an internal state
> array which contains the information necessary to generate the next
> number in the sequence. If you have that state (and the algorithm
> being used), then you can follow the sequence perfectly. The trick is
> in designing the algorithm so that it is computationally infeasible to
> determine that state array from looking at the output values alone --
> regardless of the quantity of output values you have.
... and you need to start from an unpredictable internal state. If
I have understood the matter correctly, that was the problem with
the Debian system.
Peter Alefounder.
__________________________________________________________
Sent from Yahoo! Mail.
A Smarter Email http://uk.docs.yahoo.com/nowyoucan.html
