Ž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ą:
X0 = s2 mod n
for i = 1 to ∞
Xi = (Xi-1)2 mod n
Bi = Xi 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.