Blum–Blum–Shub is a PRNG proposed in:
Lenore Blum, Manuel Blum, Michael Shub. “A Simple Unpredictable Pseudo–Random Number Generator”, SIAM Journal on Computing, volume 15, page 364-383, May 1986.
when seeded with prime numbers satisfying the specified requirements, it can be considered a cryptographically secure PRNG. The search of such prime numbers is a delicate and complex task; we have to turn to specialised literature to learn how to do it.
The following bindings are exported by the
randomisations blum-blum-shub) library. The library makes no attempt to
validate the seed numbers for the cryptographic requirements, it just
implements the PRNG algorithm; attaining cryptographic
security is entirely on our shoulders.
Build and return a new randomness source using the BBS generator. The returned randomness source is not seeded; this is because seeding a cryptographically secure generator must be done with care, and it makes no sense to have a default seed. The first operation after the creation of the source should be to seed it.
The state returned by
random-source-state-ref is a Scheme vector
of length 5, whose first value is the symbol
random-source-state/blum-blum-shub. The other values are integer
random-source-seed! function for this generator, must be
applied to a numbers maker returning:
see the algorithm details below.
BBS generates a sequence of bits, not of numbers. Bits can be concatenated to yield numbers of any sort in base 2. Seeding goes like this:
gcdfunction. (vicare-scheme)Arithmetic operations.
X = (S * S) mod M
The generator in
(vicare crypto randomisations blum-blum-shub)
computes a new integer N representable with 32 bits, from
an initial state X with the following formulation:
X0 = (X * X) mod M b0 = parity(X0) X1 = (X0 * X0) mod M b1 = parity(X1) X2 = (X1 * X1) mod M b2 = parity(X2) ...
where b(k) are the bits of N, with 0 <= k < 32, and X32 is the new state of the generator. The function parity(X) is the number of bits set to 1 in X, modulo 2.