6.2.2. The Blum Blum Shub Sequence Generator (Der Blum Blum Shub Sequenzgenerator)

6.2.2. The Blum Blum Shub Sequence Generator (Der Blum Blum Shub Sequenzgenerator)

Derzeit ist der Generator mit dem stärksten öffentlichen Beweis der Stärke der Blum Blum Shub Generator, benannt nach seinen Erfindern [BBS]. Er ist auch sehr einfach und basiert auf quadratischen Resten. Sein einziger Nachteil ist, dass er im Vergleich zu den traditionellen Techniken in Abschnitt 6.1.3 rechnerisch intensiv ist. Dies ist kein großer Nachteil, wenn er für mäßig seltene Zwecke verwendet wird, wie z.B. die Generierung von Sitzungsschlüsseln.

Wählen Sie einfach zwei große Primzahlen (sagen wir, p und q), die jeweils einen Rest von 3 ergeben, wenn sie durch 4 geteilt werden. Sei n = p * q. Wählen Sie dann eine Zufallszahl x, die relativ prim zu n ist. Der anfängliche Seed für den Generator und die Methode zur Berechnung nachfolgender Werte sind dann:

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

Seien Sie vorsichtig, nur ein paar Bits vom unteren Ende jedes s zu verwenden. Es ist immer sicher, nur das niedrigstwertige Bit zu verwenden. Wenn man nicht mehr als die:

   log  ( log  ( s  ) )
      2      2    i

niederwertigsten Bits verwendet, dann ist das Vorhersagen zusätzlicher Bits aus einer auf diese Weise generierten Sequenz nachweislich so schwer wie das Faktorisieren von n. Solange das anfängliche x geheim ist, kann n bei Bedarf öffentlich gemacht werden.

Eine interessante Eigenschaft dieses Generators ist, dass jeder der s-Werte direkt berechnet werden kann. Insbesondere:

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

Dies bedeutet, dass in Anwendungen, bei denen viele Schlüssel auf diese Weise generiert werden, es nicht notwendig ist, sie alle zu speichern. Jeder Schlüssel kann effektiv indiziert und aus diesem kleinen Index und dem anfänglichen s und n wiederhergestellt werden.