Випадковості не випадкові, або як комп’ютери генерують випадкові числа

12

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

Як думаєте, що спільного в комп’ютерних гонках, азартних іграх і криптографії? на перший погляд здається, що нічого. Але насправді всі вони залежать від випадкових чисел. Від прослуховування музики до шифрування всього інтернету-випадкові числа є важливою частиною життя сучасної людини. І найчастіше ми покладаємося на комп’ютери, які генерують їх для нас.

Це змушує задуматися: а як саме комп’ютери генерують випадкові числа?

Якщо ви займалися програмуванням, то напевно використовували в своєму коді генератор випадкових чисел. Для цього в ruby досить викликати ” rand«, а в python — »random ()”. Створення ряду випадкових чисел може здатися простим. Зрештою числа на комп’ютері-це набір одиниць і нулів. Машині просто потрібно випадковим чином вибрати 1 або 0 і повторити це стільки разів, скільки потрібно. Навіть ми, люди, можемо зробити це легко і просто на аркуші паперу.

Однак якщо копнути глибше, то ми створили комп’ютери, щоб стати тими — ким не є-повністю логічними пристроями. Виходить, випадковість суперечить їх природі. Ну хто захоче, щоб сервер спонтанно вирішив не слідувати логіці програми?

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

Unsplash

Перший і найпоширеніший тип називається «генератор псевдовипадкових чисел (гпрч)». Як випливає з назви, він не створює» справжніх ” випадкових чисел. Щоб згенерувати за допомогою нього число, знадобиться єдине початкове значення, звідки піде псевдовипадковість. Алгоритми генерації, що використовуються для гпсч, включають в себе «метод вилучення квадратів«,» лінійний конгруентний метод«,» регістр зсуву з лінійним зворотним зв’язком «і»вихор мерсенна”.

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

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

Другий тип генератора-генератор» істинно ” випадкових чисел (гісч або trng). В якості зовнішнього джерела випадковості він використовує ентропію. Не заглиблюючись в теорію хаосу і термодинаміку, відзначимо, що ентропія — це чистий нефільтрований хаос. І найкраще джерело цього хаосу – сам комп’ютер. Комп’ютер не може працювати випадковим чином, чого не скажеш про його складових.

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

Магнус енгеunsplash

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

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

Оскільки і гпрч, і гісч мають свої недоліки, їх можна без проблем використовувати в гейм-сфері та азартних іграх, але не можна — в криптографії, яка вимагає високої безпеки. З цієї причини з’явився гібридний тип « ” криптографічно стійкий генератор псевдовипадкових чисел (ксгпч або csprng)», який володіє швидкістю гпрч і безпекою гісч.

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

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

Тепер, коли наступного разу ви будете грати у відеогру, слухати музику у випадковому порядку або просто генерувати випадкове число у своєму коді, ви усвідомлюєте всю магію, яка твориться «під капотом».