Blum Blum Shub

Blum Blum Shub ( BBS ) to generator liczb pseudolosowych zaproponowany w 1986 roku przez Lenore Blum , Manuela Bluma i Michaela Shuba , który wywodzi się z funkcji jednokierunkowej Michaela O. Rabina .

Blum Blum Shub przybiera formę

{\ Displaystyle x_ {n + 1} = x_ {n} ^ {2} {\ bmod {M}}}

,

gdzie M = pq jest iloczynem dwóch dużych liczb pierwszych p i q . Na każdym etapie algorytmu część danych wyjściowych pochodzi z x _{n +1} ; wyjściem jest zwykle albo parzystość bitów x _{n +1} albo jeden lub więcej najmniej znaczących bitów x _{n +1} .

₀ Ziarno x powinno być liczbą całkowitą, która jest względnie pierwszą względem M (tzn. p i q nie są czynnikami x ), a nie 1 lub 0 . ₀

Dwie liczby pierwsze, p i q , powinny być przystające do 3 (mod 4) (to gwarantuje, że każda reszta kwadratowa ma jeden pierwiastek kwadratowy , który jest również resztą kwadratową) i powinny być bezpiecznymi liczbami pierwszymi z małym gcd (( p- 3 ) /2 , ( q-3 ) /2 ) (sprawia to, że długość cyklu jest duża).

Ciekawą cechą generatora Blum Blum Shub jest możliwość bezpośredniego obliczenia dowolnej wartości x _i (poprzez twierdzenie Eulera ):

{\ Displaystyle x_ {i} = \ lewo (x_ {0} ^ {2 ^ {i} {\ bmod {\ lambda}} (M)} \ prawo){\bmod {M}}}

,

gdzie jest funkcją $_$ . (Tutaj mamy ${\ Displaystyle \ lambda (M) = \ lambda (p \ cdot q) = \ operatorname {lcm} (p-1,q-1)}$ ).

Bezpieczeństwo

Istnieje dowód redukujący jego bezpieczeństwo do trudności obliczeniowej faktoryzacji. Kiedy liczby pierwsze są odpowiednio dobrane i O ( log log M ) bitów niższego rzędu każdego x _n , to w limicie, gdy M rośnie, odróżnienie bitów wyjściowych od losowych powinno być co najmniej tak trudne, jak rozwiązanie kwadratu problem resztkowy modulo M .

Przykład

Niech ${\ displaystyle p = 11}$ , ${\ displaystyle q = 23}$ i ${\ displaystyle$ $s = 3}$ (gdzie ziarno). Możemy spodziewać się dużej długości cyklu dla tych małych liczb, ponieważ $Displaystyle {\ rm {gcd}} ((p -3)/2,(q-3)/2)=2}$ . Generator zaczyna oceniać za pomocą $Displaystyle x_$ ${-1} = s}$ i tworzy sekwencję ${\ displaystyle x_ {0}}$ x $\ displaystyle x_ {1}}$ , ${\ Displaystyle x_ {2}}$ , ${\ Displaystyle \ ldots}$ ${\ Displaystyle x_ {5}}$ = 9, 81, 236, 36, 31, 202. tabela przedstawia dane wyjściowe (w bitach) dla różnych metod wyboru bitów używanych do określania danych wyjściowych.

Bit parzystości	Najmniej znaczący bit
0 1 1 0 1 0	1 1 0 0 1 0

Poniższa implementacja Common Lisp zapewnia prostą demonstrację generatora, w szczególności w odniesieniu do metod wyboru trzech bitów. Należy zauważyć, że wymagania nałożone na parametry p , q i s (ziarno) nie są sprawdzane.

  
  
     0  
    0   

  
  
     0  
       

  
  
     0  
       0 

        
  








     0    
                
                     
       0   
     
        
              
             0  
          
                         
                  
               
               
            
              
             
                    
                    


        
        0    
    
    
    
    
     
       
         
         0  
                   
                   
        
                   (  defun  get-number-of-1-bits  (  bits  )  "Zwraca liczbę bitów o wartości 1 w BITS-ach zakodowanych liczbami całkowitymi."  (  deklaracja  (  typ  (  liczba  całkowita  *  )  bity  ))  (  liczba  całkowita  *  )  (  liczba logów  bity  )))  (  defun  get-even-parity-bit  (  bits  )  "Zwraca bit parzystości BITÓW zakodowanych w liczbach całkowitych."  (  deklaracja  (  typ  (  liczba  całkowita  *  )  bity  ))  (  bit  (  mod  (  pobierz liczbę -z-1-bitów bitów  )  2  )  ))  (  defun  get-least-significant-bit  (  bits  )  "Zwraca najmniej znaczący bit z bitów zakodowanych w liczbach całkowitych."  (  deklaracja  (  typ  (  liczba całkowita  *  )  bitów  ))  (  bit  (  ldb  (  bajt  1  )  bity  )))  (  defun  make-blum-blum-shub  (  &key  (  p  11  )  (  q  23  )  (  s  3  ))  "  Zwraca funkcję bez argumentów, która reprezentuje prosty  Blum-Blum - Shub generator liczb pseudolosowych, skonfigurowany do używania  parametrów generatora P, Q i S (seed) i zwracający trzy wartości:  (1) liczbę x[n+1],  (2) bit parzystości liczby,  (3) najmniej znaczący bit liczby.  ---  Należy pamiętać, że parametry P, Q i S nie są sprawdzane zgodnie  z warunkami opisanymi w artykule."  (  deklaracja  (  typ  (  liczba całkowita  *  )  p  q  s  ))  (  niech  ((  M  (  *  p  q  ))  ;; M = p * q   (  x[n]  s  ))  ;; x0 = seed   (  deklaracja  (  typ  (  liczba całkowita  *  )  M  x[n]  ))  #'  (  lambda  ()  ;; x[n+1] = x[n]^2 mod M  (  niech  ((  x[n+1) ]  (  mod  (  *  x[n]  x[n]  )  M  )))  (  deklaracja  (  typ  (  liczba całkowita  *  )  x[n+1]  ))  ;; Oblicz losowy bit(y) na podstawie x[n+1 ].  (  let  ((  bit parzystości-parzystości  (  get-bit-parzystości-parzystości  x[n+1]  ))  (  bit najmniej-znaczący  (  bit-najmniej-znaczący- bit  x[n+1]  )))  (  deklaruj  (  wpisz  bit bit  -parzystości  ))  (  deklaruj  (  wpisz  bit  najmniej-znaczący-bit  ))  ;;Zaktualizuj stan tak, aby x[n+1] stało się nowym x[n].  (  setf  x[n ]  x[n+1]  )  (  wartości  x[n+1]  bit parzystości  najmniej znaczący bit  ))))))  ;; Wydrukuj przykładowe wyjścia.   (  niech  ((  bbs  (  make-blum-blum-shub  :p  11  :q  23  :s  3  )))  (  deklaracja  (  typ  (  funkcja  ()  (  wartości  (  liczba całkowita  *  )  bit  bit  ))  bbs  ))  (  format  T  " ~&Klucze: E = parzystość, L = najmniej znacząca"  )  (  format  T  "~2%"  )  (  format  T  "~&x[n+1] | E | L"  )  (  format  T  "~&---- ----------"  )  (  powtórzenie  pętli  6  do  (  wiązanie wielu wartości  (  x[n+1]  najmniej znaczący bit  parzystości  )  (  funcall  bbs  )  (  deklaracja  (  typ  (  liczba całkowita  *  )  x[n+1]  ))  (  zadeklaruj  (  wpisz  bit bit  -parzystości  ))  (  zadeklaruj  (  wpisz  bit  najmniej znaczący bit  ))  (  format  T  "~&~6d | ~d | ~d"  x[n+1]  bit parzystości  najmniej znaczący bit  ))))

Cytaty

Źródła

Blum, Lenore; Blum, Manuel; Shub, Michael (1983). „Porównanie dwóch generatorów liczb pseudolosowych” . Postępy w kryptologii . Boston, MA: Springer USA. s. 61–78. doi : 10.1007/978-1-4757-0602-4_6 . ISBN 978-1-4757-0604-8 .
Blum, L.; Blum, M.; Shub, M. (1986). „Prosty, nieprzewidywalny generator liczb pseudolosowych” (PDF) . SIAM Journal o informatyce . Towarzystwo Matematyki Przemysłowej i Stosowanej (SIAM). 15 (2): 364–383. doi : 10.1137/0215025 . ISSN 0097-5397 . Zarchiwizowane (PDF) od oryginału w dniu 2021-08-14.
Geisler, Martin; Krøigård, Mikkel; Danielsen, Andreas (grudzień 2004), About Random Bits (PDF) , CiteSeerX 10.1.1.90.3779 , zarchiwizowane (PDF) z oryginału w dniu 31.03.2016

Linki zewnętrzne