Generiranje slučajnih nizova sa zadanim vjerojatnosnim zakonom i provjera njihove adekvatnosti jedan su od najvažnijih problema moderne kriptologije. Generatori slučajnog niza koriste se u postojećim kriptosustavima za generiranje ključnih informacija i postavljanje niza parametara kriptosustava. Znanstveni i praktični značaj ovog problema toliko je velik da su mu posvećene zasebne monografije iz područja kriptologije, organizirane su sekcije u znanstvenim časopisima "Journal of Cryptology", "Cryptologia" i posebna predavanja na međunarodnim znanstvenim skupovima "Eurocrypt", "Asiacrypt", "Crypto" itd.

Početkom 20. stoljeća slučajni nizovi simulirani su pomoću najjednostavnijih slučajnih eksperimenata: bacanje novčića ili kocke, izvlačenje kuglica iz urne, postavljanje karata, rulet itd. L. Tippett je 1927. godine prvi objavio tablice koje sadrže preko 40.000 slučajni brojevi, "nasumično izvučeni iz popisnih izvješća." Godine 1939., pomoću posebno dizajnirane mehaničke naprave - generatora slučajnih brojeva, M. J. Kendall i B. Babington-Smith izradili su tablicu koja je sadržavala 10 5 slučajnih brojeva. Godine 1946. američki matematičar John von Neumann prvi je predložio računalni algoritam za generiranje slučajnih brojeva. Godine 1955. RAND Corporation objavila je široko popularne tablice koje sadrže 10 6 računalno generiranih nasumičnih brojeva.

Trenutno je potražnja za generatorima slučajnih nizova sa zadanom distribucijom vjerojatnosti, kao i za samim slučajnim nizovima, toliko porasla da su se u inozemstvu pojavile istraživačke i proizvodne tvrtke koje proizvode i prodaju velike nizove slučajnih brojeva. Primjerice, od 1996. godine diljem svijeta distribuira se kompaktni disk “The Marsaglia random number CDROM” koji sadrži 4,8 milijardi “istinski nasumičnih” bitova.

Velika većina modernih kriptografskih sustava koristi ili tokovne ili blokovne algoritme temeljene na različitim vrstama zamjenskih i permutacijskih šifri. Nažalost, gotovo svi algoritmi koji se koriste u stream kriptosustavima namijenjeni su za korištenje u vojnim i vladinim komunikacijskim sustavima, kao iu nekim slučajevima za zaštitu komercijalnih informacija, što ih sasvim prirodno čini tajnim i nedostupnim za pregled. Jedini standardni algoritmi za simetričnu enkripciju toka su američki DES standard (CFB i OFB modovi) i ruski standard GOST 28147-89 (gama mod).

Osnova za funkcioniranje tokovnih kriptosustava su generatori slučajnih ili pseudoslučajnih nizova. Razmotrimo ovo pitanje detaljnije.

2 Generator pseudoslučajnih brojeva

Tajni ključevi predstavljaju osnovu kriptografskih transformacija, za koje je, prema Kerkhoffsovom pravilu, snaga kriptosustava određena samo tajnošću ključa. Dugo je glavni problem klasične kriptografije bila poteškoća generiranja tajnog ključa. Fizičko modeliranje slučajnosti korištenjem fizičkih pojava kao što su radioaktivno zračenje ili šum pucnjave u vakuumskoj cijevi prilično je teško i skupo, a korištenje pritisaka na tipke i pokreta miša zahtijeva napor korisnika i također ne pruža potpuno prave slučajne procese. Stoga se umjesto fizičkog modeliranja koriste metode matematičkog modeliranja slučajnosti i generiranja slučajnih nizova u obliku računalnih programa ili specijaliziranih uređaja.

Ovi programi i uređaji, iako se nazivaju generatori slučajnih brojeva, zapravo generiraju determinističke sekvence koje se samo u svojim svojstvima pojavljuju nasumično i stoga se nazivaju pseudoslučajnim sekvencama. Oni su dužni osigurati da, čak i poznavajući zakon formiranja, ali bez poznavanja ključa u obliku zadanih početnih uvjeta, nitko ne bi mogao razlikovati generirani niz od slučajnog, kao da je dobiven bacanjem ideala kocke.

Generator pseudoslučajnih brojeva(PRNG, engleski Pseudorandom number generator, PRNG) - algoritam koji generira niz brojeva, čiji su elementi gotovo neovisni jedan o drugom i pokoravaju se zadanoj distribuciji (obično jednoličnoj).

Moguće je formulirati tri glavna zahtjeva koje moraju zadovoljiti kriptografski jaki generatori pseudoslučajnih nizova ili gama.

1. Gama period mora biti dovoljno velik za šifriranje poruka različitih duljina.

2. Gamu bi trebalo biti teško predvidjeti. To znači da ako su tip generatora i dio gama poznati, tada je nemoguće predvidjeti gama bit koji slijedi nakon ovog dijela ili gama bit koji prethodi ovom komadu.

3. Generiranje raspona ne bi trebalo biti povezano s velikim tehničkim i organizacijskim poteškoćama.

Najvažnija karakteristika generatora pseudoslučajnih brojeva je informacijska duljina njegovog perioda, nakon koje će se brojevi jednostavno ponavljati ili se mogu predvidjeti. Ova duljina praktički određuje mogući broj ključeva u kriptosustavu. Što je ova duljina duža, to je teže pronaći ključ.

Drugi od gore navedenih zahtjeva vezan je uz sljedeći problem: na temelju čega možemo zaključiti da je gama određenog generatora uistinu nepredvidljiva? Za sada u svijetu ne postoje univerzalni i praktično provjerljivi kriteriji za provjeru ovog svojstva. Intuitivno se slučajnost doživljava kao nepredvidivost. Da bi se gama smatrala slučajnom i nepredvidivom, njezin period mora biti barem vrlo velik, a različite kombinacije bitova određene duljine moraju biti ravnomjerno raspoređene duž cijele duljine. Ovaj se zahtjev može statistički protumačiti kao složenost zakona za generiranje pseudoslučajnog niza brojeva. Ako je iz dovoljno dugog segmenta ovog niza nemoguće statistički ili analitički utvrditi ovaj zakon generacije, onda se u načelu time možemo zadovoljiti.

I konačno, treći zahtjev mora jamčiti mogućnost praktične primjene generatora pseudoslučajnih nizova, uzimajući u obzir potrebnu brzinu i jednostavnost praktične uporabe. Razmotrimo sada neke praktične metode za dobivanje pseudoslučajnih brojeva.

3. Metode dobivanja pseudoslučajnih brojeva

Jedna od prvih takvih metoda bila je metoda koju je 1946. predložio D. von Neumann. Ova se metoda temeljila na činjenici da je svaki sljedeći broj u pseudoslučajnom nizu formiran kvadriranjem prethodnog broja i odbacivanjem znamenki na oba kraja. Međutim, ova metoda se pokazala nepouzdanom i brzo je napuštena. Druga metoda je takozvana kongruentna metoda.

3.1 Linearna kongruentna metoda

Linearna kongruentna metoda jedan je od algoritama za generiranje pseudoslučajnih brojeva. Koristi se u jednostavnim slučajevima i nema kriptografsku snagu. Uključeno u standardne biblioteke raznih kompilatora.

Ovaj se algoritam sastoji od iterativne primjene sljedeće formule:

gdje su a>0, c>0, m>0 neke cjelobrojne konstante. Dobiveni niz ovisi o izboru startnog broja X 0 a za različite njegove vrijednosti dobivaju se različiti nizovi slučajnih brojeva. U isto vrijeme, mnoga svojstva niza X j određuju se izborom koeficijenata u formuli i ne ovise o izboru startnog broja. Jasno je da je niz brojeva generiran takvim algoritmom periodičan s razdobljem koje ne prelazi m. U ovom slučaju, duljina razdoblja je jednaka m ako i samo ako:

· GCD (c, m) = 1 (tj. c i m su prosti);

· a - 1 višekratnik od p za sve proste p - djelitelje od m;

· a - 1 je višekratnik broja 4 ako je m višekratnik broja 4.

Statistička svojstva rezultirajućeg niza slučajnih brojeva potpuno su određena izborom konstanti a I c na zadanoj dubini bita e. Za ove konstante zapisani su uvjeti koji jamče zadovoljavajuću kvalitetu rezultirajućih slučajnih brojeva.

Donja tablica prikazuje najčešće korištene parametre linearnih kongruentnih generatora, posebno u standardnim bibliotekama raznih prevodilaca (funkcija rand()).

3.2 Fibonaccijeva metoda

Zanimljiva klasa generatora pseudoslučajnih nizova temelji se na korištenju Fibonaccijevih nizova. Klasičan primjer takvog niza (0,1,1,2,3,5,8,13,21,34...) - osim njegova prva dva člana, svaki sljedeći član jednak je zbroju prethodna dva.

Značajke distribucije slučajnih brojeva generiranih linearnim kongruentnim algoritmom onemogućuju njihovu upotrebu u statističkim algoritmima koji zahtijevaju visoku rezoluciju.

S tim u vezi, linearni kongruentni algoritam postupno je gubio na popularnosti, a njegovo mjesto zauzela je obitelj Fibonaccijevih algoritama, koji se mogu preporučiti za korištenje u algoritmima koji su ključni za kvalitetu slučajnih brojeva. U literaturi na engleskom jeziku Fibonaccijevi senzori ove vrste obično se nazivaju “Subtract-with-borrow Generators” (SWBG).

Najveću popularnost Fibonaccijevi senzori su stekli zahvaljujući činjenici da je brzina izvođenja aritmetičkih operacija s realnim brojevima postala jednaka brzini cjelobrojne aritmetike, te su Fibonaccijevi senzori prirodno implementirani u realnu aritmetiku.

Jedan od naširoko korištenih Fibonaccijevih senzora temelji se na sljedećoj iterativnoj formuli:

Gdje x k - realni brojevi iz raspona )