Žodis angliškai
Pseudorandom number generator
Santrumpa
PRNG
Žodis Lietuviškai
Pseudoatsitiktinių skaičių generatorius
Apibrėžimas
Kriptografijoje taip vadinamas deterministinius algoritmus naudojantis generatorius pseudoatistiktinių skaičių sekų sudarymui.
Paaiškinimai
Daugybė tinklo saugos algoritmų ir protokolų paremtų kriptografija naudoja atsitiktinius binarinius skaičius. Pavyzdžiui:
* Rakto dalinimas ir autentifikacija. Dvi komunikuojančios pusės kooperuoja dalindamosi žinutėmis siekiant perduoti raktą ar autetifikuoti viena kitą. Tokiais atvejais nonces (vienkartiniai atsitiktiniai skaičiai) yra panaudojami kaip vienas iš hash funkcijos paramterų.
* Sesijos rakto generavimas.
* Raktų generavimui RSA atviro rakto šifravimo algoritmui.
* Generavimui bitų srauto simetriniam srauto šifravimui.
Du svarbūs reikalavimai atsitiktinių skaičių sekai: atsitiktinumas ir nenuspėjamumas.
Atsitiktinumui įvertinti naudojami pagrinde du kriterijai:
* vienodas pasiskirstymas – t.y. 1 ir 0 dažnis sekoje turi būti maždaug lygus
* nepriklasomumas – jokia sekos dalis negali būti panaudota nuspėjimui kitų dalių.
Nenuspėjamumas – tai ne tik, kad atsitiktiniai skaičiai yra statistiškai atistiktiniai, bet ir kad visi sekantys sekos nariai yra nenuspėjamai. T.y tikrai atsitiktinė seka, yra tada kai kiekvienas skaičius yra statistiškai nepriklausomas nuo kitų skaičių. Tačiau tokios „tikros“ atsitiktinės sekos retai naudojamos. Dažniau naudojamos skaičių sekos, kurios atrodo atsitiktinės.
Kriptografijoje dažnai naudojami deterministiniai algoritmai pseudoatistiktinių skaičių generavimui. Taigi sekos nėra statistiškai atsitiktinės, tačiau gali praeiti daugumą atsitiktinumo testavimų. Tokių sekų generatorius kriptografijoje vadinama pseudoatsitiktinių skaičių generatorius (PRNG). PRNG įėjime gauna fiksuotą reikšmę, vadinamą seed (grūdas), ir generuoja išėjime seką bitų naudojant deterministinį algoritmą. Dažniausiai yra grįžtamasis ryšys – algoritmo rezultatai yra perduodami į įėjimą, kai papildomi išėjimo bitai yra generuojami. Svarbiausia yra tai, kad oponentas žinodamas algoritmą ir seed gali atgaminti visą bitų srautą.
Naudota literatūra
William Stallings. Cryptography and Network Security. Principles and Practice. New York, 2011.