Libraries for Vicare Scheme: random generators bbs

49.8.3 Blum–Blum–Shub generator

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 (vicare crypto 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.

Function: make-random-source/blum-blum-shub

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 numbers.

The random-source-seed! function for this generator, must be applied to a numbers maker returning:

The value of the prime number P.
The value of the prime number Q.
Integers numbers until one is found whose GCD with P * Q is 1.

see the algorithm details below.

The algorithm

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:

Select two prime numbers P and Q and compute M = P * Q, which will be the modulus of the internally generated integers. These primes are the “secret” of the generated sequence of pseudo–random integers; for cryptographic purposes they have to be kept hidden.
Generate (using another PRNG) random integers S until one is found such that: The greatest commond divisor (GCD) between S and M is 1. Notice that R6RS Scheme implementations already provide a gcd function. (vicare-scheme)Arithmetic operations.
Compute the seed X:
```
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.