Случайные цифры этой книги были получены при помощи рандомизации основной таблицы, сгенерированной эле к-тронной рулеткой. Вкратце, источник импульсов, выдающий их со случайной частотой в среднем около 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. B. Agnew) предложил генератор реально случайных битов, который можно интегрировать в СБИС [21]. Это конденсатор металл-изолятор-полупроводник (metal insulator semiconduction capacitor, MISC). Два таких конденсатора помещаются рядом друг с другом, а случайный бит является функцией разности зар ядов этих конденсаторов. Другой генератор случайных чисел генерирует поток случайных битов, используя н е-стабильность частоты свободно колеблющегося осциллятора [535]. Коммерческая микросхема от AT&T генерирует случайные числа, опираясь именно на это явление [67]. М. Гьюд (M. Gude) построил генератор случайных чисел, собирающий случайные биты из физических явлений, например, радиоактивного распада [668, 669]. Манфилд Рихтер (Manfield Richter) разработал генератор случайных чисел на базе температурного шума полупроводникового диода [1309].

Предположительно случайны временные интервалы между последовательными 2e4 излучениями света распадающегося атома ртути. Используйте. А лучше найдите полупроводниковую фирму, которая изготавливает микросхемы генераторов случайных чисел, их достаточно много .

Существует также генератор случайных чисел, использующий диск компьютера [439]. Он измеряет время, нужное для чтения блока диска, и использует изменения этого времени в качестве источника случайных чисел . Данные фильтруются, чтобы удалить структуру, вызванную квантованием, затем к векторам чисел применяется быстрое преобразование Фурье. Это устраняет смещение и корреляцию. Наконец, в качестве случайных битов используются спектральные углы для частот в диапазоне (0, п), нормализованные на единичный интервал.

Большая часть изменений скорости вращения диска вызвана турбулентностью воздуха, которая и является и с-точником случайности в системе . Хотя надо учесть следующее. Если вы выдаете на выход слишком много б и-тов, то вы используете в качестве генератора случайных чисел быстрое преобразование Фурье и рискуете пол учить определенную предсказуемость. И лучше снова и снова читать один и тот же дисковый блок, чтобы вам не пришлось фильтровать структуру, источником которой является планировщик диска . Реализация такой системы позволяла получать около 100 битов в минуту [439].

Использование таймера компьютера

Если вам нужен один случайный бит (или даже несколько), воспользуйтесь младшим значащим битом любого регистра таймера. В системе UNIX он может быть не слишком случайным из-за различной возможной синхронизации, но на некоторых персональных компьютерах это работает .

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

Наш генератор действительно случайных чисел . . . работает, устанавливая будильник и затем быстро инкрементируя р е-гистр счетчика процессора до тех пор, пока не произойдет прерывание . Далее выполняется XOR содержимого регистра и содержимого байта выходного буфера (данные регистра усекаются до 8 битов). После того, как будет заполнен каждый байт выходного буфера, буфер подвергается дальнейшей обработке циклическим сдвигом каждого символа вправо на два бита . Это приводит к эффекту перемещения наиболее активных (и случайных) младших значащих битов в старшие значащие п о-зиции. Затем весь процесс повторяется три раза. Наконец после прерываний два самых случайных бита регистра счетчика п о-влияют на каждый символ буфера. То есть происходит 4n прерываний, где n - число нужных случайных битов.

Этот метод очень чувствителен к случайности системных прерываний и квантованности таймера . При тестировании на реальных UNIX-машинах результат был очень неплох.

Измерение скрытого состояния клавиатуры

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

В идеале вы должны по каждому нажатию клавиши генерировать только один бит . Использование большего количества битов может сместить результаты в зависимости от навыков машинистки . Однако этот метод имеет ряд ограничений. Хотя нетрудно посадить за клавиатуру человека, печатающего со скоростью 100 слов в минуту или около того, если есть время для генерации ключа, глупо просить машинистку печатать текст из 100000 слов, чтобы использовать результат работы генератора в качестве одноразового блокнота .

Смещения и корреляции

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

Способом устранить смещение, или отклонение, является XOR нескольких битов друг с другом. Если случайный бит смещен к 0 на величину e, то вероятность 0 можно записать как:

P(0) = 0.5 + e

XOR двух из таких битов дает: P(0) = (0.5 + e)2 + (0.5 - e)2 = 0.5 + 2e2 Те же вычисления для XOR 4 битов дают: P(0) = 0.5 + 8e4

XOR m битов экспоненциально сходится к равной вероятности 0 и 1 . Если известно максимальное смещение, которое допустимо в вашем приложении , вы можете вычислить, сколько битов вам нужно объединить с пом о-щью XOR, чтобы уменьшить смещение до этого значения.

Еще лучше рассматривать биты попарно . Если 2 бита одинаковы отбросьте их и взгляните на следующую пару. Если 2 бита различны, используйте первый бит в качестве выхода генератора . Это полностью устраняет смещение. Другие методы уменьшения смещения используют распределение переходов сжатие и быстрое пр е-образование Фурье [511].

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

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

Одно то, что генератор случайных чисел смещен не обязательно означает его бесполезность . Это только означает, что он менее безопасен. Например, рассмотрим проблему Алисы, генерирующей 168-битовый ключ для тройного DES. A все, что у нее есть, - это генератор случайных битов со смещением к 0 : с вероятностью 55 процентов он выдает нули и с вероятностью 45 процентов - единицы . Это означает, что энтропия на бит ключа с оставит только 0.99277 (для идеального генератора она равна 1). Мэллори, пытаясь раскрыть ключ, может оптимизировать выполняемое вскрытие грубой силой, проверяя сначала наиболее вероятные ключи (000 . . . 0) и двигаясь к наименее вероятному ключу (111 . . . 1). Из-за смещения Мэллори может ожидать, что ему удастся обнаружить ключ за 2109 попыток. При отсутствии смещения Мэллори потребуется 2111 попыток. Полученный ключ менее безопасен, но это практически неощутимо .

Извлеченная случайность

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

- Копия каждого нажатия на клавиши

- Команды мыши

- Номер сектора, время дня и задержка поиска для каждой дисковой операции

- Действительное положение мыши

- Номер текущей строки развертки монитора

- Содержание действительно выводимого на экран изображения

- Содержание FAT-таблиц, таблиц ядра, и т.д.

- Времена доступа/изменения /dev/tty

- Загрузка процессора

- Времена поступления сетевых пакетов

- Выход микрофона

- /dev/audio без присоединенного микрофона

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

Так как случайность в этих событиях определяется синхронизацией осцилляторов, используйте часы с как можно меньшим квантом времени. В стандартном PC используется микросхема таймера Intel 8254 (или эквивалентная), работающая на тактовой частоте 1.1931818 МГц, поэтому непосредственное считывание регистра счетчика даст разрешение в 838 наносекунд. Чтобы избежать смещения результатов, не используйте в качестве источника событий прерывание таймера . Вот как выглядит этот процесс на языке C с MD5 (см. раздел 18.5) в качестве хэш-функции:

char Randpool[16];

/* Часто вызывается для широкого множества случайных или полуслучайных системных событий для to churn the randomness pool . Точный формат и длина randevent не имеет значения, пока его содержание