Какво е генератор на случайни числа?
Генераторът на случайни числа (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 да се падне отново, както всяко друго. Тегленето без повторения е просто различен вид теглене, а не по-случайно. Освен това само честният генератор не гарантира честността на цялата процедура: списъкът с участници и броят на опитите имат също толкова голямо значение, както обяснява нашата статия за това как да изберете случаен победител в конкурс.