Генераторы реальных случайных последовательностей

Иногда криптографически безопасные псевдослучайные последовательности недостаточно хороши. В криптографии вам могут понадобиться действительно случайные числа. Первое, что приходит в голову - это генерация ключей. Прекрасно можно генерировать случайные криптографические ключи, используя генератор псевдослучайных последовательностей, но если враг добудет копию этого генератора и главный ключ, он сможет создать те же ключи и взломать вашу криптосистему, независимо от надежности ваших алгоритмов. Последовательность, выдаваемую генератором случайных последовательностей, воспроизвести невозможно. Никто, даже вы сами, не сможет воспроизвести последовательность битов, выдаваемую этими генераторами.
Крупной философской проблемой является вопрос о том, дают ли эти методы действительно случайные биты. Я не собираюсь ввязываться в этот спор. Здесь я рассматриваю выдачу битов, которые невозможно воспроизвести, и у которых статистические свойства как у случайных битов .
Для любого генератора действительно случайных последовательностей важным вопросом является его проверка. На эту тему существует множество литературы. Маурер показал, что все эти тесты можно получить из попытки сжать последовательность. Если случайная последовательность сжимается, то она не является по настоящему случайной.
В любом случае, все, что мы имеем в этой области, во многом относится к черной магии. Главным моментом является генерация последовательности битов, которую не сможет угадать ваш противник . Это гораздо более трудная задача, чем кажется. Я не могу доказать, что любой из описанных методов генерирует случайные биты. Результатом их работы являются последовательности битов, которые невозможно легко воспроизвести.
Таблицы RAND
Давным давно, в 1955 году, когда компьютеры все еще были в новинку, Rand Corporation издала книгу, содержавшую миллион случайных цифр. Их метод описывался так:
Случайные цифры этой книги были получены при помощи рандомизации основной таблицы, сгенерированной электронной рулеткой. Вкратце, источник импульсов, выдающий их со случайной частотой в среднем около 100000 импульсов в секунду, открывался раз в секунду импульсом постоянной частоты. Цепи нормализации импульса пропускали импульсы через 5-разрядный бинарный счетчик. По сути машина являлась колесом рулетки с 32-позициями, которое в среднем делало около 3000 оборотов за выборку и выдавало одно число в секунду. Использовался двоично-десятичный преобразователь, который преобразовывал 20 из 32 чисел (оставшиеся двенадцать отбрасываются) и оставлял только последнюю цифру двузначных чисел. Эти последние цифры попадали в компостер IBM, образуя в конце концов таблицу пробитых карточек случайных цифр.
В книге рассматривались и результаты различных проверок данных на случайность. В ней также предлагался способ, как использовать эту книгу для выбора случайного числа:
Строки таблицы цифр нумеруются от 00000 до 19999. При использовании таблицы нужно сначала выбрать случайную стартовую позицию. Обычной процедурой для этого является следующее: откройте эту книгу на произвольной странице таблицы цифр и, закрыв глаза, выберите пятиразрядное число. Это число после замены первой цифры остатком от деления ее на 2 определяет стартовую строку. Остаток от деления двух цифр справа от первоначально выбранного пятиразрядного числа на 50 задает стартовый столбец в стартовой строке. Чтобы защититься от открытия книги все время на одной странице и естественного стремления выбрать число поближе к центру страницы, каждое использованное для определения стартовой позиции пятиразрядное число должно быть помечено и не должно больше использоваться для этой цели.
Главным содержанием этой книги была "Таблица случайных цифр". Цифры приводились пяти разрядными группами - "10097 32533 76520 13586 ..." - по 50 в строке и по пятьдесят строк на странице. Таблица занимала 400 страниц и, за исключением особенно выдающейся группы на странице 283, выглядевшей как "69696", была достаточно скучным чтивом. В книгу также входила таблица 100000 нормальных отклонений.
Интересным в книге RAND являются не миллионы случайных цифр, а то, что они были созданы до компьютерной революции. Во многих криптографических алгоритмах используются произвольные константы - так называемые "магические числа". Выбор магических чисел из таблиц RAND гарантировал, что они не были выбраны специально по каким-то жульническим причинам. Так, например, было сделано в Khafre.
Использование случайного шума
Лучшим способом получить большое количество случайных битов является извлечение их из естественной случайности реального мира. Часто такой метод требует специальной аппаратуры, но этот трюк можно прим е-нить и в компьютерах.
Найдите событие, которое случается регулярно, но случайно: атмосферный шум, преодолевающий какой-то порог, ребенок, падающий, учась ходить. Измерьте интервал между одним подобным событием и событием, следующим за ним. Запишите. Измерьте временной интервал между вторым и третьим событиями . Снова запишите. Если первый временной интервал больше второго, выходным битом будет 1 . Если второй интервал больше первого, то выходом события будет 0. Сделайте это снова для следующего события.
Бросьте стрелу дартс в перечень котировок Нью-Йоркской фондовой бирже в местной газете . Сравните котировку акции, в которую вы попали, с котировкой акции прямо над ней . Если больше та, в которую вы попали, выход равен 0, а если меньше - 1.
Подключите к компьютеру счетчик Гейгера, подсчитайте количество импульсов за фиксированный интервал времени и возьмите младший бит. Или измерьте время между последовательными тиками ticks. (Так как радиоактивный источник распадается, среднее время между последовательными тиками непрерывно увеличивается . Чтобы этого избежать, надо выбирать источник с достаточно длинным периодом полураспада - такой как плутоний. Если вы беспокоитесь о своем здоровье, можете внести соответствующие статистические поправки.)
Дж. Б. Эгнью (G. В. Agnew) предложил генератор реально случайных битов, который можно интегрировать в СБИС [21]. Это конденсатор металл-изолятор-полупроводник (metal insulator semiconduction capacitor, MISC). Два таких конденсатора помещаются рядом друг с другом, а случайный бит является функцией разности зарядов этих конденсаторов. Другой генератор случайных чисел генерирует поток случайных битов, используя нестабильность частоты свободно колеблющегося осциллятора. Коммерческая микросхема от AT&T генерирует случайные числа, опираясь именно на это явление . М. Гьюд (М. Gude) построил генератор случайных чисел, собирающий случайные биты из физических явлений, например, радиоактивного распада. Манфилд Рихтер (Manfield Richter) разработал генератор случайных чисел на базе температурного шума полупроводникового диода.
Предположительно случайны временные интервалы между последовательными 2е4 излучениями света распадающегося атома ртути. Используйте. А лучше найдите полупроводниковую фирму, которая изготавливает микросхемы генераторов случайных чисел, их достаточно много .
Существует также генератор случайных чисел, использующий диск компьютера. Он измеряет время, нужное для чтения блока диска, и использует изменения этого времени в качестве источника случайных чисел. Данные фильтруются, чтобы удалить структуру, вызванную квантованием, затем к векторам чисел применяется быстрое преобразование Фурье. Это устраняет смещение и корреляцию. Наконец, в качестве случайных битов используются спектральные углы для частот в диапазоне (0, л), нормализованные на единичный интервал.
Большая часть изменений скорости вращения диска вызвана турбулентностью воздуха, которая и является источником случайности в системе. Хотя надо учесть следующее. Если вы выдаете на выход слишком много битов, то вы используете в качестве генератора случайных чисел быстрое преобразование Фурье и рискуете получить определенную предсказуемость. И лучше снова и снова читать один и тот же дисковый блок, чтобы вам не пришлось фильтровать структуру, источником которой является планировщик диска. Реализация такой системы позволяла получать около 100 битов в минуту.
Использование таймера компьютера
Если вам нужен один случайный бит (или даже несколько), воспользуйтесь младшим значащим битом любого регистра таймера. В системе UNIX он может быть не слишком случайным из-за различной возможной синхронизации, но на некоторых персональных компьютерах это работает .
Не стоит извлекать таким образом слишком много битов . Выполнение много раз одной и той же процедуры последовательно может легко сместить биты, генерированные этим способом . Например, если выполнение каждой процедуры генерации бита занимает четное число тиков таймера, на выходе вашего генератора будет бесконечная последовательность одинаковых битов. Если выполнение каждой процедуры генерации бита занимает нечетное число тиков таймера, на выходе вашего генератора будет бесконечная последовательность чередующихся битов. Даже если зависимость не так очевидна, получающийся битовый поток будет далек от случайного. Один генератор случайных чисел работает следующим образом:
Наш генератор действительно случайных чисел работает, устанавливая будильник и затем быстро инкрементируя регистр счетчика процессора до тех пор, пока не произойдет прерывание. Далее выполняется XOR содержимого регистра и содержимого байта выходного буфера (данные регистра усекаются до 8 битов). После того, как будет заполнен каждый байт выходного буфера, буфер подвергается дальнейшей обработке циклическим сдвигом каждого символа вправо на два бита . Это приводит к эффекту перемещения наиболее активных (и случайных) младших значащих битов в старшие значащие позиции. Затем весь процесс повторяется три раза. Наконец после прерываний два самых случайных бита регистра счетчика повлияют на каждый символ буфера. То есть происходит 4n прерываний, где n - число нужных случайных битов.
Этот метод очень чувствителен к случайности системных прерываний и квантованности таймера. При тестировании на реальных UNIX-машинах результат был очень неплох.
Измерение скрытого состояния клавиатуры
Процесс печатания и случаен, и неслучаен. Он достаточно неслучаен, чтобы его можно было использовать для идентификации печатающего человека, но он достаточно случаен, чтобы его можно было использовать для генерации случайных битов. Измерьте время между последовательными нажатиями клавиш, затем воспользуйтесь младшими значащими битами этих измерений. Эти биты оказываются достаточно случайными. Этот метод не работает на UNIX-терминалах, так как нажатия клавиш прежде, чем они будут переданы вашей программе, проходят через фильтры и другие механизмы, но это будет работать на большинстве персональных компьютеров.
В идеале вы должны по каждому нажатию клавиши генерировать только один бит . Использование большего количества битов может сместить результаты в зависимости от навыков машинистки . Однако этот метод имеет ряд ограничений. Хотя нетрудно посадить за клавиатуру человека, печатающего со скоростью 100 слов в минуту или около того, если есть время для генерации ключа, глупо просить машинистку печатать текст из 100000 слов, чтобы использовать результат работы генератора в качестве одноразового блокнота.
Извлеченная случайность
В общем случае лучший способ генерировать случайные числа - найти большое количество кажущихся ел у-чайными событий и извлечь случайность из них. Эта случайность может храниться в накопителе и извлекаться при необходимости. .Однонаправленные хэш-функции прекрасно подходят для этого. Они быстры, поэтому вы можете пропускать биты через них, не слишком заботясь о производительности или действительной случайн о-сти каждого наблюдения. Попробуйте хэшировать почти все, что вам кажется хоть чуть-чуть случайным. Н а-пример:
—	Копия каждого нажатия на клавиши
—	Команды мыши
—	Номер сектора, время дня и задержка поиска для каждой дисковой операции
—	Действительное положение мыши
—	Номер текущей строки развертки монитора
—	Содержание действительно выводимого на экран изображения
—	Содержание FAT-таблиц, таблиц ядра, и т.д.
—	Времена доступа/изменения /dev/tty
—	Загрузка процессора
—	Времена поступления сетевых пакетов
—	Выход микрофона
—	/dev/audio без присоединенного микрофона
Если ваша система использует различные кристаллы-осцилляторы для своего процессора и часов , попытайтесь считывать время дня в плотном цикле. В некоторых (но не всех) системах это приведет к случайным колебаниям фазы между двумя осцилляторами.
Так как случайность в этих событиях определяется синхронизацией осцилляторов, используйте часы с как можно меньшим квантом времени. В стандартном PC используется микросхема таймера Intel 8254 (или эквивалентная), работающая на тактовой частоте 1.1931818 МГц, поэтому непосредственное считывание регистра счетчика даст разрешение в 838 наносекунд. Чтобы избежать смещения результатов, не используйте в качестве источника событий прерывание таймера. Вот как выглядит этот процесс на языке С с MD5 (см. раздел 18.5) в качестве хэш-функции:

После достаточных вызовов churnrand() накопления достаточной случайности в Randpool, можно генерировать из этого случайные биты. MD5 снова становится полезной, в этот раз в качестве генератора псевдослучайного байтового потока, работающего в режиме счетчика.

По многим причинам хэш-функция имеет ключевое значение. Во первых она обеспечивает простой способ генерировать произвольное количество псевдослучайных данных, не вызывая всякий раз churnrand(). На деле, когда запас в накопителе подходит к концу, система постепенно переходит от совершенной случайности к практической. В этом случае становится теоретически возможным использовать результат вызова genrand() для определения предыдущего или последующего результата. Но для этого потребуется инвертировать MD5, что вычислительно невозможно.
Это важно, так как процедуре неизвестно, что делается потом со случайными данными, которые она возвращает. Один вызов процедуры может генерировать случайное число для протокола, которое посылается в явном виде, возможно в ответ на прямой запрос взломщика. А следующий вызов может генерировать секретный ключ для совсем другого сеанса связи, в суть которого и хочет проникнуть взломщик . Очевидна важность того, чтобы взломщик не смог получить секретный ключ, используя подобную схему действий .
Но остается одна проблема. Прежде, чем в первый раз будет вызвана genrand() в массиве Randpool[] должно быть накоплено достаточно случайных данных. Если система какое-то время работала с локальным пользователем, что-то печатающим на клавиатуре, то проблем нет. Но как насчет независимой системы, которая перегружается автоматически, не обращая внимания ни на какие данные клавиатуры или мыши ?
Но есть одна трудность. В качестве частичного решения можно потребовать, чтобы после самой первой з а-грузки оператор какое-то время поработал на клавиатуре и создал на диске стартовый файл перед выгрузкой операционной системы, чтобы в ходе перезагрузок использовались случайные данные, переданные в Randseed[]. Но не сохраняйте непосредственно сам Randseed[]. Взломщик, которому удастся заполучить этот файл, сможет определить все результаты genrandQ после последнего обращения к churnrand() прежде, чем этот файл будет создан.
Решением этой проблемы является хэширование массива Randseed[] перед его сохранением, может даже вызовом genrandO. При перезагрузке системы вы считываете данные из стартового файла, передаете их churnrand(), а затем немедленно стираете их. К сожалению это не устраняет угрозы того, что злоумышленник добудет файл между перезагрузками и использует его для предсказания будущих значений функции genrand(). Я не вижу иного решения этой проблемы кроме, как подождать накопления достаточного количества случайных событий, случившихся после перезагрузки, прежде, чем позволить genrand() выдавать результаты.