From: Hal <hfinney@shell.portal.com>
Date: Mon, 2 May 94 10:09:36 PDT
To: cypherpunks@toad.com
Subject: Re:  Blum-Blum-Shub source?
Message-ID: <199405021710.KAA04820@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


The Blum-Blum-Shub PRNG is really very simple.  There is source floating
around on the crypto ftp sites, but it is a set of scripts for the Unix
bignum calculator "bc", plus some shell scripts, so it is not very port-
able.

To create a BBS RNG, choose two random primes p and q which are congruent
to 3 mod 4.  Then the RNG is based on the iteration x = x*x mod n.  x is
initialized as a random seed.  (x should be a quadratic residue, meaning
that it is the square of some number mod n, but that can be arranged by
iterating the RNG once before using its output.)

The only questionable part about the RNG is how many bits of x to use per
iteration.  The original BBS paper proved that the RNG was secure if you used
just the LSB of x each time.  Later there was a proof that you could use
log-base-two of the number of bits of n bits each time; if n were 512 bits
then you could use 9 bits per iteration.  Some time back I saw a claim on
sci.crypt that you could use up to 1/3 of the bits each time safely, but I
don't think that was proven.

Hal