Next: random generators borosh, Previous: random generators marsaglia, Up: random generators [Index]

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 value of the prime number

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

Next: random generators borosh, Previous: random generators marsaglia, Up: random generators [Index]