Генератор чисел

Генератор випадкових чисел (ГВЧ або рандомайзер) — це система або процес, створений для генерації абсолютно непередбачуваних значень при кожному запуску. За визначенням, виявити будь-яку закономірність чи передбачити майбутні результати на основі попередніх чисел просто неможливо. Ці випадкові значення генеруються за допомогою передових математичних алгоритмів або спеціалізованих апаратних пристроїв.

Використання генераторів випадкових чисел

Генерація випадкових чисел відіграє критичну роль у величезній кількості завдань: від звичайних мобільних додатків до складних комп'ютерних ігор. Наприклад, вебсайти використовують генератор випадкових чисел для динамічного показу реклами або рандомізації контенту. У сфері кібербезпеки криптографія критично залежить від випадкових чисел — вони потрібні для створення унікальних, високозахищених шифрів та криптографічних ключів.

Загалом, рандомізація необхідна для створення капчі (CAPTCHA), шифрування конфіденційних даних, формування криптографічних солей для безпечного зберігання паролів, а також для роботи генераторів надійних паролів. Крім того, ГВЧ є основою алгоритмів тасування колод у карткових іграх та онлайн-казино, систем автоматизованого прийняття рішень, статистичної вибірки й комп'ютерного моделювання.

У геймдеві алгоритми випадкових чисел роблять ігровий процес унікальним та непередбачуваним. Навіть якщо ви проходите той самий рівень усоте, ГВЧ гарантує, що досвід не повториться. Хоча базова карта або місія залишаються незмінними, саме випадковість визначає частоту появи та розташування ворогів, динамічні зміни погоди чи раптові перешкоди. Такий рівень непередбачуваності робить ігри захопливими та стимулює грати знову і знову.

Різниця між випадковими та невипадковими послідовностями

Розглянемо таку послідовність чисел: 1 , 2 , 3 , 4 , 5. Чи дійсно вона випадкова?

У статистиці випадкова величина набуває певного значення як результат незалежного випробування. Головна умова полягає в тому, що неможливо точно передбачити появу конкретного значення до його фактичної появи.

Припустимо, що наведена вище послідовність була згенерована простим послідовним натисканням клавіш у верхньому числовому ряду стандартної клавіатури. У цьому контексті комбінація є абсолютно невипадковою. Чому? Тому що після цифри 5 наступне число, 6, можна передбачити з майже стовідсотковою впевненістю.

Послідовність вважається справді випадковою лише тоді, коли між її окремими символами або числами існує нульова залежність.

Основною умовою чесного та функціонального рандомайзера чисел є те, що кожне можливе число повинно мати абсолютно однакову ймовірність випадіння. Це гарантує повну незалежність: на поточний результат ніяк не впливають числа, згенеровані до нього, і він так само не впливатиме на майбутні результати.

Наприклад, коли ви вперше кидаєте правильний гральний кубик, будь-яке число від 1 до 6 має однакові шанси випасти. Незалежно від початкового результату, коли ви кидаєте кубик вдруге, всоте або втисячне, ваші шанси отримати те саме число залишаються абсолютно незмінними.

Багатьом нескінченна послідовність цифр у математичній константі Пі (π) здається ідеально випадковою та неповторюваною. Уявіть гіпотетичний генератор, який використовує бітове представлення числа Пі, починаючи з невідомої десяткової позиції. Такий генератор може здатися абсолютно непередбачуваним для пересічного користувача і навіть міг би пройти певні статистичні тести на випадковість. Проте покладатися на Пі для криптографії вкрай небезпечно. Якщо зловмисник розкриє конкретний сегмент числа Пі, який наразі використовується, він зможе легко вирахувати всі попередні та наступні цифри, миттєво зруйнувавши безпеку всієї системи.

Для забезпечення високих стандартів безпеки Національний інститут стандартів і технологій США (NIST) розробив «Набір статистичних тестів для генераторів випадкових і псевдовипадкових чисел для криптографічних застосунків». Цей потужний інструментарій включає 15 унікальних статистичних тестів, створених для математичного вимірювання справжньої випадковості бітів, згенерованих як апаратними, так і програмними ГВЧ.

Типи генераторів випадкових чисел

Глобально існує два основних типи генераторів випадкових чисел: генератори справжніх випадкових чисел (TRNG) та генератори псевдовипадкових чисел (PRNG). Тоді як TRNG покладаються на непередбачувані фізичні явища для генерування значень, PRNG повністю базуються на математичних алгоритмах.

Генератор справжніх випадкових чисел (TRNG) спирається на спеціалізовані апаратні компоненти, які фіксують мікроскопічні фізичні процеси. Ця фізична непередбачуваність називається ентропією — математичною мірою чистого, нефільтрованого хаосу.

Справжні апаратні ГВЧ збирають ентропію з таких надзвичайно непередбачуваних фізичних явищ:

• радіоактивність,
• тепловий шум,
• електромагнітний шум,
• квантова механіка та інші.

Завдяки своїй абсолютній непередбачуваності справжні ГВЧ (True RNG) є золотим стандартом для програмного забезпечення з високим рівнем безпеки, захищених ліній зв'язку та передового шифрування даних у всьому світі.

Ці апаратні системи використовують зовнішні джерела ентропії для збору хаотичних даних, формуючи секретне початкове значення (відоме як «seed» або зерно), необхідне для безпечної генерації захищених випадкових чисел.

Натомість алгоритм генератора псевдовипадкових чисел (PRNG) зазвичай застосовується в середовищах, де сувора криптографічна безпека не є пріоритетом. Цей тип випадковості використовується скоріше для уникнення повторень та створення цікавого користувацького досвіду. Впровадження технології PRNG є значно швидшим та економічно вигіднішим, оскільки вона не потребує спеціального обладнання і легко інтегрується у стандартний програмний код. Хоча результат є повністю детермінованим і залежить від заданого алгоритму, він ідеально підходить для відеоігор, симуляцій та базових онлайн-сервісів.

PRNG використовує єдине початкове значення (зерно), щоб математично обчислити свою псевдовипадкову послідовність. На противагу цьому, TRNG генерує високоякісні випадкові числа безперервно, постійно черпаючи свіжу ентропію з непередбачуваних фізичних джерел.

Генерація псевдовипадкових чисел має серйозні вразливості. Ці алгоритми ефективні лише тому, що їхні результати здаються хаотичними для нетренованого ока. Проте, якщо хтось дізнається початкове значення (зерно), використане для конкретної послідовності PRNG, він зможе зі стовідсотковою точністю передбачити кожне наступне згенероване число.

Спідранери (speedrunners) — геймери, які прагнуть пройти відеоігри якомога швидше — часто використовують цю вразливість у техніці, що отримала назву «маніпуляція ГВЧ». За допомогою зворотного інжинірингу зерна вони змушують гру поводитися передбачувано, заощаджуючи дорогоцінні секунди. У геймінгу такі маніпуляції є нешкідливими і рідко призводять до критичних проблем.

Однак у світі кібербезпеки можливість передбачити випадкові числа — це катастрофа, особливо коли йдеться про генерацію криптографічних ключів безпеки.

Якщо хакер дізнається початкове зерно, використане для генерації ключів RSA для TLS-сертифікатів, він зможе розшифрувати захищений мережевий трафік. Це дасть йому змогу легко перехоплювати паролі, банківські дані та іншу вкрай конфіденційну інформацію, що передається через інтернет.

Саме тому в таких критичних сценаріях використання винятково надійного методу — генератора справжніх випадкових чисел — є абсолютною необхідністю.

Генератор від Google

Google пропонує власний вбудований генератор випадкових чисел, написаний на JavaScript. Цей загальнодоступний інструмент є надзвичайно зручним для швидких повсякденних завдань — наприклад, для кидання віртуальних гральних кубиків під час настільних ігор з друзями. Ви можете легко скористатися цим нативним PRNG, просто ввівши пошуковий запит «random number generator» або «генератор випадкових чисел» безпосередньо в пошуковику Google.

Лінійний конгруентний метод

Одним із найстаріших і найвідоміших алгоритмів для генераторів псевдовипадкових чисел є лінійний конгруентний метод (LCM) або лінійний конгруентний генератор (LCG). Розроблений Дерріком Генрі Лемером у 1949 році, цей алгоритм чудово підходить для простих завдань, де рівень безпеки не є критичним, оскільки він абсолютно позбавлений криптографічної стійкості.

Щоб успішно згенерувати послідовність чисел за допомогою цієї математичної моделі, необхідно визначити чотири ключові параметри:

m > 0, модуль

0 ≤ a ≤ m, множник

0 ≤ c ≤ m, приріст

0 ≤ X₀ ≤ m, початкове число

Сама псевдовипадкова послідовність чисел обчислюється рекурсивно за допомогою такої математичної формули:

Xₙ₊₁ = (aXₙ + c) mod m

Варто зазначити, що ефективність та уявна випадковість цього методу цілком і повністю залежать від ретельного вибору цих початкових параметрів.

Наприклад, якщо ми застосуємо невдало підібраний набір параметрів:

X₀ = 3, a = 4, c = 5, m = 6

ми в результаті отримаємо дуже циклічну послідовність, що постійно повторюється:

3, 5, 1, 3, 5, 1

що, очевидно, зовсім не виглядає випадковим.

Але якщо ми змінимо параметри на значно більший і ретельно продуманий набір:

X₀ = 2, a = 85, c = 507, m = 1356

Розподіл результатів миттєво стає набагато більш непередбачуваним і рівномірним. Це наочно демонструє, чому обирати початкові числа для цього алгоритмічного генератора слід з максимальною обережністю:

2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365...

Хоча добре оптимізований лінійний конгруентний генератор здатний створити статистично прийнятну псевдовипадкову послідовність, він є фундаментально вразливим. Оскільки LCG за своєю природою детерміновані та передбачувані (якщо їхні параметри відомі або їх можна відстежити), їм критично бракує криптографічної стійкості, тому їх у жодному разі не можна використовувати для захисту конфіденційних даних.

Генератори, що покладаються на лінійні конгруентні методи, були вперше успішно зламані Джимом Рідсом у 1977 році, а згодом Джоан Бояр у 1982 році (якій також вдалося скомпрометувати квадратичні та кубічні генератори). Їхні дослідження беззаперечно довели, що конгруентні алгоритми є абсолютно непридатними для сучасної криптографії. Втім, попри ці серйозні недоліки безпеки, LCG залишаються вкрай корисними для некриптографічних завдань, таких як наукові симуляції та статистичне моделювання. Вони потребують мінімум обчислювальних ресурсів і продовжують демонструвати чудові статистичні показники в багатьох емпіричних тестах.

Сучасні апаратні генератори випадкових чисел

QRBG121

Цей пристрій використовує справжню квантову випадковість. Робота QRBG121 повністю ґрунтується на квантово-фізичному процесі випромінювання фотонів у напівпровідниках та їх подальшому виявленні. Оскільки фотони випромінюються та фіксуються абсолютно хаотично і незалежно один від одного, точну інформацію про час цих мікроскопічних подій можна надійно перетворити на високозахищені випадкові біти.

Лавові лампи

Штаб-квартира компанії Cloudflare у Сан-Франциско відома тим, що використовує стіну з класичних «лавових ламп» як потужне джерело ентропії. Традиційна лавова лампа — це скляна посудина, наповнена прозорою олією та напівпрозорим воском (парафіном). Віск за своєю природою щільніший за олію, але коли його обережно нагріває лампа біля основи, він стає легшим, піднімається вгору, охолоджується і знову опускається в безперервному, заворожуючому циклі.

Оскільки гідродинаміка є неймовірно хаотичною, цей безперервний рух рідин практично неможливо передбачити математично. Кілька камер високої роздільної здатності безперервно фотографують цю мінливу стіну лавових ламп. Піксельні дані з цих надзвичайно хаотичних знімків передаються на сервер, який перетворює візуальний шум на надійні криптографічні ключі шифрування.

Інші міжнародні офіси Cloudflare також використовують геніальні фізичні джерела ентропії. У Лондоні камери фіксують глибоко непередбачувані рухи хаотичної системи з трьох маятників. Тим часом офіс у Сінгапурі використовує лічильник Гейгера для вимірювання радіоактивного розпаду невеликої безпечної гранули урану. Уран працює як ідеальне джерело даних, оскільки точна мить, коли будь-який окремий радіоактивний атом вирішує розпастися, є фундаментально випадковим актом квантової механіки.

HotBits

HotBits — це онлайн-сервіс, що надає справжні випадкові числа, згенеровані апаратним лічильником Гейгера, який реєструє фонове іонізуюче випромінювання. Користувачам достатньо заповнити форму запиту на сайті HotBits, вказати бажаний обсяг випадкових байтів і вибрати спосіб їх отримання. Щоб гарантувати максимальну криптографічну безпеку, тієї самої миті, коли запитані числа доставляються користувачеві, вони назавжди стираються з серверів HotBits.

Вакуумні квантові флуктуації

Всупереч своєму латинському кореню (vacuus, що означає «порожній»), фізичний вакуум ніколи не буває абсолютно порожнім. Згідно з принципом невизначеності Гейзенберга з квантової механіки, вакуум — це бурхливий простір, де субатомні «віртуальні частинки» безперервно з'являються та зникають.

Використовуючи це явище, канадські фізики розробили блискавично швидкий і структурно елегантний генератор випадкових чисел, який повністю базується на вакуумних флуктуаціях. Ця система використовує високочастотний імпульсний лазер, щільне середовище заломлення (наприклад, алмаз) та надзвичайно чутливий детектор фотонів. Коли лазерні імпульси проходять крізь алмаз, точні характеристики кожного імпульсу унікально спотворюються через непередбачувані квантові вакуумні флуктуації, що трапляються на шляху світла.

Під час розсіювання випромінювання виникають унікальні спектральні лінії. Оскільки в основі вакуумних флуктуацій лежить чистий квантовий хаос, властивості цих спектральних ліній змінюються абсолютно непередбачувано і не повторюються двічі — що гарантує стовідсоткову випадковість.

Генератор на вуглецевих нанотрубках

Цей передовий метод елегантно поєднує мікроскопічні розміри з непередбачуваністю теплового шуму.

Дослідники успішно створили генератор справжніх випадкових чисел, використовуючи комірку статичної оперативної пам'яті (SRAM). Революційність підходу полягає в тому, що комірка пам'яті надрукована за допомогою спеціалізованого електронного чорнила на основі напівпровідникових вуглецевих нанотрубок. Фізична система збирає флуктуації навколишнього теплового шуму всередині цих нанотрубок, щоб безперервно генерувати справжні випадкові біти.

Оскільки цей ГВЧ на вуглецевих нанотрубках можна друкувати безпосередньо на гнучких пластикових підкладках, він відкриває величезні перспективи для інновацій. Його можна легко інтегрувати в мініатюрну гнучку електроніку, носимі медичні датчики, дешеві одноразові етикетки безпеки і навіть в елементи «розумного» одягу.

Гральні кубики та Фонд електронних рубежів (EFF)

Фонд електронних рубежів (EFF) запропонував напрочуд простий, низькотехнологічний метод генерації високозахищених криптографічних паролів за допомогою фізичного TRNG: звичайних шестигранних гральних кубиків.

Наприклад, ви кидаєте п'ять кубиків одночасно і записуєте результати зліва направо. Якщо на кубиках випадає 6, 3, 1, 3 і 1, ваш кінцевий рядок буде 63131. Далі ви відкриваєте офіційний список слів EFF Diceware на їхньому сайті та шукаєте слово, закріплене за номером 63131. У цьому випадку це слово «turbofan».

Потім ви повторюєте цю процедуру кілька разів (зазвичай п'ять або шість), щоб створити надійну «парольну фразу» з кількох випадкових слів. Кінцевий результат може мати такий вигляд: «turbofan purge unfitting try pruning». Оскільки фраза генерується чистою фізичною ентропією, вона математично захищена від атак методом перебору (brute-force). Крім того, використовуючи прості мнемонічні техніки, такі яскраві та абсурдні фрази напрочуд легко запам'ятовуються.

Квантовий генератор випадкових чисел зі смартфона Nokia

У 2014 році дослідники з Женевського університету продемонстрували неймовірну винахідливість. Вони довели, що звичайний споживчий гаджет може функціонувати як квантовий генератор випадкових чисел (QRNG) — для цього використали вбудовану камеру легендарного смартфона Nokia N9.

Концепція виявилася напрочуд елегантною: сенсор камери смартфона перепрограмували для підрахунку точної кількості частинок світла (фотонів), що потрапляють на кожен окремий піксель, використовуючи стандартний світлодіод як основне джерело освітлення. Всього за одну мікросекунду кожен піксель на 8-мегапіксельній матриці фіксував близько 400 фотонів. Одночасно зчитуючи ці гігантські масиви непередбачуваних квантових світлових даних з мільйонів пікселів, дослідникам вдалося згенерувати щільну, високозахищену послідовність справжніх випадкових чисел.