Генератор випадкових чисел - це набагато складніше, ніж здається.
Як думаєте, що спільного в комп'ютерних гонках, азартних іграх і криптографії? На перший погляд здається, що нічого. Але насправді всі вони залежать від випадкових чисел. Від прослуховування музики до шифрування всього Інтернету - випадкові числа є важливою частиною життя сучасної людини. І найчастіше ми покладаємося на комп'ютери, які генерують їх для нас.
Це змушує задуматися: а як саме комп'ютери генерують випадкові числа?
Якщо ви займалися програмуванням, то напевно використовували у своєму коді генератор випадкових чисел. Для цього в Ruby достатньо викликати «rand», а в Python - «random ()». Створення низки випадкових чисел може здатися простим. Зрештою числа на комп'ютері - це набір одиниць і нулів. Машині просто потрібно випадковим чином вибрати 1 або 0 і повторити це стільки разів, скільки потрібно. Навіть ми, люди, можемо зробити це легко і просто на аркуші паперу.
Однак якщо копнути глибше, то ми створили комп'ютери, щоб стати тими, ким не є - повністю логічними пристроями. Виходить, випадковість суперечить їхній природі. Ну хто захоче, щоб сервер спонтанно вирішив не слідувати логіці програми?
По своїй суті комп'ютери - це прості машини, які приймають дані і виводять їх назад. І щоб ці машини могли генерувати випадкові числа, їм потрібне зовнішнє джерело випадковості. Це джерело буде залежати від того, який генератор випадкових чисел ви захочете використовувати. Таких генераторів два - звичайно, якщо говорити про основні.
Перший і найпоширеніший тип називається «генератор псевдопромінювальних чисел (ДПРЧ)». Як випливає з назви, він не створює «істинних» випадкових чисел. Щоб створити число, знадобиться єдине початкове значення, звідки піде псевдопромінювання. Алгоритми генерації, які використовуються для ДПРЧ, включають в себе «метод вилучення квадратів», «лінійний конгруентний метод», «регістр зрушення з лінійним зворотним зв'язком» і «вихор Мерсенна».
ДПРЧ автоматично створює довгі серії чисел з хорошими випадковими властивостями і робить це швидко і дешево - в цьому його переваги. Але є й очевидний мінус: з обмеженими ресурсами будь-який ДПРЧ рано чи пізно зациклюється і починає повторювати одну і ту ж послідовність чисел. Однак найчастіше цей шаблон не сприймається людьми, що робить ДПРЧ підходящим для використання у відеоіграх і програмуванні.
Не можна не сказати про те, що слабким місцем ДПРЧ все-таки користуються: наприклад, любителі гонок, які маніпулюють ДСЧ і змушують гру працювати передбачувано, щоб пройти її якомога швидше. Є випадки, коли передбачення випадкових чисел має більш серйозні наслідки. Знаючи початкове значення, зловмисник може вгадати згенерований пароль і отримати доступ до особистих даних користувача.
Другий тип генератора - генератор «істинно» випадкових чисел (ГІСЧ або TRNG). Як зовнішнє джерело випадковості він використовує ентропію. Не заглиблюючись у теорію хаосу і термодинаміку, зазначимо, що ентропія - це чистий нефільтрований хаос. І найкраще джерело цього хаосу - сам комп'ютер. Комп'ютер не може працювати випадково, чого не скажеш про його складові.
Комп'ютер - це складна система з безліччю рухомих частин і непостійством, де регулярно виникають тепловий шум, фотоефект та інші квантові явища. Зрештою інженери апаратного забезпечення з'ясували, що, використовуючи складну схему апаратних мікросхем і компонентів, комп'ютери можуть перетворювати фізичний шум на цифрові одиниці і нулі.
Найчастіше ДІСЧ використовують у цифрових азартних іграх: кидання кісток, тасування карт, рулетка - все це зав'язано на невизначеності. А ще в суспільних питаннях, військових закликах і виборі присяжних, де випадковість виступає як метод справедливості.
Однак насправді спектр використання ДІСЧ теж обмежений, адже у нього є свої недоліки. По-перше, для генерації чисел потрібно багато часу. А ще ДІСЧ не завжди надійні. Комп'ютерам потрібна достатня кількість ентропії для створення справжніх випадкових чисел, але випадковість полягає в тому, що вона виникає... випадково! Неактивний або новий сервер не зможе створювати номери такої ж високої якості, як активний.
Оскільки і ДПРЧ, і ДІСЧ мають свої недоліки, їх можна без проблем використовувати в гейм-сфері та азартних іграх, але не можна - в криптографії, яка вимагає високої безпеки. З цієї причини з'явився гібридний тип - «криптографічно стійкий генератор псевдопромінювальних чисел (КСГПЧ або CSPRNG)», який володіє швидкістю ДПРЧ і безпекою ГІСЧ.
КСГПЛ - це генератор, що використовує високоякісне джерело ентропії для створення початкового числа. Потім воно вводиться в алгоритм, який виробляє випадкові і безпечні числа. Простіше кажучи, він використовує ГІСЧ для створення початкового числа для ДПРЧ. Якщо все зроблено правильно, КСГПЛ гарантує, що початкове число дійсно випадкове, а отриманий результат не можна зламати або реконструювати. Зазвичай його використовують в операційних системах на зразок Unix і Linux.
Тим не менш, навіть незважаючи на переваги КСГПЛ, як і всього іншого в технологічній індустрії, абсолютна безпека недосяжна.
Тепер, коли наступного разу ви будете грати у відеогру, слухати музику в випадковому порядку або просто генерувати випадкове число у своєму коді, ви усвідомлюєте всю магію, яка твориться «під капотом».
