Cryptography

From: John K Clark (johnkc@well.com)
Date: Fri Dec 27 1996 - 23:18:34 MST


-----BEGIN PGP SIGNED MESSAGE-----

On Sun, 22 Dec 1996 Lyle Burkhead <LYBRHED@delphi.com> Wrote:

>James Rogers:
>A good pseudo-random number generator is indistinguishable
>from a true set of random numbers. [...] The output has a
>totally white spectrum. The only thing that makes it
>"pseudorandom" is that it is generated deterministically.
>The output is indistinguishable from non-deterministic
>random noise.
                  
>Lyle Burkhead <LYBRHED@delphi.com>
>Is that a theorem?
                

No.
                  
>I could be wrong, but my mathematical common sense tells me
>that each algorithm leaves some kind of fingerprint, and
>distinguishing between them is just a matter of cleverness
>and patience.
                  
In theory you could, in practice you could not, at least not unless you had a
HUGE amount of cleverness or a COSMIC amount of patience. To break a good
random number generator like Blum Blum Shub, the one that PGP uses, you would
need to factor the number that it uses as its seed. If as is usually the case,
the seed is one or two 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 it before the heat death of the universe. Unless a new factoring
algorithm was found that is a LOT faster than anything we know about today,
if it only speeded thing 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 this generator 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 a bit previous to the sequence I gave you.

                                             John K Clark johnkc@well.com

-----BEGIN PGP SIGNATURE-----
Version: 2.6.i

iQCzAgUBMsTAfH03wfSpid95AQFzlgTuKYlJ0ZOWsjwZsrilPz18N/9UALWaWXA4
UV6C3o6UQmJMsaa9Jz+b9XY8IDkDtXJgf4stvn7ankJo3iCrS8HHGrfXIm1YGmHd
+aRxleplYUSy9QAVnF9MdBH6ZhiegKkiqe0BkTr1Zn+8yiuOGaELlL4Or58fVNJr
BCHyWVuX/Yiku0c3iHZsZf3jqWTpUECbQvpYQEkSt2mFLcTGuiU=
=0NZZ
-----END PGP SIGNATURE-----



This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:35:56 MST