[11246] in cryptography@c2.net mail archive
Re: building a true RNG
daemon@ATHENA.MIT.EDU (Matt Crawford)
Mon Jul 29 19:53:34 2002
Date: Mon, 29 Jul 2002 15:47:48 -0500
From: Matt Crawford <crawdad@fnal.gov>
In-reply-to: "29 Jul 2002 13:37:49 EDT." <3D457D6D.E414C051@monmouth.com>
To: "John S. Denker" <jsd@monmouth.com>
Cc: David Wagner <daw@mozart.cs.berkeley.edu>,
cryptography@wasabisystems.com, Barney Wolff <barney@tp.databus.com>
2) I can't prove that a standard hash function such as SHA1
generates all possible codes, but I consider it likely. It would
be quite shocking if a strong hash function such as SHA1 generated
fewer codes than a weak function such as H0.
I think you could do a probabilistic proof similar to the "DES is not
a group" quasi-proof. To test a hash function h() whose range is S,
let F be the set of "balanced" functions from S -> {0, 1}. (Balanced
meaning that each f in F maps exactly half of S to 0 and half to 1.)
If you can contrive to choose many members of F at random, and compose
them with h for many arguments of h, you should be able to set
confidence limits on how much of S is covered by h.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
