Re: Mersenne Twister

From: Unruh (unruh-spam_at_physics.ubc.ca)
Date: 07/17/05 

Date: 17 Jul 2005 17:03:35 GMT

"Cristiano" <cristiano.pi@NSquipo.it> writes:

>Unruh wrote:
>>
>> A random source cannot be predicted. And no PRNG is unpredictable.
>> Just give me the algorithm and the (short) key and I can predict it
>> forever.

>Eh! Eh! If I use a CPRNG I will keep secret the key!
>You'll try to break the generator without any knowledge of the key.

>> Now, can I figure out how to predict it just given the output alone?
>> I do not know but I do know that there are very very strong patterns
>> in the output based on the fact that it is generated by a PRNG.

>Are you sure? I'd say that the patterns are very very weak because it's very
>hard to write a test which is able to find a pattern.
>Even if you test many Gbits of a CPRNG using the most effective tests, you
>don't see any pattern.

Yes, I will. It is called the algorithm which is itself a test, with an
unknown element, the key. Since the key is far far shorter than the stream
I have, that key with the algorithm defines a pattern.
Now I agree that it is not easy to find that pattern. It takes perhaps
something like 2^128 attempts, but once I have found it the pattern is
completely predictable and deterministic, and can be extended to an
arbitrarily large piece of output.

Or to use the Chaitin/Kolmogorov definition of randomness, the output is
entirely non-random. The length of the shortest program (the algorithm plus
the key) is far far shorter than the output.
And no matter which sample I take, this is always true for that PRNG. Ie,
even the average length of the program required to output a large number of
samples is far shorter than the output (whcih is not true of a true RNG)

>Cristiano

Relevant Pages

  • Re: New Encryption Idea
    ... long before the 66.7 years you have claimed, this is a very real security ... so your algorithm is at best redundant. ... > time (it can take more in the MEAS encryption mode). ... RSA won't have the pRNG requirements ...
    (sci.crypt)
  • Re: your assistance is requested
    ... I take this proof that chicks don't know shit about computers? ... Park-Miller PRNG has an even smaller range of internal states, ... and the RC5 algorithm is far more involved ... should try to publish in a crypto conference or journal. ...
    (comp.compression)
  • Re: Serialize a Strategy Pattern List of objects with out xsi:type
    ... whether this is a strategy pattern or not. ... depends on how you define algorithm. ... As for your "secondly" comment about homework, ... suggest that you create a seperate class that you will serialize. ...
    (microsoft.public.dotnet.framework)
  • Re: Reading and writing a big file in Ada (GNAT) on Windows XP
    ... memory for a substring; this is very descriptively called memmemand ... common cases (no mapping, single character patterns, and so on). ... So in this case a better algorithm is probably the way to go (and I ... the source length is>M and the pattern length is>N, ...
    (comp.lang.ada)
  • Re: Alternative rand()-algorithm?
    ... > But you, or any competent attacker, could find out with little ... > matter of iterating the shuffling algorithm through seed values. ... And each output from that PRNG will leak some of that state. ... > Periodic reseeding compensates for the entropy lost in the PRNG ...
    (comp.lang.c)
Quantcast