Iz prakse: Pravi slučajni brojevi

Slučajni brojevi su važni za kriptografiju, simulacije, igre i niz drugih primena. Svaki računar će lako generisati slučajne brojeve, samo što ti brojevi nisu zaista slučajni – između njih postoji neka relacija. Ako vam trebaju pravi slučajni brojevi, nabavite uređaj kao što je TrueRNGpro.

U većini programskih jezika postoji funkcija koja se zove rnd, random ili nešto slično tome i koja generiše slučajni broj, obično između 0 i 1. Ako vam je potrebno da, recimo, simulirate bacanje kockice, slučajan broj ćete pomnožiti sa 6, uzeti ceo deo proizvoda i dodati mu 1. Zvuči sasvim jednostavno i funkcioniše savršeno, sve dok se ne zapitate kako računar zapravo generiše slučajni broj.

(Pseudo)slučajnost…

Računar je precizno determinisan sistem koji na iste ulaze uvek daje iste izlaze – nema u njegovom radu ničeg nasumičnog. Kako onda može da nastane slučajni broj? U većini situacija koriste se pseudoslučajni brojevi, dakle brojevi između kojih postoji neka relacija, ali je ona tako izabrana da dobijeni niz brojeva daje privid slučajnosti. Pa i više od privida – matematičari su napravili čitav niz testova koji treba da pokažu da li je neki niz brojeva slučajan (najjednostavniji test: ako generišete mnogo slučajnih brojeva između 0 i 1 sa uniformnom raspodelom, trebalo bi da njihova srednja vrednost bude približno 0.5), ali su napravili i algoritme za generisanje brojeva koji prolaze te testove, iako zapravo nisu slučajni.

Avalanche efekat ili lavinski proboj, naglo povećanje jačine struje koja teče kroz inverzno polarisanu Zener diodu, stvara šum koji se pogodnim putem pretvara u niz pravih slučajnih brojeva

Najčešće se koristi linearni kongruencioni generator koji su krajem pedesetih godina prošlog veka osmislili W. E. Thomson i A. Rotenberg. Metod je brz, lako ga je razumeti i implementirati a rezultati su odlični. On generiše niz brojeva X1, X2, X3, … između kojih postoji relacija Xn+1 = (a*Xn + c) mod m, gde su a, c i m pogodno izabrane konstante. Recimo Knuth‑ov MMIX koristi m=264, a=6364136223846793005, c=1442695040888963407 dok programski jezik C++ (minstd_rand) koristi m=231‑1, a=48271, c=0. Ako želite nešto jednostavnije, stari dobri Sinclair ZX‑81 je koristio m=216+1, a=75, c=74 dok je još stariji TI‑59 koristio m=199017, a=24298, c=99991. Sve ove kombinacije parametara će dati niz pseudoslučajnih brojeva koji polaže svaki osmišljeni test slučajnosti.

Pošto se kod kongruencionog generatora sledeći broj računa na osnovu prethodnog, jasno je da za čitav postupak treba zadati X0, prvi broj u nizu od koga računanje počinje. Taj broj zovemo seed („seme“), pri čemu isti seed uvek generiše isti niz pseudoslučajnih brojeva. To je veoma zgodno kod testiranja programa, pošto uvek imate isti niz „slučajnih“ događaja pa lakše možete da ponovite eventualnu grešku. Kada završite testiranje, za prvi broj treba izabrati nešto slučajno kako bi korisnik, recimo, uvek dobijao drugačiju partiju igre. Odakle taj slučajni broj, kad smo rekli da u računaru ništa nije slučajno? Pa, sve dok se radi o jednom slučajnom broju, može se nešto smisliti, recimo broj milisekundi u tekućem vremenu ili čak stanje nekog sistemskog registra (kod zaštita za Spectrum kao izvor slučajnih brojeva korišćen je R (Refresh) registar procesora Z80). Važno je zapamtiti da na osnovu jednog broja kongruencioni algoritam pravi veoma dug niz „slučajnih“ brojeva.

…i njena ograničenja

U čemu je problem sa pseudoslučajnim brojevima? Problema nema, ali ostaje činjenica da među njima postoji neka (u ovom slučajno sasvim jednostavna) relacija. Uzmimo primer kriptografije – želimo da primenimo one‑time pad, jedinu šifru koja je za sva vremena neprobojna. Svaki bajt otvorenog teksta XOR‑ujemo sa slučajnim brojem i rezultat prosleđujemo korespondentu; ako on ima isti niz slučajnih brojeva, lako će dešifrovati poruku, dok je neko ko presretne šifrovani tekst potpuno nemoćan nad njim, pošto su svi slučajni nizovi jednako verovatni, pa se tajanstvena poruka može pretvoriti u bilo koji tekst odgovarajuće izabranim slučajnim brojevima.

Sve ovo važi ako su brojevi slučajni, ali ne i ako su pseudoslučajni. Napadač ne zna seed, verovatno ne zna ni brojeva a, c, m, ali zna da relacija postoji i to može biti osnova za napad na šifru. Napad nije jednostavno osmisliti, Donald Knuth na samom kraju sekcije 3.6 drugog toma njegove slavne trilogije The Art of Computer Programming daje to kao zadatak za vežbu i označava ga kao veoma težak, a i ja sam ga dao kao „nezvaničnu Dejanovu pitalicu“ u Računarima 88 (januar 1993). Tada su ga rešili Vladimir Božin i Nikola Bulatović, tada studenti, kasnije svetski priznati matematičari. Ukratko, razbijanje takve šifre nije jednostavno, ali je moguće. Zato treba koristiti prave slučajne brojeve. Samo, kako doći do njih?

Zener dioda na zadatku

Prave slučajne brojeve možemo da generišemo tako što ćemo bacati novčić, još bolje kockicu, pratiti protok automobila u nekoj raskrsnici, precizno snimati vremena između pritiska na dva tastera i na mnogo drugih načina. Najbolje je koristiti neki zgodan fizički proces, a najbolji rezultati dobijaju se primenom kvantnih efekata ili radioaktivnog raspada. Ako ne želite atomski reaktor u sobi, potražićete nešto jednostavnije. Recimo avalanche efekat ili lavinski proboj, naglo povećanje jačine struje koja teče kroz inverzno polarisanu Zener diodu. Nećemo se ovde mnogo upuštati u elektroniku, samo ćemo reći da ovaj efekat stvara šum koji se pogodnim putem pretvara u niz pravih slučajnih brojeva.

Da biste sve to isprobali, potreban je odgovarajući uređaj pa smo na Amazon.com‑u za oko 100 dolara kupili TrueRNGpro, koji generiše slučajne brojeve impozantnom brzinom od 3.2 Mbps i šalje ih računaru preko USB porta. Uz to ima i LED diode koje u svakom trenutku prikazuju kako stvari (brojevi) teku, a rezultati na sajtu proizvođača sasvim dobro prolaze na testovima slučajnosti.

Ostalo je samo da pustimo uređaj u pogon, što se pokazalo prilično komplikovanim zadatkom. Zapravo, moram da kažem da decenijama nisam testirao uređaj koji bi bio ovoliko user‑unfriendly. Valjda se smatra da kupac ovakve sprave veoma dobro zna šta radi i da je to haker kome ne treba mnogo toga objašnjavati…

Od kutije do brojeva

Uređaj stiže bez ikakvog uputstva, na njemu postoji USB port i četiri diode. Dobro, da ga priključim na računar pa da vidim šta će biti. Onda primetih da je priključak mini USB, koji nisam video već godinama (Kindle ima microUSB što je već antičko, a ovo je kameno doba). Morao sam duboko da zaronim u donje fioke ormana da nađem kabl. Najzad ga uključim, upale se tri sijaličice i – ništa. Gledam po Device Manager‑u, pojavio se neki fantomski COM port za koji nema drajvera.

Odem na sajt proizvođača, preuzmem drajver, instaliram ga (desni klik na .INF fajl pa Install, nisam to radio godinama). Računar pronađe uređaj, ispiše Setting up your device i sve prođe dobro, ali i dalje se ništa ne dešava. Pogledam u Device Manager, postoji port COM4, ali šta sa njim? Probam da pokrenem Windows Terminal, ali uzalud, nema više Windows Terminal‑a u Windows‑u (!?). Probam Netterm, ne može da se poveže na COM port. Nađem neki drugi komunikacioni klijent, instaliram, probam da podesim brzinu, parnost, broj stop bitova… razne varijante i – ništa.

Matematičari su napravili testove koji treba da pokažu da li je neki niz brojeva slučajan, ali i algoritme za generisanje brojeva koji prolaze te testove, iako zapravo nisu slučajni

Najzad pronađem da proizvođač ima svoj Github nalog na kome su neki skriptovi za Python. Recimo install_python_libs.bat. Zvuči kao dobar početak. Pokrenem, kad on počne da mi grdi Python da je mator, pa da mi je pip mator, pa svaki drugi red po neka greška… Šta ću, instaliram najnoviji Python, najnoviji pip, pustim sve ponovo, prođe. Pokrenem test, a on nešto radi, radi, radi, radi, radio jedno 10 minuta i na kraju kaže… ništa. Samo izađe napolje. Ali nikakvu grešku ne prijavljuje.

Najzad pokrenem program truerng_read_example.py, on malo mulja i završi rad bez ikakve poruke. Ali kad sam pogledao u folder, nastao je fajl random.bin sa megabajtom slučajnih brojeva. Podvrgao sam ih nizu standardnih testova (Dieharder, ENT, Rngtest) i zaista deluju slučajno. Eto dobre osnove za kriptografsku zabavu…

Korisna adresa: ubld.it/products/truerngpro