Генераторы настоящих случайных чисел в криптографии

Генераторы ПСЧ находят широкое применение в криптографии, например, при потоковом шифровании. Однако иногда бывает необходимо генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (random number generator) или сокращённо ГСЧ (RNG). Генератор настоящих случайных чисел в зависимости от некоторого инициализирующего значения выдает последовательность, которая не может быть впоследствии повторена.

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

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

· количество импульсов счетчика Гейгера за единицу времени, например, за одну секунду;

· числа, оказывающиеся на верхней грани игрального кубика при произвольном броске;

· количество самолетов, пролетающих над определенным районом в единицу времени, например, месяц.

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

Тем не менее, разработчики интегральных схем конструируют и производят аппаратные ГСЧ, основанные на разных принципах. Например, разработан способ с использованием двух конденсаторов типа "металл - диэлектрик - полупроводник". Случайное значение является функцией разности зарядов этих конденсаторов. В другом устройстве обрабатывается и используется значение температурного шума полупроводникового диода.

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

Таблица RAND В 1955 Rand Corporation опубликовала книжку с миллионом случайных цифр.

Использование таймера компьютера Если необходим один случайный бит (или даже несколько), то можно взять наименьший значимый бит таймера. Это может плохо работать под Unix’ом из-за различий синхронизацией, но на PC будет нормально. Нельзя получать таким образом много битов. Например, если каждый вызов процедуры генерации бита занимает четное число тиков таймера, то мы будем получать одни и те же значения, если нечетное – то последовательность 101010… Даже если зависимость не настолько очевидна, результирующая строка будет далека от случайности.

Использование случайного шума Самый лучший способ получить случайное число – это обратиться к естественной случайности реального мира – радиоактивный распад, шумные диоды и т.п. В принципе, элемент случайности есть и в компьютерах:

• время дня;

• загруженность процессора;

• время прибытия сетевых пакетов и т.п.

Проблема не в том, чтобы найти источники случайности, но в том, чтобы сохранить случайность при измерениях. Например, это можно делать так: найдем событие, случающееся регулярно, но случайно (шум превышает некоторый порог). Измерим время между первым событием и вторым, затем между вторым и третьим. Если 1,2 2,3 t > t, то выдадим 1; если 1,2 2,3 t ≤ t, то выдадим 0. Затем повторим процесс.