|
FER, ZEMRIS
Autor: Saša Jurić e-mail: sasa.juric@fer.hr
SADRŽAJ
Potreba za slučajnim brojevima se javlja u mnogim programima. Razni kriptografski algoritmi i protokoli zahtijevaju u određenim koracima određeni niz slučajnih bitova (npr. generacija javnog ključa, generacija slučajnih bitova u postupku autentifikacije, ključevi u digitalnom potpisu i pečatu, …). Česta primjena slučajnih brojeva je i u računalnim simulacijama (Monte Carlo metoda) gdje se simulacijom stohastičkog sustava pokušava doći do rješenja problema kojeg je nemoguće riješiti analitičkim putem. Ideja je da se uzevši u obzir karakteristike nekog sustava, varijablama tog sustava pridjeljuju slučajni brojevi te se nizom simulacija i odgovarajućom statističkom obradom rezultata izvlače očekivani zaključci (npr. očekivana srednja vrijednost neke varijable, vjerojatnost pojave nekog događaja i sl.). Tipično se, dakle, primjena slučajnih brojeva može svrstati u dvije kategorije: kriptografija i računalna simulacija. Obje kategorije postavljaju zahtjeve da slučajni brojevi koji se upotrebljavaju što više sliče “stvarnim” slučajnim brojevima. Važno je primjetiti da se slučajni brojevi u stvarnosti javljaju samo u prirodnim pojavama i situacijama koje je nemoguće predvidjeti (npr. bacanje potpuno simetričnog novčića). U primjeni se međutim upotrebljavaju sklopovska i/ili programska rješenja koja dovode do toga da su dobiveni brojevi manje ili više slučajni. Karakteristika slučajnosti se formalno gledano ne može definirati. Uzevši u obzir da sama pojava niza slučajnih brojeva predstavlja nepredvidivi, stohastički sustav, nemoguće je za neki niz brojeva reći da je slučajan ili nije. Formalno je dokazano da je svaki niz brojeva jednako “slučajan” kao i bilo koji drugi niz brojeva (npr. niz 5, 5, 5, 5, 5 je jednako “slučajan” kao i niz 12, 77, 34, 19, 3). U praksi se pri proučavanju slučajnosti nekog niza brojeva zapravo gleda skup odabranih testova koji provjeravaju određene karakteristike ulaznog niza brojeva (za koji želimo ustanoviti je li “slučajan”). Svaki test pokušava ustanoviti javljaju li se u ulaznom nizu nekakve pravilnosti koje se statistički ne bi smjeli javiti te se niz prihvaća ili odbacuje kao “slučajan”. Zaključak da je niz slučajan zapravo znači da niz pokazuje neke karakteristike koje se očekuju od niza slučajnih brojeva. Niz slučajnih brojeva generira se od strane generatora slučajnih brojeva. Generatore slučajnih brojeva možemo općenito podijeliti u dvije kategorije: generatori “istinski” slučajnih brojeva i generatori pseudoslučajnih brojeva. Generatori “istinski” slučajnih brojeva (RNG – Random number generators) U ovu kategoriju spadaju generatori koji generiraju slučajne brojeve na temelju prirodnih pojava tj. izvor slučajnih brojeva je nedeterministički (slučajni broj u nizu je neovisan o svom prethodniku). Ti generatori su u potpunosti ili većim djelom sklopovske naravi te je njihova izvedba osjetljiva i skupa, a primjena je ograničena. Dodatno, generacija brojeva može biti spora, a sam sklop je podložan kvarovima. Stoga se ovakvi generatori češće upotrebljavaju u simulacijskim primjenama. Izvore “istinski” slučajnih brojeva možemo svrstati u dvije kategorije:
Pametnim kombiniranjem više različitih izvora slučajnih brojeva moguće je dobiti dobar generator slučajnih brojeva. Generatori pseudoslučajnih brojeva (PRNG – Pseudorandom number generators) Ovaj tip generatora je u biti funkcija koja na temelju početnih uvjeta daje izlazni niz pseudoslučajnih brojeva. Ulaz u generator (početni uvjeti, seed) mora biti “istinski” slučajan, te se dobija iz generatora “istinski” slučajnih brojeva (npr. vrijeme sistemskog sata). Nakon određivanja početnih uvjeta, svaki broj u nizu se može predvidjeti što dovodi do determinističke karakteristike generatora, pa se dobiveni brojevi nazivaju pseudoslučajnima. Cijeli niz se može reproducirati samo uz znanje početnih uvjeta pa, ako je potrebna reprodukcija niza, dovoljno je sačuvati samo početne uvjete. Zanimljivo je da se u ispitivanjima, pseudoslučajni brojevi ponekad pokazuju uspješniji od slučajnih brojeva dobivenih iz fizičkih izvora. Pažljivim odabirom generatora i početnih uvjeta, determinističke metode koje se upotrebljavaju moguće je prikriti, i izlazni niz poprima mnoge karakteristike slučajnih brojeva. Općenito su generatori pseudoslučajnih brojeva brži, lakše ostvarivi i prenosivi. Unatoč tome, potrebno je paziti pri odabiru generatora bilo da se generator upotrebljava u simulacijske svrhe ili je riječ o kriptografskom generatoru. Konvencije U nastavku teksta će biti opisani tipični generatori pseudoslučajnih brojeva i metode testiranja generatora. Pojam generatora slučajnih brojeva će označavati generator pseudoslučajnih brojeva. Važno je napomenuti da većina metoda za testiranje ispituje efikasnost generatora (pseudo)slučajnih bitova (RBG ili PRBG). Iako se na prvi pogled čini da se generator slučajnih bitova razlikuje u svojstvima od generatora slučajnih brojeva, to nije slučaj. Generator slučajnih brojeva jednostavno se može dobiti grupiranjem bitova dobivenih iz generatora slučajnih bitova. GENERATORI PSEUDOSLUČAJNIH BROJEVA Već je ranije spomenuto da je svaki niz brojeva jednako slučajan kao i bilo koji drugi niz brojeva što je moguće i formalno dokazati. U praksi je naravno jasno da se neki nizovi brojeva ne mogu smatrati slučajnima (npr. alterirajući niz 0 i 1, monotono rastući niz, niz od samo jednog broja, …). Neka od poželjnih svojstava koje se očekuju od generiranog niza su:
Dodatno se očekuje mogućnost reproduciranja niza, prenosivost i velika brzina rada uz minimalne memorijske zahtjeve. Mogućnost reproduciranja niza je važna zbog detekcije i ispravljanja pogrešaka uzrokovanih od strane generatora (loš generator slučajnih brojeva često može uzrokovati neispravan rad programa). Od prenosivog generatora se očekuje da pokazuje ista svojstva u različitim uvjetima rada (različiti strojevi, operacijski sustavi, programski jezici ugradnje). Važno je da uz iste početne uvjete generator generira isti niz brojeva. Velika brzina je zahtjev koji je važan u simulacijskim primjenama gdje se generira veliki broj slučajnih brojeva (npr. niz od 106 brojeva). Očito je da pri generaciji tako velikog broja brojeva generator mora biti što je moguće brži. Pri tome je važno primjetiti da je brzina sekundarni zahtjev u odnosu na kvalitetu generiranog niza (u smislu slučajnosti). Naime, osnovna svrha generatora slučajnih brojeva je generiranje niza brojeva koji pokazuju određene slučajne karakteristike. Važno je pri optimizaciji generatora voditi računa da se kvaliteta generiranog niza ne smanji. U nastavku će biti ukratko opisani neki osnovni generatori pseudoslučajnih brojeva. Ti generatori (kao uostalom i svi generatori o kojima ima smisla raspravljati) zadovoljavaju većinu navedenih uvjeta. Važno je, međutim, primjetiti da su spomenuti uvjeti zapravo osnovni uvjeti koje generator slučajnih brojeva mora ispuniti. Temeljita ispitivanja kvalitete generatora uvode mnoštvo dodatnih uvjeta koje generirani niz mora zadovoljavati (posebno ako se generator primjenjuje u kriptografske svrhe). LCG (Linear Congruential Generator) Vjerovatno najčešće upotrebljavani generator slučajnih brojeva radi na jednostavnom principu. Početni uvjet (seed) je cijeli broj koji ujedno predstavlja i prvi broj u nizu, a obično se dobija pomoću nekog generatora “istinski” slučajnih brojeva (npr. sistemski sat). Svaki slijedeći broj u nizu računa se na temelju svog prethodnika a prema formuli:
Cjelobrojne konstante a, c i m su zajedno sa početnim uvjetima parametri koji u potpunosti određuju niz koji će biti generiran, pa stoga LCG možemo označiti kao uređenu četvorku:
Budući da je svaki broj u nizu u potpunosti određen svojim prethodnikom, memorijski zahtjevi ovakvog generatora su minimalni i generator je brz. Nažalost, zbog jednostavne izvedbe, period generatora je ograničen konstantom m i ne može biti veći od m (ali zato može biti manji!). Dodatno, uočeno je da n-torke koje se dobiju grupiranjem po n elemenata iz generiranog niza pokazuju pravilnu strukturu u n dimenzionalnom prostoru za proizvoljni broj n. Općenito, postoje tri vrste LCG-a koji se upotrebljavaju:
LFG (Lagged Fibonacci Generator) LFG je tip generatora koji u posljednje vrijeme postaju sve popularniji. Niz brojeva se generira prema formuli:
gdje su p,q cijeli brojevi i vrijedi p > q, a · je neka binarna operacija (zbrajanje ili množenje mod m, XOR, …). Tipično se kao operacija upotrebljava zbrajanje modulo m, a m se uzima u obliku potencije broja dva (m = 2M), pa će u nastavku teksta biti razmatrani samo takvi generatori koji onda imaju oblik:
a generatori će se označavati sa LFG(p,q,M). Očito je da su početni uvjeti generatora zapravo niz brojeva X0, …, Xp-1 koji se mogu odabrati npr. upotrebom LCG generatora. Uz pažljivi odabir p i q, moguće je postići duže periode generatora u usporedbi sa LCG generatorima: P = (2p – 1 )2M-1. Dva često upotrebljavana generatora ovakvog tipa su:
Teoretskim razmatranjem, može se pokazati da period generatora ovisi i o izboru početnih uvjeta (prvih p brojeva u nizu). Naime, broj različitih kombinacija prvih p brojeva je veći od maksimalnog perioda P pa je očito da će neke (mnoge) kombinacije prvih p brojeva rezultirati periodom manjim od maksimalnog perioda P. Navedeni problem se može riješiti kanonskom formom LFG generatora. U kanonskoj formi, pri inicijalizaciji (tj. određivanju početnih uvjeta) generatora, potrebno je postaviti Xp-1 na nula. Dodatno je potrebno postaviti najmanje značajne bitove prvih p brojeva na nulu osim za jedan ili dva karakteristična broja (izbor tih brojeva ovisi o izboru brojeva p i q). Ovakvim izborom početnih brojeva, generator će uvijek postizati maksimalni period, ali je preciznost generatora smanjena za jedan bit. Naime očito je da će generirani nizovi brojeva uvijek imati iste najmanje značajne bitove (jer su oni isti za svaki početni niz brojeva). Stoga je potrebno u generiranom nizu brojeva zanemariti najmanje značajni bit pa se generirani broj kreće u rasponu [0,2M–1]. Također, uz neke karakteristične kombinacije početnih brojeva, može se dogoditi da prvih nekoliko generiranih brojeva ne posjeduje “slučajne” karakteristike. Razna ispitivanja su pokazala da niz generiran pomoću LFG generatora ima bolja “slučajna” svojstva u odnosu na niz generiran pomoću LCG generatora (posebno u smislu perioda generiranih nizova). Ipak je i kod LFG generatora primjećen problem pravilnosti pri grupiranju n-torki u n dimenzionalnom prostoru. Dodatno, izvedba LFG generatora zahtijeva veći memorijski prostor što često može biti problem, pogotovo u situacijama kada je potrebno održavati više paralelnih generatora u memoriji. Sažetak LCG i LFG su dvije osnovne vrste generatora pseudoslučajnih brojeva. LCG se još i danas najčešće upotrebljava unatoč činjenici da generirani niz brojeva pokazuje mnoge pravilnosti (pogotovo pri grupiranju n-torki). Razlog tome leži u činjenici da je za većinu primjena LCG sasvim dovoljan generator, njegova izvedba je jednostavna, memorijski zahtjevi su mali i generirani niz izgleda dovoljno “slučajan”. U primjenama većih računalnih simulacija, gdje je potrebno generirati veliki broj slučajnih brojeva (tipično, iznad 232), LCG nije nikako primjenjiv i njegova upotreba se ne savjetuje. U takvim situacijama, LFG generator se pokazuje kao dobra kombinacija brzine i kvalitete uz određene memorijske zathjeve. Dodatno se često upotrebljavaju kombinacije dva generatora (npr. dva LCG generatora ili LCG i LFG generator). Teoretski (i u praksi) je pokazano da kombinacija dva generatora daje barem jednako dobar (ili loš) generator. Pažljivim izborom parametara oba generatora, njihovom kombinacijom period se može znatno povećati i ostala “slučajna” svojstva poboljšati, ali na račun brzine i eventualno memorijskih zahtjeva. Iako je već ranije spomenuto da je zahtjev brzine generiranja brojeva sekundarni zahtjev, o tome ipak treba voditi riječ, ako se generatori upotrebljavaju u računalnim simulacijama. Naime u takvim situacijama se generira veliki broj slučajnih brojeva te je naravno brzina generatora vrlo važan faktor. KRIPTOGRAFSKI SIGURNI GENERATORI PSEUDOSLUČAJNIH BROJEVA (BITOVA) Dosada prikazani generatori najčešću primjenu imaju pri generaciji slučajnih brojeva u svrhu računalne simulacije. U kriptografskim primjenama, međutim, potrebna je dodatna sigurnost. Naime pri generaciji slučajnih bitova koji služe kao ključevi, nužno je osigurati nepredvidivost brojeva u generiranom nizu. Ulaz u generator mora biti odabran tako da ga je praktićki nemoguće otkriti bilo metodom pogađanja, bilo pretraživanjem svih mogućih kombinacija. Npr. ako se kao ulaz uzima vrijeme, ono mora biti što preciznije odabrano tj. potrebno je uzeti u obzir što je više moguće informacija o trenutnom vremenu (godina, mjesec, … , milisekunde). Dodatno, period generatora mora biti izuzetno velik. Time se postiže vrlo veliki broj različitih nizova koje je nemoguće pretraživati u konačnom vremenu. Ako je generator pažljivo konstruiran tako da generirani niz u sebi ne sadrži očite elemente pravilnosti, metoda predviđanja (pogađanja) niza je svedena na minimum. Dobiveni niz se tada može upotrijebiti npr. kao tajni ključ za slanje poruka. Sami algoritmi generatora su javno dostupni, ono što mora biti privatno za pojedinu kriptografsku aplikaciju je način izbora početnih uvjeta. Generator mora biti tako napravljen da je bez znanja početnih uvjeta nemoguće predvidjeti niz brojeva unatoč poznavanju algoritma. Važno je primjetiti da bi kriptografski sigurni generatori (CSPRBG – cryptographically secure pseudorandom bit generator) bili izuzetno korisni i u računalnim simulacijama jer općenito daju puno kvalitetnije nizove od standardnih generatora. Problem međutim leži u činjenici da su, zbog relativno složenih algoritama, bitno sporiji u odnosu na standardne generatore što ih čini nepogodnima za generaciju vrlo velikog broja podataka. Međutim, u kriptografskim primjenama je potrebno generirati mali broj podataka (tipično par desetaka ili stotina bitova) pa brzina izvođenja ne predstavlja veliki faktor pri izboru generatora. U nastavku će biti prikazana dva kriptografski sigurna generatora koji se temelje na DES i RSA algoritmima kriptiranja. Ideja je da se upotrebljava jednosmjerna funkcija f(s) koja se upotrebljava na nizu s,s1,s2,s3, … i daje niz f(s),f(s1),f(s2),f(s3), … U ovisnosti o tome koja se funkcija upotrebljava, iz izlaznog niza se zadržavaju samo određeni bitovi kako bi se eliminirala korelacija između uzastopnih elemenata u nizu. ANSI X9.17 generator kao funkciju upotrebljava trostruko E-D-E kriptiranje sa dva ključa DES algoritmom. Trostruko E-D-E kriptiranje se definira na slijedeći način:
gdje EK(x) označava kriptiranje uz pomoć ključa K, a DK(x) označava dekriptiranje uz pomoć ključa K. Ako se uzme da vrijedi:
tada je riječ o trostrukom E-D-E kriptiranju sa dva ključa. Ulazni podaci generatora su: slučajni 64-bitni podatak s (seed), cijeli broj m i ključevi kriptiranja K1 i K2. Algoritam se odvija prema slijedećim koracima:
Važno je napomenuti da za ovaj algoritam nije formalno dokazano da je kriptografski siguran. Međutim generator se pokazao upotrebljivim (dovoljno sigurnim) u većini primjena. Prednost ovog generatora u odnosu na dokazane kriptografski sigurne generatore je jednostavnija izvedba i bitno veća brzina. RSA generator pseudoslučajnih brojeva Algoritam generatora se odvija prema slijedećim koracima:
Dobiveni rezultat je niz slučajnih bitova z1, …, zl. Važno je primjetiti da se brojevi generiraju sporo (u odnosu na dosad prikazane generatore), zbog razloga što je potrebno računati potenciju velikog broja (tipično par stotina bitova) te ostatak dijeljenja sa velikim brojem (iste veličine) što naravno nije sklopovski podržano. Postoje određene metode koje donekle mogu ubrzati rad generatora uz minimalnu cijenu kvalitete niza (poboljšani generator ostaje i dalje kriptografski siguran u određenim uvjetima). Važno je međutim napomenuti da se svaki postupak optimizacije mora izvesti uz maksimalni oprez jer pojava korelacije među susjednim bitovima bitno povećava mogućnost provale. ISPITIVANJE GENERATORA SLUČAJNIH BROJEVA Pod pojmom ispitivanja generatora, misli se na ispitivanje kvalitete generiranog niza. Pri ispitivanju se želi ustanoviti pokazuje li generirani niz ili ne neke poželjne karakteristike (npr. nedostatak pravilnosti u nizu, ispravna distribucija brojeva i sl.). Cilj ispitivanja je iz beskonačnog skupa testova (tj. beskonačnog skupa karakteristika niza) izvući bitne testove. Postoji mnoštvo različitih skupova testova, ali niti jedan ne može proglasiti niz generiranih brojeva “slučajnim”, moguće je samo zaključiti pokazuje li niz neka od ponašanja koja bi pokazao niz generiran od strane idealnog generatora (idealni generator je npr. čovjek koji baca potpuno simetrični novčić). Nasuprot tome, na temelju rezultata se može sigurno zaključiti da neki niz nije slučajan tj. da generator radi neispravno. Npr. ako generator generira niz u kojem su svi brojevi isti, očito je da se ne radi o slučajnim brojevima. Osnova za ispitivanje je statistički test tvrdnje. Prije ispitivanja, postavlja se nulta tvrdnja (H0) te alternativna tvrdnja (Ha). Pri ispitivanju generatora slučajnih brojeva, tvrdnje imaju slijedeći oblik:
Za svaki ispit potrebno je odrediti statističku vrijednost koja se ispituje tj. vrijednost pomoću koje se odlučuje koja od tvrdnji se prihvaća kao istinita (uvijek se prihvaća točno jedna od navedenih tvrdnji). Nakon toga, potrebno je teoretski, matematičkim postupcima, odrediti očekivani rezultat nulte tvrdnje u uvjetima normalne, referentne raspodjele. Nakon toga se određuje kritična vrijednost za koju se ne očekuje da će se premašiti u uvjetima normalne raspodjele (tj. mala je vjerojatnost da će se dogoditi taj slučaj). Konačno, na temelju generiranog niza se računa tražena statistička vrijednost. Ako mjerena vrijednost prelazi teoretski određen prag, može se sa određenom sigurnošću reći da generirani niz nije niz slučajnih brojeva (prihvaćanje Ha). Vrijedi i obratno tj. ako mjerena vrijednost ne prelazi određeni prag, moguće je sa određenom sigurnošću prihvatiti H0. Mjera sigurnosti s kojom se generator prihvaća ili ne prihvaća kao ispravan se naziva nivo značaja a . Ako je a prevelik, ispitivanje može odbaciti niz koji u stvarnosti je niz slučajnih brojeva. Obratno, ako je a premali, ispitivanje može prihvatiti niz koji u stvarnosti nije niz slučajnih brojeva. Tipično se vrijednost a uzima između 0.001 i 0.05. U ovdje spomenutim ispitivanjima, a će iznositi 0.01 (tipično za kriptografske primjene). To znači da se niz može prihvatiti ili odbaciti sa 99% sigurnosti ili drugim riječima, rezultat ispita će dovesti do krivog zaključka u 1% slučajeva (pod ovime se ne misli da će od sto ispitivanja istog niza jedno ispitivanje dati pogrešan rezultat, nego da će se pogrešan zaključak izvesti nad jednim od sto mogućih kombinacija niza slučajnih brojeva). Tipično se u ispitima upotrebljavaju dvije standardne raspodjele: normalna raspodjela (očekivana raspodjela promatranih vrijednosti u nekom prostoru) te c 2 raspodjela (očekivana raspodjela učestalosti pojave nekih događaja). Ako ispitani niz nije niz slučajnih brojeva, mjerena statistička vrijednost ispita će se nalaziti u ekstremnim dijelovima krivulje (veličina tih dijelova ovisi o odabranoj vrijednosti a ). Odabir raspodjele ovisi o karakteristici koja se ispituje, a dodatno je u posebnim ispitivanja moguće uzeti i neku drugu raspodjelu. Sam tijek ispitivanja zahtjeva generiranje velikog niza brojeva (barem 103 brojeva u nizu, a tipično oko 106 brojeva). Važno je istaknuti da svaki ispit mjeri neku od poželjnih karakteristika slučajnih brojeva (npr. ravnomjerna raspodjela brojeva u prostoru). Nakon serije ispitivanja u najboljem slučaju moguće je zaključiti da ispitivani generator posjeduje željena svojstva te da bi mogao biti dobar generator slučajnih brojeva (čak i tako neodređen zaključak se može izvući sa 99% sigurnosti). S druge strane moguće je zaključiti da ispitivani generator nije odgovarajući (također sa 99% sigurnosti). Poželjno je nakon provedene serije statističkih ispita izvršiti dodatna eksperimentalna ispitivanja. Tipični primjer je upotreba generatora u simulaciji čiji rezultati se mogu a priori teoretski odrediti: simulacijom se računa neka vrijednost te se uspoređuje sa izračunatom teoretskom vrijednosti. U nastavku će biti prikazan skup ispita koju preporučuje NIST (National Institute of Standards and Technology). Algoritmi za pojedine ispite su navedeni u odgovarajućoj NIST dokumentaciji (2.) zajedno sa pripadnim formalnim matematičkim izvodim te ovdje neće biti prikazani. Nivo značaja u svim ispitima iznosi 0.01, a poželjno je da se niz sastoji od barem 100 brojeva. Svi ispiti se vrše nad nizom bitova, ali izvedeni zaključci se normalno mogu primjeniti za generator slučajnih brojeva. Već je ranije spomenuto da se generator slučajnih brojeva dobije jednostavnim grupiranjem više bitova iz niza slučajnih bitova. Ispitivanje učestalosti u nizu Promatrana karakteristika u ovom ispitu je odnos jedinica i nula u nizu bitova. Svrha je uočiti da li je u promatranom ispitu približno jednak broj jedinica i nula. Naravno, za očekivati je da kvalitetni generator slučajnih bitova daje približno jednak broj jedinica i nula. Sva druga ispitivanja ovise o prolazu ovog ispita. Može se reći da je prolaz ovog ispita nužan, ali ne i dovoljan uvjet za donošenje zaključka radi li se o nizu slučajnih bitova ili ne. Ispitivanje učestalosti u bloku Promatrana karakteristika u ovom ispitu je odnos jedinica i nula u M-bitnim blokovima u nizu. Svrha je uočiti je li broj jedinica i nula podjednak u svakom M-bitnom bloku. Za blok veličine M=1 ovaj ispit se pretvara u ispit učestalosti u nizu. Ispitivanje uzastopnih ponavljanja istih bitova u nizu Promatrana karakteristika u ovom ispitu je ukupni broj uzastopnih ponavljanja jednog broja u niz. Uzastopno ponavljanje je pojava dva ili više istih brojeva za redom. Svrha je uočiti da li se broj uzastopnih ponavljanja sa očekivanim brojem koji bi bio u savršeno slučajnom nizu Ispitivanje najdužeg uzastopnog ponavljanja jedinica u bloku Promatrana karakteristika u ovom ispitu je najduže uzastopno ponavljanje jedinica u M-bitnim blokovima. Svrha je odrediti da li se dužina najdužeg uzastopnog ponavljanja poklapa sa dužinom koja bi se očekivala u nizu slučajnih bitova. Nepravilnost u dužini najdužeg uzastopnog ponavljanja jedinica u bloku povlači za sobom i nepravilnost u dužini najdužeg uzastopnog ponavljanja nula u bloku, pa nije potrebno obaviti posebno ispitivanje za ponavljanje nula u M bitnim blokovima. Veličina bloka M se bira u ovisnosti o veličini niza n, prema tablici koju preporučuje NIST. Ispitivanje ranga matrice Promatrana karakteristika u ovom ispitu je rang matrica koje se dobiju iz podniza ispitivanog niza. Namjera je ustanoviti postoji li linearna ovisnost između podnizova fiksne duljine u ispitivanom nizu. Spektralno ispitivanje Promatrana karakteristika u ovom ispitu su amplitude u diskretnoj Fourierovoj transformaciji promatranog niza. Svrha ispita je otkrivanje periodičkih pojava u promatranom nizu (ponavljajući uzorci koji su međusobno “previše blizu”) koje bi ukazale na odstupanja od niza slučajnih bitova. Ispitivanje ponavljanja predloška u generiranom nizu Promatrana karakteristika u ovom ispitu je broj ponavljanja unaprijed određenog niza bitova (predloška) u generiranom nizu. Preveliki broj ponavljanja predloška ukazuje na pravilnost u generiranom nizu bitova, te potencijalno lošu distribuciju brojeva koji se dobiju grupiranjem bitova (kada se želi ostvariti niz slučajnih brojeva). Ispit se javlja u dvije varijante: sa preklapanjem (overlapping) i bez preklapanja (non-overlapping). U varijanti sa preklapanjem, dopušteno je da se uzorci međusobno preklapaju (npr. broj ponavljanja predloška 101 u nizu 1010101 iznosi tri). Obratno, u varijanti bez preklapanja to nije dopušteno (za isti primjer, broj ponavljanja iznosi dva: 1010101). Maurerov univerzalni statistički test Promatrana karakteristika u ovom ispitu je broj bitova između istih uzoraka (mjera koja određuje koliko se niz može komprimirati). Svrha ispita je ispitati da li se promatrani niz može značajno komprimirati bez gubitaka informacije. Za niz koji se može značajno komprimirati smatra se da nije niz slučajnih bitova zbog činjenice da je kompresija niza (bez gubitaka) efikasnija ukoliko niz pokazuje periodička svojstva, Ispitivanje na temelju Lempel-Ziv kompresije Promatrana karakteristika u ovom ispitu je broj različitih uzoraka (riječi) u ispitivanom nizu na temelju koje se određuje može li se niz značajnije komprimirati ili ne. Ispitivanje linearne složenosti Promatrana karakteristika u ovom ispitu je veličina posmačnog registra s povratnom vezom. Ispitivani niz se dijeli na blokove te se za svaki M-bitni blok računa minimalna veličina posmačnog registra s povratnom vezom koji generira sve bitove u tom bloku. Za niz slučajnih bitova se očekuju veće veličine posmačnog registra s povratnom vezom. Ispitivanje preklapajućih uzoraka Promatrana karakteristika u ovom ispitu je učestalost pojave svih mogućih m-bitnih uzoraka (uz preklapanje) u cijelom ispitivanom nizu. Namjera je otkriti da li je broj pojava 2m m-bitnih preklapajućih uzoraka približno jednak broju koji se očekuje za niz slučajnih brojeva. Niz slučajnih brojeva bi trebao imati ravnomjernu raspodjelu, tj. očekuje se da je vjerojatnost pojave svih m-bitnih uzoraka jednaka. Za m=1 ovaj ispit prelazi u ispit učestalosti u nizu. Ispitivanje približne entropije Promatrana karakteristika u ovom ispitu je također učestalost pojave svih mogućih preklapajućih m-bitnih uzoraka u nizu. Namjera je usporediti učestalost preklapajućih blokova susjednih veličina (m-bitni i m+1-bitni blok) sa očekivanim rezultatima. Ispitivanje kumulativne sume Promatrana karakteristika u ovom ispitu je najveće odstupanje od nule kumulativne koja se dobije postepenim zbrajanjem članova modificiranog niza. Modificirani niz dobije se tako da sve nule u ispitivanom nizu poprime vrijednost -1. Namjera je ustanoviti je li najveće odstupanje preveliko ili premalo u odnosu na očekivano. Ispitivanje slučajnog hoda Slučajni hod na temelju kumulativne sume dobije se nakon što se sve nule u nizu zamijene sa vrijednosti –1. Prolaskom kroz bitove promatranog niza računa se suma. Trenutna vrijednost u nekom koraku označava stanje. Ciklus u slučajnom hodu sastoji se od niza koraka koji počinju i završavaju na istom mjestu. Korak je u stvari promjena sume za +/- 1 pri računanju sume za sljedeći bit u nizu. Svrha ispita je odrediti da li broj “posjeta” svakom stanju u jednom ciklusu značajno odstupa od očekivanog broja za niz slučajnih bitova. Dodatna varijanta ovog ispita za karakteristiku uzima broj koliko je neko stanje posjećeno u slučajnom hodu kroz cijeli niz (a ne kroz ciklus).
Korisne informacije i tekstovi mogu se pronaći i na stranicama pLab projekta: http://random.mat.sbg.ac.at © Zavod za Elektroniku,
Mikroelektroniku, Računalne i Inteligente Sustave
|