Large Random Numbers - Cryptography in C and C++ - page 264

prime to n .From X 0 := X 2 ( mod n ) , we obtain the start value X 0 for a sequence
of integers that we calculate by successive squaring modulo n :
X i +1 = X i mod n. (12.3)

As random numbers we remove from each value X i the least-significant bit.
We may thus make a formal description of the generator: The state set is denoted
by S := { 0 , 1 ,...,n− 1 }

, the random values are defined by R := { 0 , 1 }

,the
state transitions are described by the function φ : S → S , φ ( x )= x 2 mod n ,and
the output function is ψ : S → R ,with ψ ( x ):= x ( mod 2) .
A random sequence constructed of binary digits thus obtained can be
considered secure in the cryptographic sense: The ability to predict previous or
future binary digits from a portion of those that have already been calculated
is possible only if the factors p and q of the modulus are known. If these are
kept secret, then according to current knowledge, the modulus n must be
factored for one to be able to predict further bits of a BBS random sequence
with probability greater than 2 or to reconstruct unknown parts of the sequence.
The security of the BBS generator thus rests on the same principle as the RSA
procedure. The cost of such derived trust in the quality of the BBS generator
lies in the expense of generating random bits; for each bit, the squaring of a
number modulo a large integer is required, which is reflected in a large amount
of computation time for long sequences. This is of little consequence, however,
in the development of shorter sequences of random bits, such as for the creation
of a single cryptographic key. In such a case, the sole criterion is security, and in
evaluating security, one must take into account the procedure for obtaining start
values. Since the BBS generator is also a deterministic procedure, “fresh chance”
can be included only as described in the previous section via suitably obtained
start values.
With the aid of the function prime_l , prime numbers p ≡ q ≡ 3( mod 4)
are determined, both with approximately the same number of binary digits (this
results in the modulus being as difficult as possible to factor, and the security of
the BBS generator depends on this), and the modulus n = pq is created. 3
Beginning with the start value X 0 , the next numbers in the sequence
X i +1 = X i ( mod n ) are computed using the function SwitchRandBBS_l() , which
outputs as random bit the least-significant bit of X i +1 . The value X i +1 is stored
in a buffer as the current state of the generator, which is managed by the calling
function. We will return to the question of how this buffer is to be initialized
with a suitable start value with the first call to SwitchRandBBS_l() . But first let us
implement the function.

3

Several such moduli of various lengths are contained in the FLINT/C package, though without
the associated factors, which are known only to the author ;-).