6.2.2. The Blum Blum Shub Sequence Generator (Le générateur de séquence Blum Blum Shub)

6.2.2. The Blum Blum Shub Sequence Generator (Le générateur de séquence Blum Blum Shub)

Actuellement, le générateur qui a la preuve publique la plus forte de solidité est appelé le générateur Blum Blum Shub, nommé d'après ses inventeurs [BBS]. Il est également très simple et est basé sur les résidus quadratiques. Son seul inconvénient est qu'il est intensif sur le plan calculatoire par rapport aux techniques traditionnelles données dans la Section 6.1.3. Ce n'est pas un inconvénient majeur s'il est utilisé pour des fins modérément peu fréquentes, telles que la génération de clés de session.

Choisissez simplement deux grands nombres premiers (disons, p et q) qui donnent chacun un reste de 3 lorsqu'ils sont divisés par 4. Soit n = p * q. Ensuite, choisissez un nombre aléatoire, x, qui est relativement premier avec n. La graine initiale pour le générateur et la méthode pour calculer les valeurs subséquentes sont alors:

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

Faites attention de n'utiliser que quelques bits du bas de chaque s. Il est toujours sûr d'utiliser seulement le bit de poids le plus faible. Si on n'utilise pas plus que le:

     log  ( log  ( s  ) )
        2      2    i

bits de poids faible, alors prédire tout bit supplémentaire à partir d'une séquence générée de cette manière est prouvablement aussi difficile que de factoriser n. Tant que le x initial est secret, n peut être rendu public si désiré.

Une caractéristique intéressante de ce générateur est que n'importe laquelle des valeurs s peut être directement calculée. En particulier,

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

Cela signifie que dans les applications où de nombreuses clés sont générées de cette façon, il n'est pas nécessaire de toutes les sauvegarder. Chaque clé peut être effectivement indexée et récupérée à partir de ce petit index et des s et n initiaux.