Deterministički PRNG
PRNG-ovi su generatori pseudo-slučajnih brojeva. Isti termin se često koristi za opisivanje PRBG - generatora pseudo-slučajnih bitova, kao i raznih stream šifri. PRNG-ovi, poput stream šifri, sastoje se od internog stanja (u rasponu veličine od 16 bita do nekoliko megabajta), funkcije za inicijalizaciju internog stanja ključem ili sjemenom, funkcije za ažuriranje internog stanja i izlazne funkcije. PRNG-ovi se dijele na jednostavne aritmetičke, pokvarene kriptografske i kriptografske. Njihova zajednička svrha je generiranje nizova brojeva koji se ne mogu razlikovati od slučajnih brojeva.
Nijedan deterministički algoritam ne može generirati potpuno slučajne brojeve, već samo aproksimirati neka svojstva slučajnih brojeva. kao što je rečeno, "Svako ko ima slabost za aritmetičke metode dobijanja slučajnih brojeva je bez sumnje grešnik.".
Svaki PRNG s ograničenim resursima prije ili kasnije zaglavi. Dužina PRNG ciklusa zavisi od samog generatora i iznosi u proseku oko 2 (n / 2) gde je n veličina unutrašnjeg stanja u bitovima, iako linearno-kongruentni generatori i LFSR generatori imaju maksimalne cikluse reda reda 2 n. Ako PRNG može konvergirati u prekratke cikluse, PRNG postaje predvidljiv i neupotrebljiv.
Većina jednostavnih aritmetičkih generatora, iako brzi, pati od mnogih ozbiljnih nedostataka:
- Period / periodi su prekratki
- Uzastopne vrijednosti nisu nezavisne
- Neki bitovi su "manje slučajni" od drugih
- Neravnomjerna univarijantna distribucija
- Reverzibilnost
Konkretno, RANDU algoritam, koji se decenijama koristi u kompjuterima, pokazao se veoma lošim. Kao rezultat toga, mnoge studije su manje pouzdane nego što bi mogle biti.
PRNG sa entropijskim izvorom ili RNG
Uz postojeću potrebu za generiranjem lako reproducibilnih nizova slučajnih brojeva, postoji i potreba za generiranjem potpuno nepredvidivih ili jednostavno potpuno slučajnih brojeva. Takvi generatori se nazivaju "Generator nasumičnih brojeva" ("Generator slučajnih brojeva") ili skraćeno RNG. Budući da se takvi generatori najčešće koriste za generiranje jedinstvenih simetričnih i asimetričnih ključeva za enkripciju, najčešće se grade od kombinacije jakog PRNG-a i vanjskog izvora. Stoga je pod RNG-om sada uobičajeno podrazumijevati upravo kripto-jaki PRNG sa vanjskim izvorom entropije.
Gotovo svi glavni proizvođači mikročipova isporučuju hardverske RNG-ove sa različitim izvorima entropije, koristeći različite metode da ih očiste od neizbježne predvidljivosti. Međutim na ovog trenutka brzina prikupljanja slučajnih brojeva od strane svih postojećih mikročipova (nekoliko hiljada bita u sekundi) ne odgovara brzini modernih procesora.
U personalnim računarima, autori softvera RNG koriste mnogo brže izvore entropije, kao što su šum zvučne kartice ili vrednosti brojača takta procesora, koji su lako čitljivi, na primer, korišćenjem instrukcija u Intelovim procesorima. Prije pojave u procesorima mogućnosti očitavanja vrijednosti brojača takta procesora, koji je najosjetljiviji na najmanje promjene okoline, prikupljanje entropije je bila najranjivija tačka RNG-a. Ovaj problem još uvijek nije u potpunosti riješen u mnogim uređajima (npr. pametnim karticama) koji su i dalje ranjivi na ovaj način. Mnogi RNG-ovi još uvijek koriste tradicionalne (zastarjele) metode za prikupljanje entropije kao što su radnje korisnika (pokreti miša, itd.), kao što su i Yarrow, ili komunikacija između niti, kao u Javinom sigurnom randomu.
Evo nekoliko primjera RNG-ova sa njihovim entropijskim izvorima i generatorima:
- / dev / nasumično in / - izvor entropije: međutim, ona se prikuplja samo tokom hardverskih prekida; PRNG: LFSR, sa izlaznim heširanjem; prednosti: je u svim Unix-ovima, pouzdan izvor entropije; nedostaci: "zagreva se" jako dugo, može se "zaglaviti" dugo vremena ili radi kao PRNG ( / dev / urandom);
- Yarrow iz - izvor entropije: tradicionalne (zastarjele) metode; PRNG: AES-256 i malo interno stanje; prednosti: fleksibilan dizajn otporan na kriptovanje; nedostaci - dugo se „greje“, veoma malo unutrašnje stanje, previše zavisi od kriptografske snage odabranih algoritama, spor, primenjiv isključivo za generisanje ključeva;
- generator od Leonida Yurieva (Leo Yuriev) - izvor entropije: šum zvučne kartice; PRNG: još nije poznato; prednosti: najvjerovatnije dobar i brz izvor entropije; nedostaci - ne postoji nezavisni, očigledno kriptografski jak PRNG, dostupan je isključivo kao DLL za Windows;
- Microsoft CryptoAPI - izvor entropije: trenutno vrijeme, veličina tvrdog diska, veličina slobodne memorije, ID procesa i NETBIOS naziv računara; PRNG: 128-bitni interni heš stanja (heš je prisutan samo u 128-bitnim verzijama Windowsa); prednosti - ugrađen u Windows, ne "zaglavi" se; nedostaci - malo unutrašnje stanje, lako predvidljivo;
- Java SecureRandom - izvor entropije: komunikacija između niti; PRNG: interni hash stanja (1024 bita); dostojanstvo - u Javi još nema drugog izbora, veliko unutrašnje stanje; nedostaci: sporo prikupljanje entropije, iako u Javi još uvijek nema drugog izbora;
- Haos od Ruptor - izvor entropije:, prikuplja se kontinuirano; PRNG: heširanje 4096-bitnog internog stanja zasnovanog na nelinearnoj varijanti Marsaglia generatora; dostojanstvo: dok najbrži od svih, odlično unutrašnje stanje, ne "zaglavi".
Hardverski PRNG
Pored dobro poznatih zastarjelih LFSR generatora koji su se u prošlom stoljeću naširoko koristili kao hardverski PRNG-ovi, nažalost, vrlo malo se zna o modernim hardverskim PRNG-ovima (stream šiframa), budući da je većina njih razvijena u vojne svrhe i čuva se u tajnosti. Gotovo svi postojeći komercijalni hardverski PRNG-ovi su patentirani i također se čuvaju u tajnosti. Hardverski PRNG-ovi su ograničeni strogim zahtjevima za utrošenu memoriju (najčešće je zabranjena upotreba memorije), brzinu (1-2 ciklusa takta) i površinu (nekoliko stotina FPGA ili ASIC ćelija). Zbog tako strogih zahtjeva za hardverske PRNG-ove, vrlo je teško napraviti kriptografski generator, tako da su do sada svi poznati hardverski PRNG-ovi bili pokvareni. Primjeri takvih generatora su Toyocrypt i LILI-128, koji su oba LFSR generatora i oba su pokvarena korištenjem algebarskih napada.
Zbog nedostatka dobrih hardverskih PRNG-ova, proizvođači su primorani da koriste mnogo sporije, ali nadaleko poznate blok šifre poput AES-a i hash funkcije kao što su
Prva široko korištena tehnika generiranja slučajnih brojeva bio je algoritam koji je predložio Lehmer, a koji je poznat kao linearna kongruentna metoda. Ovaj algoritam je parametriran sa četiri broja kako slijedi:
Niz slučajnih brojeva (X n) dobija se korištenjem sljedeće iterativne jednakosti:
X n +1 = (a X n + c) mod m
Ako su m, a i c cijeli brojevi, tada je niz cijelih brojeva u rasponu 0 X n< m.
Izbor vrijednosti za a, c i m je kritičan za dizajniranje dobrog generatora slučajnih brojeva.
Očigledno, m mora biti vrlo veliko da bi se moglo stvoriti mnogo slučajnih brojeva. Vjeruje se da m treba biti približno jednako maksimalnom pozitivnom cijelom broju za dati računar. Dakle, obično je m blizu ili jednako 2 31.
Prilikom odabira generatora slučajnih brojeva koriste se tri kriterija:
1. Funkcija mora kreirati potpuni period, tj. svi brojevi između 0 i m prije nego što se generirani brojevi počnu ponavljati.
2. Generirana sekvenca mora se pojaviti nasumično. Niz nije slučajan jer je generisan deterministički, ali različiti statistički testovi koji se mogu primijeniti trebali bi pokazati da je niz slučajan.
3. Funkcija mora biti efikasno implementirana na 32-bitnim procesorima.
Vrijednosti a, c i m treba odabrati na način da su ispunjena ova tri kriterija. U skladu s prvim kriterijem, može se pokazati da ako je m jednostavno i c = 0, tada će za određenu vrijednost a period kreiran funkcijom biti jednak m-1. Za 32-bitnu aritmetiku, odgovarajuća prosta vrijednost je m = 2 31 - 1. Dakle, funkcija za generiranje pseudoslučajnih brojeva je:
X n +1 = (a X n) mod (2 31 - 1)
Samo mali broj vrijednosti zadovoljava sva tri kriterija. Jedna takva vrijednost je a = 7 5 = 16807, koja se koristila u porodici računara IBM 360. Ovaj generator se široko koristi i prošao je preko hiljadu testova, više od bilo kojeg drugog generatora pseudo-slučajnih brojeva.
Snaga linearnog kongruentnog algoritma je da ako su faktor i modul (baza) pravilno odabrani, onda će se rezultujući niz brojeva statistički ne razlikovati od niza koji je nasumičan iz skupa 1, 2, ..., m- 1. Ali ne može biti slučajnosti u nizu dobivenom algoritmom, bez obzira na izbor početne vrijednosti X 0. Ako je odabrana vrijednost, tada će preostali brojevi u nizu biti unaprijed definirani. Ovo se uvijek uzima u obzir u kriptoanalizi.
Ako protivnik zna da se koristi linearni kongruentni algoritam i ako su njegovi parametri poznati (a = 7 5, c = 0, m = 2 31 - 1), onda ako se otkrije jedan broj, cijeli niz brojeva postaje poznato. Čak i ako protivnik samo zna da se koristi linearni kongruentni algoritam, poznavanje malog dijela niza je dovoljno za određivanje parametara algoritma i svih narednih brojeva. Pretpostavimo da neprijatelj može odrediti vrijednosti X 0, X 1, X 2, X 3. onda:
X 1 = (a X 0 + c) mod mX 2 = (a X 1 + c) mod mX 3 = (a X 2 + c) mod m
Ove jednakosti nam omogućavaju da pronađemo a, c i m.
Dakle, iako je algoritam dobar generator pseudo-slučajnog niza brojeva, poželjno je da sekvenca koja se stvarno koristi bude nepredvidljiva, jer u ovom slučaju poznavanje dijela niza neće omogućiti određivanje njegovih budućih elemenata. Ovaj cilj se može postići na nekoliko načina. Na primjer, korištenje internog sistemskog sata za izmjenu toka nasumičnih brojeva. Jedan od načina da se koristi sat je ponovno pokretanje niza nakon N brojeva, koristeći trenutnu vrijednost sata po modulu m kao novo sjeme. Drugi način je jednostavno dodavanje trenutne vrijednosti vremena svakom slučajnom broju po modulu m.
algoritam za generiranje pseudoslučajnih brojeva tzv BBS algoritam(iz imena autora - L. Blum, M. Blum, M. Shub) ili rezidualni generator... Za kriptografske svrhe, ovaj metod je predložen 1986. godine.To je kako slijedi. Prvo, dva velika prosta 1 Poziva se pozitivan cijeli broj veći od jedan jednostavno, ako nije djeljiv ni sa jednim drugim brojem osim sa sobom i jednim. Za više informacija o prostim brojevima pogledajte "Osnove teorije brojeva koje se koriste u kriptografiji javnog ključa". brojevi p i q. P i q moraju biti oba uporedivi sa 3 po modulu 4, odnosno dijeljenjem p i q sa 4 treba dobiti isti ostatak 3. Zatim se izračunava broj M = p * q, koji se naziva Bloomov cijeli broj. Zatim se bira drugi slučajni cijeli broj x koji je relativno prost (tj. nema zajedničkih djelitelja osim jednog) sa M. Izračunajte x0 = x 2 mod M. x 0 se naziva početnim brojem generatora.
U svakom n-tom koraku rada generatora izračunava se x n + 1 = x n 2 mod M. Rezultat n-tog koraka je jedan (obično najmanji značajan) bit broja x n + 1. Ponekad se kao rezultat uzima bit parnosti, odnosno broj jedinica u binarnom prikazu elementa. Ako je broj jedinica u zapisu brojeva paran - bit parnosti se uzima jednak 0, neparan - bit parnosti se uzima jednak 1.
na primjer, neka je p = 11, q = 19 (pazimo da je 11 mod 4 = 3, 19 mod 4 = 3). Tada je M = p * q = 11 * 19 = 209. Odaberite x, koprostor sa M: neka je x = 3. Izračunajmo početni broj generatora x 0:
x 0 = x 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.
Izračunajmo prvih deset brojeva x i koristeći BBS algoritam. Kao nasumične bitove, uzet ćemo najmanji bitni bit u binarnoj notaciji broja x i:
| x 1 = 9 2 mod 209 = 81 mod 209 = 81 | najmanje značajan dio: | 1 |
| x 2 = 81 2 mod 209 = 6561 mod 209 = 82 | najmanje značajan dio: | 0 |
| x 3 = 82 2 mod 209 = 6724 mod 209 = 36 | najmanje značajan dio: | 0 |
| x 4 = 36 2 mod 209 = 1296 mod 209 = 42 | najmanje značajan dio: | 0 |
| x 5 = 42 2 mod 209 = 1764 mod 209 = 92 | najmanje značajan dio: | 0 |
| x 6 = 92 2 mod 209 = 8464 mod 209 = 104 | najmanje značajan dio: | 0 |
| x 7 = 104 2 mod 209 = 10816 mod 209 = 157 | najmanje značajan dio: | 1 |
| x 8 = 157 2 mod 209 = 24649 mod 209 = 196 | najmanje značajan dio: | 0 |
| x 9 = 196 2 mod 209 = 38416 mod 209 = 169 | najmanje značajan dio: | 1 |
| x 10 = 169 2 mod 209 = 28561 mod 209 = 137 | najmanje značajan dio: | 1 |
Najinteresantnije svojstvo ove metode za praktične svrhe je da za dobijanje n-tog broja niza nije potrebno izračunati svih prethodnih n brojeva x i. Ispada da se x n može odmah dobiti po formuli
Na primjer, izračunajmo x 10 odmah iz x 0:
Kao rezultat toga, zapravo smo dobili istu vrijednost kao u sekvencijalnom proračunu - 137. Čini se da su proračuni prilično složeni, ali u stvarnosti se mogu lako strukturirati kao mala procedura ili program i koristiti po potrebi.
Sposobnost "direktnog" primanja xn dozvoljava da se BBS algoritam koristi za striming enkripciju, na primjer, za datoteke sa slučajnim pristupom ili fragmente datoteka sa zapisima baze podataka.
Sigurnost BBS algoritma zasniva se na složenosti faktoringa velikog broja Ms. Tvrdi se da ako je M dovoljno veliko, ne mora se čak ni držati u tajnosti; dok se M ne faktorizuje, niko ne može predvideti izlaz PRNG generatora. To je zbog činjenice da je problem faktoringa brojeva oblika n = pq (p i q su prosti brojevi) računski vrlo težak ako znamo samo n, a p i q su veliki brojevi koji se sastoje od nekoliko desetina ili stotina bitovi (ovo je tzv problem faktorizacije).
Osim toga, može se dokazati da napadač, znajući određenu sekvencu koju generiše BBS generator, neće moći odrediti ni prethodne bitove prije, ni sljedeće. BBS generator nepredvidivo lijevo i u pravom smjeru... Ovo svojstvo je vrlo korisno za kriptografske svrhe, a povezano je i sa specifičnostima faktoringa M.
Najznačajniji nedostatak algoritma je to što nije dovoljno brz, što ne dozvoljava njegovu upotrebu u mnogim područjima, na primjer, u proračunima u realnom vremenu, a također, nažalost, u streaming enkripcija.
Ali ovaj algoritam proizvodi zaista dobar niz pseudo-slučajnih brojeva sa dugim periodom (sa odgovarajućim izborom početnih parametara), što ga omogućava da se koristi u kriptografske svrhe prilikom generisanja ključeva za šifrovanje.
Ključni pojmovi
Stream cipher- stream šifra.
BBS algoritam- jedan od metoda za generisanje pseudoslučajnih brojeva. Naziv algoritma potiče od imena autora - L. Blum, M. Blum, M. Shub. Algoritam se može koristiti u kriptografiji. Za izračunavanje sljedećeg broja x n + 1 prema BBS algoritmu, koristi se formula x n + 1 = x n 2 mod M, gdje je M = pq proizvod dva velika prosta broja p i q.
Generator pseudoslučajnih brojeva (PRNG)- neki algoritam ili uređaj koji stvara niz bitova koji izgleda kao nasumičan.
Linearni kongruencijalni generator pseudo-slučajni brojevi - jedan od najjednostavnijih PRNG-ova, koji za izračunavanje sljedećeg broja ki koristi formulu ki = (a * k i-1 + b) mod c, gdje su a, b, c neke konstante, ak i-1 je prethodni pseudoslučajni broj.
Zaostali Fibonačijev metod- jedan od metoda za generisanje pseudoslučajnih brojeva. Može se koristiti u kriptografiji.
Stream cipher- šifra koja šifrira ulaznu poruku jedan bit (ili bajt) po operaciji. Stream enkripcija eliminira potrebu za cijepanjem poruke u cjelobrojne blokove. Stream šifre se koriste za šifriranje podataka u realnom vremenu.
Kratak sažetak
Šifra toka je šifra koja šifrira ulaznu poruku jedan bit (ili bajt) u isto vrijeme. Stream enkripcija eliminira potrebu za cijepanjem poruke u cjelobrojne blokove. Dakle, ako se prenosi niz znakova, svaki znak se može šifrirati i odmah prenijeti. Stream šifre se koriste za šifriranje podataka u realnom vremenu.
Simulacija slučajnosti je često potrebna u kompjuterskim programima. Na primjer, kada se razvijaju igre. Ako program ima generator, odnosno proizvođača, slučajnog broja, onda pomoću tako dobijenog broja možete odabrati jednu ili drugu granu izvršavanja programa, ili proizvoljan objekat iz kolekcije. Drugim riječima, glavna stvar je generirati broj. Na njemu se zasniva emulacija različite vrste slučajnosti.
Ne znamo sa sigurnošću postoji li neka nezgoda u prirodi ili nam se to samo čini zbog ograničenosti našeg znanja. Znamo samo da u programiranju nema prave slučajnosti. Nema gdje uzeti proizvoljan broj, ne možete programirati njegov izgled niotkuda. Možete kreirati samo program koji će, kao rezultat primjene složene formule na "zrno", proizvesti broj, a činiće nam se da je taj broj slučajan.
"Zrno" je ulaz u formulu. To može biti, na primjer, sistemsko vrijeme u milisekundama, koje se stalno mijenja. Shodno tome, "zrno" će biti stalno drugačije. Ili ga programer može sam podesiti.
Takav program (u stvarnosti, modul ili funkcija) naziva se generator pseudo-slučajnih brojeva. Standardna Python biblioteka uključuje random modul. Sadrži mnoge funkcije vezane za emulaciju slučajnosti (na primjer, "promiješavanje" elemenata niza), a ne samo funkcije za generiranje pseudo-slučajnih brojeva.
Ovaj vodič će vas provesti kroz random (), randrange () i randint () funkcije iz random modula. Imajte na umu da random modul sadrži random () funkciju istog imena. Dešava se.
Da biste pristupili funkcijama, morate uvesti nasumični modul:
>>> uvezi nasumično
Ili uvezite pojedinačne funkcije iz njega:
>>> iz slučajnog uvoza random, randrange, randint
Funkcije za dobivanje cijelih "slučajnih" brojeva - randint () i randrange ()
Funkcije randint () i randrange () generiraju pseudo-slučajne cijele brojeve. Prvi je najjednostavniji i uvijek uzima samo dva argumenta - granice cijelog raspona iz kojih se bira bilo koji broj:
>>> nasumični .randint (0, 10) 6
ili (ako su pojedinačne funkcije uvezene):
>>> randint (100, 200) 110
U slučaju randint (), obje granice su uključene u raspon, odnosno, jezikom matematike, segment se opisuje kao.
Brojevi mogu biti negativni:
>>> nasumični .randint (-100, 10) -83 >>> nasumični .randint (-100, -10) -38
Ali prvi broj uvijek mora biti manji ili barem jednak drugom. To jest, a<= b.
Funkcija randrange () je složenija. Može potrajati jedan argument, dva ili čak tri. Ako je naveden samo jedan, onda vraća nasumični broj između 0 i navedenog argumenta. Štaviše, sam argument nije uključen u raspon. Na jeziku matematike, ovo je)
