= Žodis angliškai =
Blum Blum Shub Generator

== Santrumpa ==
BBS

== Žodis Lietuviškai ==
Blum Blum Shub (BBS) generatorius
----
== Apibrėžimas ==

Kriptografijoje taip vadinamas deterministinis algoritmas pseudoatistiktinių skaičių sekų sudarymui.

----
== Paaiškinimai ==

Populiarus būdas generuoti saugius pseudoatsitiktinius skaičius yra žinomas kaip Blum, Blum, Shub (BBS) generatorius. Jis turi vieną stipriausią atvirą įrodymą apie jo kriptografinį stiprumą.

Pirma, pasirenkami du dideli pirminiai skaičiai, p ir q, kad abu turėtų liekaną 3 dalijant iš 4:

p≡q≡3(mod 4)

Toks užrašymas reiškia (p mod 4)=(q mod 4)=3. Pavyzdžiui pirminiai skaičiai 7 ir 11 tenkina šią lygtį 7≡11≡3(mod 4). Tarkim n=p X q. Toliau parenkamas atsitiktinis skaičius s, taip, kad s yra reliatyviai pirminis n atžvilngiu, t.y. nei p nei q yra kartotiniai s. Tada BBS generatorius generuoja seką bitų B_i pagal algoritmą:

X,,0,,  = s^2^  mod n

for i = 1 to ∞

X,,i,,  = (X,,i,,-1)^2^  mod n

B,,i,,  = X,,i,,  mod 2

Pavyzdiniai parametrai algoritmo būtų n = 192649 = 383 X 503, ir pradinis skaičius seed s = 101355.

BBS yra žinomas kaip kriptografiškai saugus pseudoatsitiktinis bitų generatorius (CSPRBG). CSPRG yra apibrėžiamas kaip išlaikantis sekančio bito testą, kuris apibrėžiamas kaip: pseudoatsitiktinis bitų generatorius yra sakoma išlaikantis sekančio bito testą, jeigu nėra tokio polinominio laiko algoritmo, kuriam perdavus pirmus k bitus generuojamos sekos, galima nuspėsti (k+1) bitą didesne tikimybe nei 1/2. 

BBS saugumas yra pagrįstas n kartotinių radimo sunkumu. Taigi oponentas gali gauti n ir jam reikia nustatyti du pirminius kartotinius p ir q. Priklausomai nuo šios užduoties sunkumo, atitinkamai BBS yra saugus.

 .
----
== Naudota literatūra ==

William Stallings. Cryptography and Network Security. Principles and Practice. New York, 2011.

----
 . CategoryŽodis