Действительно удачная идея [1489], запатентованная NSA, показана на 6-й. Записывайте выход вашего любимого генератора в простой m-битовый сдвиговый регистр. По каждому тактовому импульсу сдвигайте регистр на один бит вправо. Затем для каждого выходного потока выполните AND регистра с другим m-битовым вектором, рассматриваемым как уникальный идентификатор для выбранного выходного потока, затем объедините с помощью XOR все биты, получая выходной бит для этого потока . Если требуется получить параллельно н е-сколько выходных потоков, для каждого выходного потока нужно использовать отдельный вектор и логический массив X0R/AND.

Генератор

Вектор 1

Поток 1

Поток 2

Поток n

Рис. 17-11. Генератор нескольких битов.

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

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

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

Крупной философской проблемой является вопрос о том, дают ли эти методы действительно случайные биты. Я не собираюсь ввязываться в этот спор. Здесь я рассматриваю выдачу битов, которые невозможно во с-произвести, и у которых статистические свойства как у случайных битов .

Для любого генератора действительно случайных последовательностей важным вопросом является его пр о-верка. На эту тему существует множество литературы . Тесты на случайность можно найти в [863, 99]. Маурер показал, что все эти тесты можно получить из попытки сжать последовательность [1031, 1032]. Если случайная последовательность сжимается, то она не является по настоящему случайной .

В любом случае, все, что мы имеем в этой области, во многом относится к черной магии . Главным моментом является генерация последовательности битов, которую не сможет угадать ваш противник . Это гораздо более трудная задача, чем кажется. Я не могу доказать, что любой из описанных методов генерирует случайные биты. Результатом их работы являются последовательности битов, которые невозможно легко воспроизвести . Подробности можно найти в [1375, 1376, 511].

Таблицы RAND

Давным давно, в 1955 году, когда компьютеры все еще были в новинку, Rand Corporation издала книгу, содержавшую миллион случайных цифр [1289]. Их метод описывался так:

Случайные цифры этой книги были получены при помощи рандомизации основной таблицы, сгенерированной эле к-тронной рулеткой. Вкратце, источник импульсов, выдающий их со случайной частотой в среднем около i00000 импульсов в секунду, открывался раз в секунду импульсом постоянной частоты. Цепи нормализации импульса пропускали импульсы ч е-рез 5-разрядный бинарный счетчик. По сути машина являлась колесом рулетки с 32-позициями, которое в среднем делало около 3000 оборотов за выборку и выдавало одно число в секунду. Использовался двоично-десятичный преобразователь, который преобразовывал 20 из 32 чисел (оставшиеся двенадцать отбрасываются) и оставлял только последнюю цифру двузначных чисел. Эти последние цифры попадали в компостер IBM, образуя в конце концов таблицу пробитых карточек случайных цифр.

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

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

Главным содержанием этой книги была "Таблица случайных цифр". Цифры приводились пяти разрядными группами - "i0097 32533 76520 i3586 . . . - по 50 в строке и по пятьдесят строк на странице. Таблица занимала 400 страниц и, за исключением особенно выдающейся группы на странице 283, выглядевшей как "69696", была достаточно скучным чтивом. В книгу также входила таблица i00000 нормальных отклонений .

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

Использование случайного шума

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

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

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

Подключите к компьютеру счетчик Гейгера, подсчитайте количество импульсов за фиксированный интервал времени и возьмите младший бит. Или измерьте время между последовательными тиками ticks. (Так как радиоактивный источник распадается, среднее время между последовательными тиками непрерывно увеличивается . Чтобы этого избежать, надо выбирать источник с достаточно длинным периодом полураспада - такой как пл у-тоний. Если вы беспокоитесь о своем здоровье , можете внести соответствующие статистические поправки .)

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

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

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

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

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

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

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

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