6.2.2. The Blum Blum Shub Sequence Generator

Currently the generator which has the strongest public proof of strength is called the Blum Blum Shub generator, named after its inventors [BBS]. It is also very simple and is based on quadratic residues. Its only disadvantage is that it is computationally intensive compared to the traditional techniques given in Section 6.1.3. This is not a major drawback if it is used for moderately-infrequent purposes, such as generating session keys.

Simply choose two large prime numbers (say, p and q) that each gives a remainder of 3 when divided by 4. Let n = p * q. Then choose a random number, x, that is relatively prime to n. The initial seed for the generator and the method for calculating subsequent values are then:

              2
   s    =  ( x  )(Mod n)
    0
              2
   s    = ( s   )(Mod n)
    i+1      i

Be careful to use only a few bits from the bottom of each s. It is always safe to use only the lowest-order bit. If one uses no more than the:

   log  ( log  ( s  ) )
      2      2    i

low-order bits, then predicting any additional bits from a sequence generated in this manner is provably as hard as factoring n. As long as the initial x is secret, n can be made public if desired.

An interesting characteristic of this generator is that any of the s values can be directly calculated. In particular,

         ( (2^i) (Mod ((p-1)*(q-1)) ) )
s  = ( s                                )(Mod n)
 i      0

This means that in applications where many keys are generated in this fashion, it is not necessary to save them all. Each key can be effectively indexed and recovered from that small index and the initial s and n.