Blum Blum Shub - Blum Blum Shub - Wikipedia

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (září 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek příliš spoléhá na Reference na primární zdroje. Vylepšete to přidáním sekundární nebo terciární zdroje. (září 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Blum Blum Shub (B.B.S.) je generátor pseudonáhodných čísel navržené v roce 1986 Lenore Blum, Manuel Blum a Michael Shub^[1] z čehož je odvozen Michael O. Rabin je jednosměrná funkce.

Blum Blum Shub má podobu

${ displaystyle x_ {n + 1} = x_ {n} ^ {2} { bmod {M}}}$,

kde M = pq je produktem dvou velkých připraví p a q. V každém kroku algoritmu je odvozen nějaký výstup X_n+1; výstup je obvykle buď bitová parita z X_n+1 nebo jeden nebo více nejméně významných bitů X_n+1.

The semínko X₀ by mělo být celé číslo, které je co-prime M (tj. p a q nejsou faktory X₀) a ne 1 nebo 0.

Dvě prvočísla, p a q, oba by měli být shodný až 3 (mod 4) (to zaručuje, že každý kvadratický zbytek má jednu odmocnina což je také kvadratický zbytek) a mělo by být bezpečné prvočísla s malým gcd ((p-3)/2, (q-3)/2) (tím se délka cyklu zvětší).

Zajímavou vlastností generátoru Blum Blum Shub je možnost vypočítat jakýkoli X_i hodnota přímo (přes Eulerova věta ):

${ displaystyle x_ {i} = left (x_ {0} ^ {2 ^ {i} { bmod { lambda}} (M)} right) { bmod {M}}}$,

kde ${ displaystyle lambda}$ je Funkce Carmichael. (Tady máme ${ displaystyle lambda (M) = lambda (p cdot q) = operatorname {lcm} (p-1, q-1)}$).

Bezpečnostní

Existuje důkaz snižující jeho bezpečnost na výpočetní obtížnost faktoringu.^[1] Jsou-li prvočísla vybrána vhodně, a Ó (log log M) bity nižšího řádu každého z nich X_n jsou na výstupu, pak v limitu jako M zvětšuje se, rozlišení výstupních bitů od náhodných by mělo být přinejmenším stejně obtížné jako řešení problému kvadratické reziduosity modulo M.

Příklad

Nechat ${ displaystyle p = 11}$, ${ displaystyle q = 23}$ a ${ displaystyle s = 3}$ (kde ${ displaystyle s}$ je semeno). Můžeme očekávat, že pro ty malé počty dostaneme velkou délku cyklu, protože ${ displaystyle { rm {gcd}} ((p-3) / 2, (q-3) / 2) = 2}$Generátor začne vyhodnocovat ${ displaystyle x_ {0}}$ používáním ${ displaystyle x _ {- 1} = s}$ a vytvoří sekvenci ${ displaystyle x_ {0}}$, ${ displaystyle x_ {1}}$, ${ displaystyle x_ {2}}$, ${ displaystyle ldots}$ ${ displaystyle x_ {5}}$ = 9, 81, 236, 36, 31, 202. Následující tabulka ukazuje výstup (v bitech) pro různé metody výběru bitů používané k určení výstupu.

Následující Společný Lisp implementace poskytuje jednoduchou ukázku generátoru, zejména pokud jde o metody výběru tří bitů. Je důležité si uvědomit, že požadavky kladené na parametry p, q a s (osivo) nejsou kontrolovány.

(defun get-number-of-1-bits (bity)  "Spočítá a vrátí počet bitů s jednou hodnotou v BITS."  (prohlásit (celé číslo bity))  (the unsigned-byte    (smyčka pro bitový index z 0 níže (celočíselná délka bity)          když (logbitp bitový index bity) součet 1)))(defun get-even-parity-bit (číslo)  "Vrátí sudý paritní bit ČÍSLA."  (prohlásit (celé číslo číslo))  (the bit (mod (get-number-of-1-bits číslo) 2)))(defun získat nejméně významný bit (číslo)  "Vrátí nejméně významný bit ČÍSLA."  (prohlásit (celé číslo číslo))  (the bit (ldb (byte 1 0) číslo)))(defun make-blum-blum-shub (&klíč (p 11) (q 23) (s 3))  "Vrátí funkci bez argumentů, která představuje jednoduchý   Generátor pseudonáhodných čísel Blum-Blum-Shub, nakonfigurovaný pro použití   parametry generátoru P, Q a S (seed) a vrácení tří hodnot:   (1) sudý paritní bit čísla,   (2) nejméně významný bit čísla,   (3) číslo x [n + 1].   ---   Pamatujte, že parametry P, Q a S nejsou ohlášeny   v souladu s podmínkami popsanými v článku. “  (prohlásit (typ celé číslo p q s))  (nechat ((M    (* p q))       ;; M = p * q        (x [n] s))            ;; x0 = semeno    (prohlásit (celé číslo M x [n]))    #'(lambda ()        ;; x [n + 1] = x [n] ^ 2 mod M        (nechat ((x [n + 1] (mod (* x [n] x [n]) M)))          (prohlásit (celé číslo x [n + 1]))          ;; Vypočítejte náhodné bity na základě x [n + 1].          (nechat ((sudý-parita-bit       (get-even-parity-bit       x [n + 1]))                (nejméně významný bit (získat nejméně významný bit x [n + 1])))            ;; Aktualizujte stav tak, aby se z x [n + 1] stalo nové x [n].            (setf x [n] x [n + 1])            (hodnoty sudý-parita-bit                    nejméně významný bit                    x [n + 1]))))));; Tisk příkladných výstupů.(nechat ((bbs (make-blum-blum-shub : str 11 : q 23 : s 3)))  (formát T "~ & Klávesy: E = sudá parita, ~                     L = nejméně významné ")  (formát T "~2%")  (formát T "~ & x [n + 1] | E | L")  (formát T "~&--------------")  (smyčka opakovat 6 dělat    (vázání více hodnot (sudý-parita-bit nejméně významný bit x [n + 1])        (funcall bbs)      (formát T "~ & ~ 6d | ~ d | ~ d"        x [n + 1] sudý-parita-bit nejméně významný bit))))

Reference

Všeobecné

• Blum, Lenore; Blum, Manuel; Shub, Mike (1982). "Porovnání dvou generátorů pseudonáhodných čísel". Pokroky v kryptologii: Sborník CRYPTO '82. Plénum: 61–78. Citovat deník vyžaduje | deník = (Pomoc)
• Geisler, Martin; Krøigård, Mikkel; Danielsen, Andreas (prosinec 2004). "O náhodných bitech". CiteSeerX  10.1.1.90.3779. Citovat deník vyžaduje | deník = (Pomoc) k dispozici jako PDF a gzipovaný Postskript

externí odkazy

• GMPBBS, implementace v jazyce C od Marka Rossmillera
• BlumBlumShub, implementace v jazyce Java od Marka Rossmillera
• Implementace v Javě
• Testy náhodnosti