6.2.2. The Blum Blum Shub Sequence Generator (Il Generatore di Sequenze Blum Blum Shub)

6.2.2. The Blum Blum Shub Sequence Generator (Il Generatore di Sequenze Blum Blum Shub)

Attualmente il generatore che ha la prova pubblica di robustezza più forte è chiamato generatore Blum Blum Shub, dal nome dei suoi inventori [BBS]. È anche molto semplice ed è basato su residui quadratici. Il suo unico svantaggio è che è computazionalmente intensivo rispetto alle tecniche tradizionali date nella Sezione 6.1.3. Questo non è uno svantaggio importante se viene usato per scopi moderatamente non frequenti, come la generazione di chiavi di sessione.

Semplicemente scegliere due grandi numeri primi (diciamo, p e q) che ciascuno dà un resto di 3 quando diviso per 4. Sia n = p * q. Poi scegliere un numero casuale, x, che è relativamente primo a n. Il seed iniziale per il generatore e il metodo per calcolare i valori successivi sono quindi:

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

Bisogna fare attenzione a usare solo pochi bit dalla parte inferiore di ogni s. È sempre sicuro usare solo il bit di ordine più basso. Se si usano non più dei

     log  ( log  ( s  ) )
        2      2    i

bit di ordine basso, allora prevedere qualsiasi bit aggiuntivo da una sequenza generata in questo modo è dimostrabilmente difficile quanto fattorizzare n. Finché l'x iniziale è segreto, n può essere reso pubblico se desiderato.

Una caratteristica interessante di questo generatore è che qualsiasi dei valori s può essere calcolato direttamente. In particolare,

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

Questo significa che nelle applicazioni dove molte chiavi sono generate in questo modo, non è necessario salvarle tutte. Ogni chiave può essere efficacemente indicizzata e recuperata da quell'indice piccolo e dall's e n iniziali.