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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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