Як працюють генератори випадкових чисел

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

Ключові висновки

Генератор псевдовипадкових чисел (PRNG) перетворює початкове число на довгу повторювану послідовність.
Криптографічно захищений PRNG (CSPRNG) розроблений таким чином, що минулі результати практично не можуть виявити майбутні.
Справжня випадковість походить від джерел фізичної ентропії, а не лише від алгоритму.
Браузери надають CSPRNG через crypto.getRandomValues(), що є правильним вибором для щоденних чесних розіграшів.
Справедливість також залежить від того, як значення відображаються в діапазоні: упереджена арифметика за модулем може спокійно сприяти деяким результатам.

Чому випадковість складніше, ніж здається

Комп’ютер виконує інструкції. Якщо ви запускаєте ту саму програму двічі з однаковими вхідними даними, ви зазвичай отримуєте той самий результат. Генератор випадкових чисел повинен порушити це очікування, не зламавши машину.

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

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

Що робить генератор псевдовипадкових чисел

PRNG зберігає внутрішній стан. Щоразу, коли ви запитуєте число, він перетворює стан і повертає частину результату. Трансформація зазвичай швидка і детермінована. З огляду на той самий початковий стан, та сама послідовність з’являється знову.

Більшість PRNG зрештою повторюють свій стан. Кількість значень перед повторенням називається періодом. Тривалий період корисний, але він автоматично не робить генератор безпечним. Зловмисник, який може спостерігати достатньо вихідних даних, може реконструювати внутрішній стан і передбачити майбутні значення.

PRNG проти CSPRNG

PRNG загального призначення оптимізовано для швидкості та статистичної якості. CSPRNG розроблений, щоб протистояти передбаченню. Він використовує криптографічні примітиви та побудований таким чином, що вивчення одного виводу не повинно виявити наступного.

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

Використовуйте CSPRNG для паролів, токенів, чесних розіграшів із призом і всього, що може передбачити зловмисник. Для декоративної анімації або грубої симуляції може бути достатньо звичайного PRNG.

Звідки береться справжня випадковість

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

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

Як працюють генератори на цьому сайті

Інструменти на цьому сайті використовують crypto.getRandomValues() у вашому браузері. Результати генеруються локально і не завантажуються.

Для цілих діапазонів браузер повертає 32-розрядне значення без знаку. Наївний підхід використовує залишок після ділення, але це може внести невелике зміщення, коли діапазон не рівномірно ділиться на повний 32-бітний простір. Натомість генератори використовують вибірку відхилення: значення за межами незміщеної області відкидаються та перемальовуються. Результатом є рівномірний розподіл у запитаному діапазоні.

Перемішування використовує алгоритм Фішера–Єйтса з безпечними випадковими індексами. На відміну від випадкового сортування з випадковим компаратором, Фішер–Єйтс створює кожну перестановку з рівною ймовірністю, коли випадкові індекси однакові.

Що є достатньо випадковим для вашого випадку використання?

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

Паролі та коди відновлення.
Розіграші, розіграші та прослуховування зі справжнім призом.
Довільне розподіл людей по командах або групах.
Токени, ідентифікатори сеансу та все, що стосується безпеки.
Будь-яку нічию, яку вам, можливо, доведеться захищати публічно.

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

Проста перевірка справедливості

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

Для публічних розіграшів запишіть дані, налаштування та результат. Запис сприяє довірі більше, ніж будь-яке твердження про випадковість.

Підсумок

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