Как компьютеры генерируют случайные числа

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

Компьютеры могут генерировать действительно случайные числа, наблюдая за некоторыми внешними данными, такими как движения мыши или шум вентилятора, которые непредсказуемы, и создавая на их основе данные. Это известно как энтропия. В других случаях они генерируют «псевдослучайные» числа с помощью алгоритма, поэтому результаты выглядят случайными, даже если это не так.

Эта тема становится все более спорной в последнее время, с большим количеством людей сомнения, является ли заслуживающим доверием встроенного аппаратного чип Intel, генератора случайных чисел. Чтобы понять, почему это может не вызывать доверия, вам нужно понять, как в первую очередь генерируются случайные числа и для чего они используются.

Для чего используются случайные числа

Случайные числа использовались на протяжении многих тысяч лет. Будь то подбрасывание монеты или бросание кубиков, цель состоит в том, чтобы оставить конечный результат на усмотрение случайности. Генераторы случайных чисел в компьютере похожи - они попытка добиться непредсказуемого, случайного результата.

СВЯЗАННЫЕ: Что такое шифрование и как оно работает?

Генераторы случайных чисел полезны для множества различных целей. Помимо очевидных приложений, таких как генерация случайных чисел для азартных игр или создание непредсказуемых результатов в компьютерной игре, случайность важна для криптографии.

Криптография требует чисел, которые злоумышленники не могут угадать. Мы не можем использовать одни и те же числа снова и снова. Мы хотим генерировать эти числа очень непредсказуемым образом, чтобы злоумышленники не могли их угадать. Эти случайные числа необходимы для безопасного шифрования, независимо от того, шифруете ли вы свои файлы или просто используете веб-сайт HTTPS в Интернете.

Истинные случайные числа

Вам может быть интересно, как компьютер на самом деле может генерировать случайное число. Откуда эта «случайность»? Если это всего лишь фрагмент компьютерного кода, разве не возможно, чтобы числа, генерируемые компьютером, были предсказуемыми?

Обычно мы группируем случайные числа, генерируемые компьютерами, на два типа, в зависимости от того, как они генерируются: «истинные» случайные числа и псевдослучайные числа.

Чтобы сгенерировать «истинное» случайное число, компьютер измеряет некоторый тип физического явления, происходящего вне компьютера. Например, компьютер может измерить радиоактивный распад атома. Согласно квантовой теории, невозможно точно узнать, когда произойдет радиоактивный распад, так что это, по сути, «чистая случайность» Вселенной. Злоумышленник не сможет предсказать, когда произойдет радиоактивный распад, поэтому он не узнает случайное значение.

В качестве более повседневного примера компьютер может полагаться на атмосферный шум или просто использовать точное время нажатия клавиш на клавиатуре в качестве источника непредсказуемых данных или энтропии. Например, ваш компьютер может заметить, что вы нажали клавишу ровно через 0,23423523 секунды после 14:00. Возьмите достаточно времени, связанного с этими нажатиями клавиш, и у вас будет источник энтропии, который можно использовать для генерации «истинного» случайного числа. Вы непредсказуемая машина, поэтому злоумышленник не может угадать точный момент нажатия этих клавиш. Устройство / dev / random в Linux, которое генерирует случайные числа, «блокирует» и не возвращает результат до тех пор, пока не соберет достаточно энтропии для возврата действительно случайного числа.

Псевдослучайные числа

Псевдослучайные числа - альтернатива «истинным» случайным числам. Компьютер может использовать начальное значение и алгоритм для генерации чисел, которые кажутся случайными, но на самом деле предсказуемыми. Компьютер не собирает случайных данных из окружающей среды.

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

Например, предположим, что злоумышленник знает алгоритм и начальное значение, которое использует генератор псевдослучайных чисел. Допустим, алгоритм шифрования получает от этого алгоритма псевдослучайное число и использует его для генерации ключа шифрования без добавления какой-либо дополнительной случайности. Если злоумышленник знает достаточно, он может работать в обратном направлении и определить псевдослучайное число, которое алгоритм шифрования должен был выбрать в этом случае, взломав шифрование.

Аппаратный генератор случайных чисел АНБ и Intel

Чтобы упростить жизнь разработчикам и помочь генерировать безопасные случайные числа, чипы Intel включают аппаратный генератор случайных чисел, известный как RdRand. Этот чип использует источник энтропии на процессоре и предоставляет программному обеспечению случайные числа по запросу.

Проблема здесь в том, что генератор случайных чисел - это, по сути, черный ящик, и мы не знаем, что внутри него происходит. Если бы RdRand содержал бэкдор АНБ, правительство могло бы взломать ключи шифрования, которые были сгенерированы только с данными, предоставленными этим генератором случайных чисел.

Это серьезная проблема. В декабре 2013 года разработчики FreeBSD удалили поддержку прямого использования RdRand в качестве источника случайности, заявив, что не могут ему доверять. [Источник] Выходные данные устройства RdRand будут переданы в другой алгоритм, который добавляет дополнительную энтропию, гарантируя, что любые бэкдоры в генераторе случайных чисел не будут иметь значения. Linux уже работал таким образом, дополнительно рандомизируя случайные данные, поступающие из RdRand, чтобы их нельзя было предсказать даже при наличии бэкдора. [Источник] В недавней AMA («Спросите меня о чем угодно») на Reddit генеральный директор Intel Брайан Кржанич не ответил на вопросы об этих проблемах. [Источник]

Конечно, это скорее всего проблема не только с чипами Intel. Разработчики FreeBSD также назвали чипы Via по имени. Это противоречие показывает, почему так важно генерировать действительно случайные и непредсказуемые числа.

Чтобы генерировать «истинные» случайные числа, генераторы случайных чисел собирают «энтропию» или кажущиеся случайными данные из физического мира вокруг них. Для случайных чисел, которые на самом деле не обязательно должны быть случайными, они могут просто использовать алгоритм и начальное значение.

Кредит изображения: rekre89 на Flickr, Лиза Брюстер на Flickr, Райан Сомма на Flickr, huangjiahui на Flickr