Що таке генератор випадкових чисел?
Генератор випадкових чисел (RNG) — це система, яка видає випадкові або псевдовипадкові числа. Чи можна насправді передбачити наступне число, залежить від типу генератора. Деякі генератори спираються на фізичний процес, деякі обчислюють свої числа за допомогою алгоритму, і лише частина таких алгоритмів побудована так, що навіть той, хто бачив їхні результати, не може передбачити, що буде далі. «Виглядати випадковим» і «бути непередбачуваним» — різні поняття, і більша частина цієї статті саме про цю різницю.
Апаратні генератори випадкових чисел
Апаратний генератор випадкових чисел (HRNG), який ще називають генератором істинно випадкових чисел (TRNG), отримує випадкові значення з фізичного процесу. Найдавніші такі генератори можна побачити на власні очі: підкинута монета, кинутий кубик, колесо рулетки. Механіка описує кожен із них повністю, і все ж добре зроблене колесо на практиці залишається непередбачуваним, бо найменші відмінності в тому, як починається кожне обертання, переростають у цілком різні результати.
Натомість сучасні апаратні генератори вимірюють мікроскопічні явища: дробовий шум і тепловий шум в електронних схемах, атмосферний шум, квантові ефекти. Це добрі джерела ентропії — непередбачуваності, яку можна виміряти, — але фізичне джерело за своєю природою не ідеальне: воно може давати зміщені результати, змінюватися з часом і виходити з ладу, тож його якість потрібно оцінювати й контролювати, а отримані дані за потреби додатково обробляти; саме це описують стандарти, такі як NIST SP 800-90B. Апаратні джерела застосовують там, де ця гарантія важлива найбільше — передусім у криптографії, де вони дають непередбачуваний початковий матеріал для ключів, що лежать в основі таких протоколів, як Transport Layer Security (TLS).
Генератори псевдовипадкових чисел
Альтернатива фізичному пристрою — алгоритм. Генератор псевдовипадкових чисел (PRNG) видає послідовність, яка виглядає випадковою, але повністю визначається початковим значенням (seed). Якщо дати те саме початкове значення тому самому алгоритму, щоразу вийде та сама послідовність. Це слабкість там, де результат має бути непередбачуваним, а початкове значення чи внутрішній стан можна вгадати або відновити, і перевага там, де результат має бути відтворюваним, — симуляцію чи тест можна запустити ще раз точно так само. PRNG також швидкі, дешеві й прості в реалізації, тому на них покладається більшість програмного забезпечення. Серед відомих алгоритмів — лінійний конгруентний генератор (LCG), генератори xorshift і вихор Мерсенна.
Вихор Мерсенна
Вихор Мерсенна, опублікований 1997 року Макото Мацумото та Такудзі Нісімурою, — один із найпоширеніших генераторів псевдовипадкових чисел і типовий вибір у багатьох мовах програмування. Свою назву він отримав через період — довжину послідовності до її повторення, — який у стандартному варіанті, MT19937, дорівнює простому числу Мерсенна 219937 − 1. Він проходить більшість статистичних тестів випадковості й добре підходить для симуляцій. Проте його не розробляли, щоб зберігати таємниці: за 624 послідовними 32-бітовими значеннями на виході будь-хто може відновити його внутрішній стан і передбачити кожне наступне значення, тому його не можна використовувати для ключів, паролів чи будь-чого іншого, що має лишатися непередбачуваним.
Криптографічно стійкі генератори та ентропія
Багатьом застосункам потрібні одразу і швидкість алгоритму, і непередбачуваність фізичного джерела. Відповідь — криптографічно стійкий генератор псевдовипадкових чисел (CSPRNG). Це все ще PRNG, але побудований так, що за частиною його результатів практично неможливо передбачити решту; він отримує початкове значення і регулярно оновлює його з джерела справжньої ентропії. Початкове значення з фізичного джерела саме по собі не робить звичайний PRNG стійким: для цього має бути спеціально розроблений сам алгоритм. Фізичне джерело, як-от тепловий шум або інтервали між апаратними подіями, дає невелику кількість істинної випадковості, а CSPRNG перетворює її на довгу послідовність значень і видає їх значно швидше. Саме таку комбінацію операційна система пропонує програмам, що в ній виконуються, і саме це сьогодні на практиці зазвичай мають на увазі під «генератором випадкових чисел». Такий генератор створює ключі шифрування, токени сесій і паролі.
Випадкові числа в браузері
JavaScript дає вебсторінці два вбудовані способи отримати випадкові значення, і вони належать до різних класів. Math.random() — звичайний PRNG: стандарт мови JavaScript залишає вибір алгоритму кожному браузеру й нічого не обіцяє щодо безпеки — годиться для анімації, але не підходить для жеребкування, результат якого хтось може оскаржити. Другий варіант — 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 випасти знову, як і будь-яке інше. Жеребкування без повторів — це інший вид жеребкування, а не більш випадковий. І сам по собі чесний генератор не робить чесною всю процедуру: список учасників і кількість спроб важать не менше — про це розповідає наша стаття про те, як вибрати випадкового переможця конкурсу.