Using SHA1 as RNG

[Gareth McCaughan]

Paul Foley wrote:
>  On Fri, 14 Mar 2003 18:14:12 +0000 (UTC), Klaus Alexander Seistrup wrote:
>  
> > It is probably quite expensive to use the sha module for shuffling
> > the bits, but the resulting period is huge.
>  
>  How do you know what the period is?  What makes you think it doesn't
>  depend on the seed?  [I.e., for some seed, it may only produce a
>  single value continuously].

Suppose f is the SHA-1 hash function and you calculate
f(x), f(f(x)), f(f(f(x))), etc. And suppose this sequence
repeats after N iterations. Then, after N trials, you
have found either something that maps to x under SHA-1
or else two things that map to the same place. If N is
much less than the square root of the number of possible
SHA-1 values -- i.e., if N is much less than 2**80 --
then SHA-1 is broken with high probability :-).

Another way to use a cryptographic hash function to generate
random numbers is to calculate f(0), f(1), f(2) and so on.
This has some advantages: you can revisit any set of old
values you like without having to start at the beginning
and recalculate them all, and you can start several sequences
off in different places and know how long it will be until
any sequence starts reproducing any other.

Using the Mersenne Twister that will be in Python 2.3
is, as others have said, probably a better approach in
practice. :-)

-- 
Gareth McCaughan  Gareth.McCaughan at pobox.com
.sig under construc