>>Hal Finney <hal@rain.org> writes: >There are pseudo random
>>number generators which are believed to be >indistinguishable
>>from true random number generators even with all the >computing
>>power in the entire universe (by some definition).
>Wayne Hayes <wayne@cs.toronto.edu> Do you have a reference for
>this? The best ones that I've heard of that are purely
>algorithmic are the well-known linear congruential ones. They
>are hard to distinguish from truly random ones, but definitely
>not if you have "all the computing power in the universe".
To break a good random number generator like "Blum Blum Shub", you'd need to
factor the number that it uses as its seed and that would take a HUGE amount
of cleverness or a COSMIC amount of patience. If as is usually the case, the
seed is one or two thousand bits long, then that's far beyond the capacity
of any existing computer, if you make it 4 or 5 thousand bits long then you
will not be able to find enough silicon in the observable universe to make
enough chips for a computer to factor the it before the heat death of the
cosmos. Unless a new factoring algorithm is found that's a LOT faster than
anything we know about today, if it only speeded things up a trillion times
it would be useless, and unless somebody makes a Quantum Computer, Blum Blum
Shub is safe.
Even if you knew the seed number I used in my generator, I could give you a
sequence produced by it and you couldn't even say there is a 51% chance that
the next bit in the sequence will be a 1, nor could you know anything about
the bit previous to the sequence I gave you.
There is a lot about random number generators in Bruce Schneier's book
"Applied Cryptography".
John K Clark johnkc@well.com
-----BEGIN PGP SIGNATURE-----
Version: 2.6.i
iQCzAgUBNGdfDX03wfSpid95AQEbgATwjN2CBJ0Ui2SrQ+WazDV7pO6EJzDAtTSC
8oVync2xkhgd3yaLsHH315NexPwUBHC/PKHTtAdXofO1shrnTFTZVve5dzYIoBOu
512bfTzggNCN8HKNk49jcFZqyfBu4Qw34G0Trajlr0RgIvbvOs9z8WTLbBNxkoMA
e0czcjOINB2U1KClpnmwAmqOOOSwul1BYP9ZnjwW2Bn8QJ//osA=
=ZMdr
-----END PGP SIGNATURE-----