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

Компьютеры генерируют случайные числа для разнообразных задач – шифрования, видеоигр и азартных игр. Случайные числа подразделяются на два типа — истинно случайные числа и псевдослучайные числа, и данное различие важно для надежности шифросистем.

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

Случайные числа используются уже тысячелетиями в виде бросания монетки или костей, чтобы оставить конечный результат на волю случая. Компьютерные генераторы случайных чисел аналогичны — они стремятся получить непредсказуемый, случайный результат. Они имеют огромное значение для шифрования.

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

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

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

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

Более обыденный пример – компьютер мог бы полагаться на атмосферные помехи или использовать точное время нажатия кнопок на клавиатуре в качестве источника непредсказуемых данных или энтропии. Допустим, компьютер мог бы заметить, что кнопки были нажаты ровно через 0.34254674 секунды после 17 часов. Сбор достаточного количества точных моментов времени, соотносимых с нажатиями кнопок, даст источник энтропии для генерации подлинно случайного числа. Действия пользователя непредсказуемым, поэтому злоумышленник не сможет угадать точные моменты нажатия кнопок. Устройство /dev/random в Linux, генерирующее случайные числа — “блоки” – не возвращает результат, пока не накопит достаточно энтропии, чтобы возвратить истинно случайное число.

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

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

Это не всегда плохо. Скажем, в случае видеоигры неважно, обусловлены ли происходящие в ней события истинно случайными числами или же псевдослучайными. В случае шифрования недопустимы псевдослучайные числа, поддающиеся угадыванию.

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

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

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

В декабре 2013 года разработчики FreeBSD убрали поддержку использования RdRand в качестве непосредственного источника случайности в силу недоверия к нему. Вывод устройства RdRand стал подаваться на вход другого алгоритма, добавляющего дополнительную энтропию, чтобы сделать бесполезными бэкдоры в генераторе случайных чисел. Linux тоже стала вносить дополнительную случайность в выходные данные RdRand с той же целью.