Што такое генератар выпадковых лікаў?
Генератар выпадковых лікаў (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%. Адзін са спосабаў ліквідаваць такое зрушэнне — адкідаць непадыходныя значэнні і выбіраць зноў; матэрыялы пра генератар выпадковых лікаў разглядаюць гэта падрабязна.
Людзей часта здзіўляюць яшчэ дзве рэчы. Паўторы — гэта нармальна: калі цэлы лік ад 1 да 10 выбіраецца незалежна і ўсе лікі роўнаімаверныя, то толькі што атрыманы лік мае такі ж шанец 1 з 10 з'явіцца зноў, як і любы іншы. Выбар без паўтораў — гэта іншы тып розыгрышу, а не больш выпадковы. І адзін толькі сумленны генератар не робіць усю працэдуру справядлівай: спіс удзельнікаў і колькасць спроб важныя не менш, як тлумачыць наш артыкул пра тое, як выбраць выпадковага пераможцу конкурсу.