Шта је генератор случајних бројева?
Генератор случајних бројева (RNG) је систем који производи случајне или псеудослучајне бројеве. Да ли се следећи број заиста може предвидети зависи од врсте генератора. Неки генератори се ослањају на физички процес, неки израчунавају бројеве помоћу алгоритма, а неки алгоритми су пројектовани тако да чак ни неко ко је видео њихове претходне резултате не може да предвиди шта следи. Изгледати случајно и бити непредвидив су различита својства, и највећи део овог чланка посвећен је управо тој разлици.
Хардверски генератори случајних бројева
Хардверски генератор случајних бројева (HRNG), који се назива и прави генератор случајних бројева (TRNG), добија своје бројеве из физичког процеса. Најстарији раде пред нашим очима: бачени новчић, бачена коцкица, точак рулета. Механика у потпуности описује сваки од њих, али добро направљен точак у пракси је и даље непредвидив, јер мале разлике у начину покретања сваког окретања прерастају у потпуно различите исходе.
Савремени хардверски генератори уместо тога мере микроскопске појаве: сачмени и термални шум у електронским колима, атмосферски шум, квантне ефекте. То су добри извори ентропије — мерљиве непредвидивости — али физички извор по својој природи није савршен: може имати неуједначене шансе, може временом одступати или отказати, па се његов квалитет мора процењивати и пратити, а његови резултати по потреби додатно обрађивати, што описују стандарди као што је NIST SP 800-90B. Хардверски извори се користе тамо где је гаранција најважнија — пре свега у криптографији, где обезбеђују непредвидив полазни материјал за кључеве у протоколима као што је Transport Layer Security (TLS).
Генератори псеудослучајних бројева
Алтернатива физичком уређају је алгоритам. Генератор псеудослучајних бројева (PRNG) производи низ који изгледа случајно, али је у потпуности одређен почетном вредношћу (енгл. seed). Дајте исту почетну вредност истом алгоритму и сваки пут ћете добити исти низ. То је слабост свуда где резултат мора бити непредвидив и где се почетна вредност или унутрашње стање могу погодити или реконструисати, а предност свуда где резултат мора бити поновљив — симулација или тест могу се поново покренути на потпуно исти начин. PRNG генератори су такође брзи, јефтини и лаки за имплементацију, због чега се већина софтвера ослања на њих. Међу познате породице спадају линеарни конгруентни генератор (LCG), генератори xorshift и Mersenne Twister.
Mersenne Twister
Mersenne Twister, који су 1997. године објавили Макото Мацумото и Такуји Нишимура, један је од најчешће коришћених генератора псеудослучајних бројева и подразумевани избор у многим програмским језицима. Његово име потиче од његовог периода — дужине низа пре него што почне да се понавља — који у стандардној варијанти MT19937 износи Мерсенов прости број 219937 − 1. Пролази већину статистичких тестова случајности и добро одговара симулацијама. Међутим, није пројектован за чување тајни: из 624 узастопна 32-битна излазна резултата свако може реконструисати његово унутрашње стање и предвидети сваку вредност која следи, тако да се не сме користити за кључеве, лозинке или било шта друго што мора остати непредвидиво.
Криптографски сигурни генератори и ентропија
Многим применама потребне су обе ствари одједном: брзина алгоритма и непредвидивост физичког извора. Одговор је криптографски сигуран генератор псеудослучајних бројева (CSPRNG). То је и даље PRNG, али направљен тако да увид у део његових резултата не пружа практичан начин да се предвиди остатак, а његова почетна вредност се редовно обнавља из извора праве ентропије. Почетна вредност из физичког извора не чини обичан PRNG сигурним; сам алгоритам мора бити пројектован за то. Физички извор, као што је термални шум или време хардверских догађаја, пружа малу количину праве случајности, а CSPRNG из ње знатно брже добија дугачак низ вредности. Ову комбинацију оперативни систем нуди програмима који се на њему извршавају, и то је оно што „генератор случајних бројева” данас обично значи у пракси. Он производи кључеве за шифровање, токене сесија и лозинке.
Случајни бројеви у прегледачу
JavaScript пружа веб-страници два уграђена начина за добијање случајних вредности, и они припадају различитим класама. Math.random() је обичан PRNG: стандард језика препушта алгоритам сваком прегледачу и не гарантује ништа у погледу сигурности — добро за анимацију, неподесно за извлачење које би неко могао оспорити. Други је Web Crypto API. Његов метод crypto.getRandomValues() враћа криптографски сигурне случајне вредности, које производи CSPRNG покренут ентропијом оперативног система.
Наш генератор случајних бројева на мрежи користи Web Crypto API за свако извлачење, а бројеви се производе у вашем прегледачу, а не на серверу. Исти извор покреће и остале генераторе на овом сајту, било да бацате коцкице, бацате новчић или генеришете лозинку.
Од случајних битова до броја у вашем распону
Криптографски сигуран генератор је само половина поштеног извлачења. Он испоручује сирове битове, а програм их још мора претворити у број у вашем распону — и ту се могу јавити неуједначене шансе. Претпоставимо да извор даје вредности од 0 до 9 са једнаким шансама, а вама је потребан број од 0 до 5. Узимање остатка при дељењу са 6 изгледа природно, али се 0, 1, 2 и 3 тада могу добити на два начина, а 4 и 5 на само један, па сваки од бројева од 0 до 3 има шансу од 20%, а 4 и 5 само по 10%. Један од начина да се уклоне неуједначене шансе (енгл. modulo bias) јесте одбацивање вредности које се не уклапају и поновно извлачење; материјали о случајним бројевима детаљно се баве овим питањем.
Још две ствари често изненаде људе. Понављања су нормална: када се цео број од 1 до 10 извлачи независно и сваки број једнако је вероватан, управо извучени број има исту шансу 1 од 10 да се поново појави као и било који други. Извлачење без понављања је другачија врста извлачења, а не случајнија. Такође, поштен генератор сам по себи не чини целокупан поступак поштеним: листа учесника и број покушаја подједнако су важни, као што објашњава наш чланак о томе како изабрати победника наградне игре.