Як комп'ютери генерують випадкові числа

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

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

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

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

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

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

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

Справжні випадкові числа

Можливо, вам цікаво, як комп'ютер може реально генерувати випадкове число. Звідки походить ця «випадковість». Якщо це просто шматок комп'ютерного коду, чи неможливо цифри, які генерує комп'ютер, можуть бути передбачуваними?

Взагалі групуємо комп'ютери з випадковими числами, що генеруються, у два типи, залежно від того, як вони генеруються: “Правда” випадкові числа та псевдовипадкові числа.

Щоб створити “справжнє” випадкове число, комп'ютер вимірює деякий тип фізичного явища, що відбувається поза комп'ютером. Наприклад, комп'ютер міг виміряти радіоактивний розпад атома. Згідно з квантовою теорією, немає ніякого способу знати напевно, коли відбудеться радіоактивний розпад, так що це, по суті, “чиста випадковість” від Всесвіту. Зловмисник не зможе передбачити, коли відбудеться радіоактивний розпад, щоб вони не знали випадкового значення.

Для більш повсякденного прикладу комп'ютер може покладатися на атмосферний шум або просто використовувати точний час натискання клавіш на клавіатурі як джерело непередбачуваних даних або ентропії. Наприклад, ваш комп'ютер може помітити, що ви натиснули клавішу рівно через 0,23423523 секунди після 14:00. Візьміть достатньо часу, пов'язаного з цими натисканнями клавіш, і у вас буде джерело ентропії, яке можна використовувати для генерування "істинної" випадкової. номер. Ви не передбачувана машина, тому зловмисник не може вгадати точний момент, коли ви натискаєте ці клавіші. Пристрій / dev / random на Linux, який генерує випадкові числа, "блоки" і не повертає результат, поки не збирає достатню кількість ентропії, щоб повернути справді випадкове число.

Псевдовипадкові цифри

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

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

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

NSA та Intel's Hardware Random Number Generator

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

Проблема в тому, що генератор випадкових чисел по суті є чорним ящиком, і ми не знаємо, що відбувається всередині нього. Якщо RdRand містив бекдор NSA, уряд міг би зламати ключі шифрування, які були згенеровані тільки з даними, отриманими від генератора випадкових чисел.

Це є серйозною проблемою. У грудні 2013 року розробники FreeBSD видалили підтримку для використання RdRand безпосередньо як джерело випадковості, сказавши, що їм не можна довіряти. [Джерело] Вихід пристрою RdRand буде подаватися в інший алгоритм, який додає додаткову ентропію, гарантуючи, що будь-які бекдори в генераторі випадкових чисел не мають значення. Linux вже працював таким чином, продовжуючи рандомізувати випадкові дані, що надходять з RdRand, так що це не було б передбачуваним, навіть якщо б був бекдор. [Джерело] У недавньому AMA ("Ask Me Anything") на Reddit, генеральний директор Intel Брайан Крзаніч не відповів на запитання щодо цих проблем. [Джерело]

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

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

Кредит на зображення: rekre89 на Flickr, Lisa Brewster на Flickr, Райан Сомма на Flickr, huangjiahui на Flickr