Deterministički PRNG-ovi
PRNG-ovi (PRNG-ovi) su generatori pseudo-slučajnih brojeva. Isti izraz se često koristi za opisivanje PRBG - generatora pseudo-slučajnih bitova, kao i raznih stream šifri. PRNG-ovi, poput šifri toka, sastoje se od unutarnjeg stanja (veličine od 16 bita do nekoliko megabajta), funkcije za inicijalizaciju unutarnjeg stanja ključem ili sjemenkama, funkcije ažuriranja unutarnjeg stanja i izlazne funkcije. PRNG-ovi se dijele na jednostavne aritmetičke, pokvarene kriptografske i kriptografske jake. Njihova je opća svrha generirati nizove brojeva koji se ne mogu razlikovati od slučajnih.
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, "Svatko tko ima slabost prema aritmetičkim metodama za dobivanje slučajnih brojeva je bez sumnje grešnik".
Svaki PRNG s ograničenim resursima prije ili kasnije zapne. Duljina PRNG ciklusa ovisi o samom generatoru i u prosjeku iznosi oko 2 (n/2) gdje je n veličina unutarnjeg stanja u bitovima, iako linearno-kongruencijalni generatori i LFSR generatori imaju maksimalne cikluse reda veličine 2 n . Ako PRNG može konvergirati u cikluse koji su prekratki, taj PRNG postaje predvidljiv i neupotrebljiv.
Većina jednostavnih aritmetičkih generatora, iako brzi, pati od mnogih ozbiljnih nedostataka:
- Prekratko razdoblje/razdoblja
- Uzastopne vrijednosti nisu neovisne
- Neki bitovi su "manje slučajni" od drugih
- Nejednolika univarijantna distribucija
- reverzibilnost
Konkretno, RANDU algoritam, koji se desetljećima koristio u računalima, pokazao se vrlo lošim. Kao rezultat toga, mnoge studije su manje pouzdane nego što bi mogle biti.
PRNG s izvorom entropije 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 "generatori slučajnih 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 iz kombinacije kriptografski jakog PRNG-a i vanjskog izvora. Stoga je pod RNG-om sada uobičajeno podrazumijevati PRNG-ove otporne na kripto-otpornost s vanjskim izvorom entropije.
Gotovo svi glavni proizvođači mikročipova opskrbljuju hardverske RNG-ove s različitim izvorima entropije, koristeći različite metode kako bi ih očistili od neizbježne predvidljivosti. Međutim, na ovaj trenutak brzina prikupljanja slučajnih brojeva od strane svih postojećih mikročipova (nekoliko tisuća bita u sekundi) ne odgovara brzini modernih procesora.
Na osobnim računalima autori softvera RNG koriste mnogo brže izvore entropije, kao što su šum zvučne kartice ili vrijednosti brojača takta procesora koje se lako čitaju, na primjer, korištenjem uputa u Intelovim procesorima. Prije pojave u procesorima sposobnosti čitanja vrijednosti najosjetljivijih na najmanje promjene u okruženju, brojač ciklusa procesora, prikupljanje entropije bila je najranjivija točka RNG-a. Taj problem još uvijek nije u potpunosti riješen u mnogim uređajima (npr. pametnim karticama), koji stoga ostaju ranjivi. Mnogi RNG-ovi još uvijek koriste tradicionalne (zastarjele) metode prikupljanja entropije kao što su radnje korisnika (pokreti miša, itd.), kao što su i Stolisnik, ili interakcija između niti, kao što je u Java secure random.
Evo nekoliko primjera RNG-ova s njihovim entropijskim izvorima i generatorima:
- /dev/random in / - izvor entropije: , međutim, prikuplja se samo tijekom hardverskih prekida; PRNG: LFSR, s izlazom raspršenim putem ; prednosti: dostupan u svim Unixima, pouzdan izvor entropije; nedostaci: jako dugo se "grije", može se "zaglaviti" dugo vremena ili radi kao PRNG ( /dev/urandom);
- Stolisnik iz - izvor entropije: tradicionalne (zastarjele) metode; PRNG: AES-256 i malo unutarnje stanje; prednosti: fleksibilan dizajn otporan na kripto; nedostaci - dugo se "grije", vrlo malo unutarnje stanje, previše ovisi o kriptografskoj snazi odabranih algoritama, spor je, primjenjiv samo za generiranje ključeva;
- generator od Leonida Yurieva (Leo Yuriev) - izvor entropije: šum zvučne kartice; PRNG: još nije poznato; prednosti: najvjerojatnije dobar i brz izvor entropije; nedostaci - nema neovisnog, očito otpornog na kripto PRNG, dostupan je samo kao DLL za Windows;
- Microsoft CryptoAPI - izvor entropije: trenutno vrijeme, veličina tvrdog diska, veličina slobodne memorije, ID procesa i NETBIOS naziv računala; PRNG: 128-bitni interni hash stanja (haš dostupan samo na 128-bitnim verzijama sustava Windows); prednosti - ugrađen u Windows, ne "zapinje"; nedostaci - malo unutarnje stanje, lako predvidljivo;
- Java SecureRandom - izvor entropije: interakcija između niti (niti); PRNG: hash internog stanja (1024 bita); prednosti - u Javi još nema drugog izbora, veliko interno stanje; nedostaci: sporo prikupljanje entropije, iako u Javi još uvijek nema drugog izbora;
- Kaos iz Ruptora - izvor entropije: , prikuplja se kontinuirano; PRNG: 4096-bitno interno raspršivanje stanja na temelju nelinearne verzije Marsaglia generatora; prednosti: dok najbrži od svih, veliko unutarnje stanje, ne "zapinje".
Hardverski PRNG
Osim zastarjelih dobro poznatih LFSR generatora koji su se u prošlom stoljeću naširoko koristili kao hardverski PRNG-ovi, nažalost vrlo se malo zna o modernim hardverskim PRNG-ovima (stream ciphers), budući da je većina njih razvijena u vojne svrhe i čuva se u tajnosti. Gotovo svi postojeći komercijalni hardverski PRNG-ovi patentirani su i također se čuvaju u tajnosti. Hardverski PRNG-ovi ograničeni su strogim zahtjevima za potrošnju memorije (najčešće korištenje memorije je zabranjeno), brzinu (1-2 ciklusa) i površinu (nekoliko stotina FPGA ili ASIC ćelija). Zbog tako strogih zahtjeva za hardverski PRNG, vrlo je teško stvoriti generator otporan na kriptovalute, stoga su do sada svi poznati hardverski PRNG-ovi bili pokvareni. Primjeri takvih generatora su Toyocrypt i LILI-128, koji su LFSR generatori i oba su pokvarena algebarskim napadima.
Zbog nedostatka dobrih hardverskih PRNG-ova, proizvođači su prisiljeni koristiti puno sporije, ali nadaleko poznate blok šifre poput AES-a i hash funkcija kao što su
Prva široko korištena tehnologija za generiranje slučajnog broja bio je algoritam koji je predložio Lehmer, a koji je poznat kao linearna kongruentna metoda. Ovaj algoritam je parametriran s četiri broja kako slijedi:
Niz slučajnih brojeva (X n ) dobiva 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 se stvara niz cijelih brojeva u rasponu 0 X n< m.
Izbor vrijednosti za a, c i m ključan je za razvoj dobrog generatora slučajnih brojeva.
Očito, m mora biti vrlo velik da bi mogao generirati mnogo slučajnih brojeva. Vjeruje se da bi m trebao biti približno jednak maksimalnom pozitivnom cijelom broju za ovo računalo. Dakle, obično je m blizu ili jednako 2 31 .
Prilikom odabira generatora slučajnih brojeva koriste se tri kriterija:
1. Funkcija mora stvoriti puno razdoblje, t.j. svi brojevi između 0 i m prije nego što se generirani brojevi počnu ponavljati.
2. Generirani slijed mora se pojaviti nasumično. Slijed nije slučajan jer je generiran deterministički, ali različiti statistički testovi koji se mogu primijeniti trebali bi pokazati da je slijed slučajan.
3. Funkcija mora biti učinkovito implementirana na 32-bitnim procesorima.
Vrijednosti a, c i m moraju se odabrati na način da su ispunjena ova tri kriterija. U skladu s prvim kriterijem, može se pokazati da ako je m prost i c = 0, tada će za određenu vrijednost a razdoblje koje stvara funkcija biti jednako 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 a zadovoljava sva tri kriterija. Jedna takva vrijednost je a = 7 5 = 16807, koja se koristila u obitelji računala IBM 360. Ovaj generator ima široku primjenu i prošao je više od tisuću testova, više od svih ostalih generatora pseudoslučajnih brojeva.
Snaga linearnog kongruentnog algoritma je da ako su faktor i modul (baza) pravilno odabrani, tada će se rezultirajući niz brojeva biti statistički nerazlučiv od niza koji je slučajan 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. To 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 poznat . Čak i ako protivnik samo zna da se koristi linearni kongruentni algoritam, poznavanje malog dijela niza dovoljno je za određivanje parametara algoritma i svih sljedećih brojeva. Pretpostavimo da neprijatelj može odrediti vrijednosti X 0 , X 1 , X 2 , X 3 . Zatim:
X 1 \u003d (a X 0 + c) mod mX 2 = (a X 1 + c) mod mX 3 = (a X 2 + c) mod m
Ove jednakosti nam omogućuju da pronađemo a, c i m.
Dakle, iako je algoritam dobar generator pseudoslučajnog niza brojeva, poželjno je da sekvenca koja se zapravo koristi bude nepredvidljiva, jer u ovom slučaju poznavanje dijela niza neće omogućiti određivanje njegovih budućih elemenata. . Taj se cilj može postići na nekoliko načina. Na primjer, korištenje internog sata sustava za izmjenu toka slučajnih brojeva. Jedan od načina korištenja sata je ponovno pokretanje niza nakon N brojeva, koristeći trenutnu vrijednost sata po modulu m kao novu početnu vrijednost. 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 generator kvadratnog ostatka. Za potrebe kriptografije, ova metoda je predložena 1986. godine.To je kako slijedi. Prvo, dva velika prosta broja 1 Pozitivan cijeli broj veći od jedan se zove jednostavan, ako nije djeljiv ni s jednim brojem osim sobom i jedinicom. Za više informacija o prostim brojevima, pogledajte "Osnove teorije brojeva korištene u kriptografiji javnog ključa". p i q brojevi. Brojevi p i q moraju biti oba usporedivi s 3 po modulu 4, odnosno pri dijeljenju p i q s 4, treba dobiti isti ostatak 3. Zatim se izračunava broj M = p * q, nazvan Bloomov cijeli broj. Zatim se odabire drugi nasumični cijeli broj x, koprost (tj. nema zajedničkih djelitelja osim jednog) s M. Izračunaj x0= x 2 mod M . x 0 naziva se početnim brojem generatora.
Na svakom n-tom koraku generatora izračunava se x n+1 = x n 2 mod M. Rezultat n-tog koraka je jedan (obično najmanje značajan) bit od x n+1. Ponekad se kao rezultat uzima paritetni bit, odnosno broj jedinica u binarnom prikazu elementa. Ako je broj jedinica u unosu broja 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 . Odabiremo x jednako prost s M : neka je x = 3 . Izračunajte početni broj generatora x 0:
x 0 = x 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.
Izračunajte prvih deset brojeva x i koristeći BBS algoritam. Uzet ćemo najmanji bitni bit u binarnom prikazu broja x i kao slučajne bitove:
| x 1 = 9 2 mod 209= 81 mod 209= 81 | niski bit: | 1 |
| x 2 = 81 2 mod 209 = 6561 mod 209 \u003d 82 | niski bit: | 0 |
| x 3 = 82 2 mod 209= 6724 mod 209= 36 | niski bit: | 0 |
| x 4 = 36 2 mod 209= 1296 mod 209= 42 | niski bit: | 0 |
| x 5 = 42 2 mod 209= 1764 mod 209= 92 | niski bit: | 0 |
| x 6 = 92 2 mod 209= 8464 mod 209= 104 | niski bit: | 0 |
| x 7 = 104 2 mod 209 = 10816 mod 209 \u003d 157 | niski bit: | 1 |
| x 8 = 157 2 mod 209 = 24649 mod 209 \u003d 196 | niski bit: | 0 |
| x 9 = 196 2 mod 209 = 38416 mod 209 \u003d 169 | niski bit: | 1 |
| x 10 = 169 2 mod 209 = 28561 mod 209 \u003d 137 | niski bit: | 1 |
Najzanimljivije svojstvo ove metode za praktične svrhe je da za dobivanje 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, stvarno smo dobili istu vrijednost kao u sekvencijalnom izračunu, - 137 . Izračuni se čine prilično kompliciranim, ali zapravo ih je lako zamotati u mali postupak ili program i koristiti kada je to potrebno.
Mogućnost dobivanja xn "izravno" omogućuje korištenje BBS algoritma za stream enkripciju, na primjer, za datoteke slučajnog pristupa ili fragmente datoteka sa zapisima baze podataka.
Sigurnost BBS algoritma temelji se na poteškoći faktorizacije velikog broja M. Tvrdi se da ako je M dovoljno velik, ne mora se čak ni držati u tajnosti; dok se M ne izvuče, nitko ne može predvidjeti izlaz PRNG generatora. To je zbog činjenice da je problem faktoriranja brojeva oblika n = pq (p i q su prosti brojevi) u faktore računski vrlo težak ako znamo samo n, a p i q su veliki brojevi koji se sastoje od nekoliko desetica ili stotine bitova (ovaj tzv problem faktorizacije).
Osim toga, može se dokazati da napadač, znajući neki niz koji generira BBS generator, neće moći odrediti ni prethodne niti sljedeće bitove. BBS generator nepredvidivo u lijevom smjeru i u pravom smjeru. Ovo svojstvo je vrlo korisno za potrebe kriptografije, a povezano je i s osobitostima faktorizacije broja M.
Najznačajniji nedostatak algoritma je taj što nije dovoljno brz, što ne dopušta da se koristi u mnogim područjima, na primjer, u izračunima u stvarnom vremenu, i, nažalost, u stream enkripcija.
Ali ovaj algoritam proizvodi stvarno dobar slijed pseudo-slučajnih brojeva s velikim periodom (s odgovarajućim izborom početnih parametara), što mu omogućuje da se koristi u kriptografske svrhe pri generiranju ključeva za šifriranje.
Ključni pojmovi
stream šifra- stream šifra.
BBS algoritam je jedna od metoda za generiranje pseudoslučajnih brojeva. Naziv algoritma potječ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 umnožak dvaju velikih prostih brojeva 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 pseudoslučajni brojevi jedan je od najjednostavnijih PRNG-ova koji koristi formulu k i =(a*k i-1 +b)mod c za izračunavanje sljedećeg broja k i , gdje su a, b, c neke konstante, a k i-1 je prethodni pseudoslučajni broj.
Fibonaccijeva metoda s odgodama je jedna od metoda za generiranje pseudoslučajnih brojeva. Može se koristiti u kriptografiji.
Stream šifra je šifra koja šifrira ulaznu poruku jedan bit (ili bajt) po operaciji. Inline enkripcijski algoritam eliminira potrebu za cijepanjem poruke na cijeli broj blokova. Stream šifre se koriste za šifriranje podataka u stvarnom vremenu.
Kratak sažetak
Tokovna šifra je šifra koja šifrira ulaznu poruku jedan bit (ili bajt) po operaciji. Inline enkripcijski algoritam eliminira potrebu za cijepanjem poruke na cijeli broj blokova. Dakle, ako se prenosi niz znakova, svaki znak se može šifrirati i prenijeti odjednom. Stream šifre se koriste za šifriranje podataka u stvarnom vremenu.
U računalnim programima često je potrebno oponašati slučajnost. Na primjer, prilikom razvoja igara. Ako program ima određeni generator, tj. proizvođača, slučajnog broja, tada se pomoću tako dobivenog broja može izabrati jednu ili drugu granu izvršavanja programa, ili proizvoljan objekt iz kolekcije. Drugim riječima, glavna stvar je generirati broj. Na njemu se temelji emulacija slučajnosti druge vrste.
Zasigurno ne znamo postoji li nezgoda u prirodi ili nam se to samo čini zbog ograničenog znanja našeg znanja. Znamo samo da u programiranju nema prave slučajnosti. Nigdje uzeti proizvoljan broj, ne možete programirati njegov izgled niotkuda. Možete stvoriti samo program koji će, kao rezultat primjene složene formule na "sjeme", proizvesti broj, a činit će nam se da je taj broj slučajan.
"Zrno" je početni podatak za formulu. To može biti, na primjer, sustavno vrijeme u milisekundama, koje se stalno mijenja. Stoga će "zrno" biti stalno drugačije. Ili ga programer može sam postaviti.
Takav program (zapravo modul ili funkcija) naziva se generator pseudoslučajnih brojeva. Python standardna biblioteka uključuje nasumični modul. Sadrži puno funkcija koje se odnose na emulaciju slučajnosti (na primjer, "promiješavanje" elemenata niza), a ne samo funkcije za generiranje pseudoslučajnih brojeva.
Ovaj vodič će pokriti funkcije random(), randrange() i randint() iz random modula. Imajte na umu da random modul sadrži random() funkciju istog imena. Događa se.
Za pristup funkcijama morate uvesti nasumični modul:
>>> uvoz nasumično
Ili uvezite pojedinačne funkcije iz njega:
>>> iz slučajnog uvoza random , randrange, randint
Funkcije za dobivanje cjelobrojnih "slučajnih" brojeva - randint() i randrange()
Funkcije randint() i randrange() generiraju pseudoslučajne cijele brojeve. Prvi od njih je najjednostavniji i uvijek uzima samo dva argumenta - granice cjelobrojnog raspona iz kojeg se odabire bilo koji broj:
>>> nasumični .randint (0 , 10 ) 6
ili (ako su uvezene zasebne funkcije):
>>> randint (100 , 200 ) 110
U slučaju randint(), obje granice su uključene u raspon, tj. jezikom matematike, segment je opisan kao .
Brojevi mogu biti negativni:
>>> nasumično .randint (-100 , 10 ) -83 >>> nasumični .randint (-100 , -10 ) -38
Ali prvi broj uvijek mora biti manji ili barem jednak drugom. To je<= 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. Štoviše, sam argument nije uključen u raspon. U jeziku matematike, to je
