Generisanje slučajnih nizova sa datim zakonom verovatnoće i provera njihove adekvatnosti su među najvažnijim problemima moderne kriptologije. Generatori slučajnih sekvenci se koriste u postojećim kriptosistemima za generiranje ključnih informacija i postavljanje brojnih parametara kriptosistema. Naučni i praktični značaj ovog problema je toliki da su mu posvećene posebne monografije iz oblasti kriptologije, sekcije se organizuju u naučnim časopisima "Journal of Cryptology", "Cryptologia" i posebne sesije na međunarodnim naučnim konferencijama "Eurocrypt ", "Asiacrypt", "Crypto" i sl.

Početkom 20. stoljeća imitirani su nasumični nizovi uz korištenje najjednostavnijih nasumičnih eksperimenata: bacanje novčića ili kocke, vađenje loptica iz urne, polaganje karata, rulet itd. L. Tippet je 1927. objavio tabele koje sadrže preko 40.000 slučajni brojevi po prvi put. , "arbitrarno izvučeni iz popisnih izvještaja". 1939. godine, koristeći posebno dizajnirani mehanički uređaj - generator slučajnih brojeva, M. J. Kendall i B. Babington-Smith kreirali su tabelu koja je uključivala 10 5 slučajnih brojeva. Godine 1946. američki matematičar John von Neumann prvi je predložio kompjuterski algoritam za generiranje slučajnih brojeva. Godine 1955. RAND Corporation je objavila široko popularne tabele koje sadrže 10 6 kompjuterski generisanih nasumičnih cifara.

Trenutno je potražnja za generatorima slučajnih nizova sa zadatim distribucijama vjerovatnoće, kao i za samim slučajnim nizovima, toliko porasla da su se u inostranstvu pojavile naučne i proizvodne kompanije koje se bave proizvodnjom i prodajom velikih nizova slučajnih brojeva. Na primjer, od 1996. godine u svijetu se distribuira CD-ROM "The Marsaglia random number CDROM", koji sadrži 4,8 milijardi "true random" bitova.

Ogromna većina modernih kriptografskih sistema koristi stream ili blok algoritme zasnovane na različitim tipovima supstitucijskih i permutacionih šifri. Nažalost, gotovo svi algoritmi koji se koriste u stream kriptosistemima namijenjeni su upotrebi u vojnim i vladinim komunikacijskim sistemima, a u nekim slučajevima i za zaštitu komercijalnih informacija, što ih sasvim prirodno čini tajnim i nedostupnim za pregled. Jedini standardni algoritmi za strimovanje simetrične enkripcije su američki DES standard (CFB i OFB načini) i ruski GOST 28147-89 standard (gama mod).

Osnova funkcionisanja stream kriptosistema su generatori slučajnih ili pseudo-slučajnih sekvenci. Razmotrimo ovo pitanje detaljnije.

2 Generator pseudoslučajnih brojeva

Tajni ključevi su osnova kriptografskih transformacija, za koje je, prema Kerckhoffsovom pravilu, snaga kriptosistema određena samo tajnošću ključa. Glavni problem klasične kriptografije dugo je bio teškoća generiranja tajnog ključa. Fizičko modeliranje slučajnosti korištenjem takvih fizičkih fenomena kao što je, na primjer, radioaktivno zračenje ili šum pucnjave u vakuumskoj cijevi je prilično složeno i skupo, a korištenje tipki i pokreta miša zahtijevaju napor korisnika i također ne daju potpuno istinite slučajne procese. Stoga se umjesto fizičkog modeliranja koriste metode matematičkog modeliranja slučajnosti i generiranja slučajnih nizova u obliku kompjuterskih programa ili specijalizovanih uređaja.

Ovi programi i uređaji, iako se zovu generatori slučajnih brojeva, zapravo generiraju determinističke sekvence koje izgledaju samo nasumične po svojim svojstvima i stoga se nazivaju pseudo-slučajnim nizovima. Od njih se traži da, čak i poznavajući zakon formiranja, ali ne znajući ključ u obliku datih početnih uslova, niko ne može razlikovati generisani niz od slučajnog, kao da je dobijen bacanjem idealne kocke za igru.

Generator pseudoslučajnih brojeva(PRNG, engleski Pseudorandom number generator, PRNG) je algoritam koji generiše niz brojeva, čiji su elementi gotovo nezavisni jedan od drugog i poštuju datu distribuciju (obično uniformnu).

Moguće je formulisati tri osnovna zahtjeva koje moraju zadovoljiti kriptografski jaki generatori pseudoslučajnih sekvenci ili gama.

1. Gama period mora biti dovoljno velik da šifrira poruke različitih dužina.

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

3. Generisanje gama ne bi trebalo da bude povezano sa velikim tehničkim i organizacionim poteškoćama.

Najvažnija karakteristika generatora pseudoslučajnih brojeva je informacijska dužina njegovog perioda, nakon kojeg će se brojevi jednostavno ponavljati ili biti predvidljivi. Ova dužina praktično određuje mogući broj ključeva kriptosistema. Što je ova dužina duža, teže je podići ključ.

Drugi od navedenih zahtjeva vezan je za sljedeći problem: na osnovu čega se može zaključiti da je gama određenog generatora zaista nepredvidiva? Za sada u svijetu ne postoje univerzalni i praktično provjerljivi kriteriji za ispitivanje ovog svojstva. Intuitivno, slučajnost se doživljava kao nepredvidiva. Da bi se gama smatrala nasumičnom i nepredvidivom, barem njen period mora biti vrlo velik, a različite kombinacije bitova određene dužine moraju biti ravnomjerno raspoređene po cijeloj dužini. Ovaj zahtjev se može statistički tumačiti kao složenost zakona generiranja pseudoslučajnog niza brojeva. Ako je nemoguće ni statistički ni analitički odrediti ovaj zakon generiranja iz dovoljno dugog segmenta ovog niza, onda se to u principu može zadovoljiti.

I, konačno, treći uslov treba da garantuje mogućnost praktične implementacije generatora pseudo-slučajnih sekvenci, uzimajući u obzir potrebnu brzinu i lakoću praktične upotrebe. Razmotrimo sada neke praktične metode za dobijanje pseudoslučajnih brojeva.

3 Metode za dobijanje pseudoslučajnih brojeva

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

3.1 Linearna kongruencijalna metoda

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

Ovaj algoritam se sastoji u iterativnoj primjeni sljedeće formule:

gdje su a>0, c>0, m>0 neke cjelobrojne konstante. Rezultirajući niz ovisi o izboru početnog broja x0 a za njegove različite vrijednosti dobijaju se različiti nizovi slučajnih brojeva. Istovremeno, mnoga svojstva niza Xj određuju se izborom koeficijenata u formuli i ne zavise od izbora početnog broja. Jasno je da je niz brojeva generiran takvim algoritmom periodičan s periodom koji ne prelazi m. U ovom slučaju, dužina perioda je m ako i samo ako:

gcd (c, m) = 1 (tj. c i m su međusobno prosti);

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

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

Statistička svojstva rezultirajućeg niza slučajnih brojeva u potpunosti su određena izborom konstanti a I c na datoj dubini bita e. Za ove konstante su napisani uslovi koji garantuju zadovoljavajući kvalitet dobijenih slučajnih brojeva.

Tabela ispod pokazuje najčešće korišćene parametre linearnih kongruencijalnih generatora, posebno u standardnim bibliotekama različitih kompajlera (funkcija rand()).

3.2 Fibonačijev metod

Zanimljiva klasa generatora pseudo-slučajnih sekvenci zasniva se na upotrebi Fibonačijevih sekvenci. Klasičan primjer takvog niza (0,1,1,2,3,5,8,13,21,34 ...) - sa izuzetkom njegova prva dva člana, svaki sljedeći član jednak je zbiru dva prethodna.

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

U tom smislu, linearni kongruencijalni algoritam je postepeno gubio svoju popularnost, a njegovo mjesto je zauzela porodica Fibonačijevih algoritama, koji se mogu preporučiti za upotrebu u algoritmima koji su kritični za kvalitet slučajnih brojeva. U engleskoj literaturi, Fibonačijevi senzori ovog tipa se obično nazivaju "Generatori za oduzimanje sa posuđivanjem" (SWBG).

Fibonačijevi senzori su stekli najveću popularnost zbog činjenice da je brzina izvođenja aritmetičkih operacija sa realnim brojevima postala jednaka brzini celobrojne aritmetike, a Fibonačijevi senzori su prirodno implementirani u realnu aritmetiku.

Jedan od široko korištenih Fibonačijevih mjerača temelji se na sljedećoj iterativnoj formuli:

gdje X k - realni brojevi iz opsega)