Тихой сапой

Идея апгрейда зрела давно. Силенок старенького К6-200 хватало для большинства повседневных задач, но вот на праздники жизни - просмотр DivX-фильмов и даже прослушивание mp3-файлов - оставались жалкие, неудобоваримые крохи.

Идея апгрейда зрела давно. Силенок старенького К6-200 хватало для большинства повседневных задач, но вот на праздники жизни - просмотр DivX-фильмов и даже прослушивание mp3-файлов - оставались жалкие, неудобоваримые крохи. По предварительным прикидкам, изменения намечались на конец года: К6-200 должны были сменить новая системная плата и один из Duron’ов - и вследствие давней привязанности к продукции AMD, и - несомненных прошлогодних достижений этой фирмы. Как оказалось, Intel я списывал со счетов и напрасно, и преждевременно: эти строки я набиваю на компьютере с процессором Celeron 566 и интеловским же чипсетом i815…

А началось все с того, что одному из приятелей потребовался генератор случайных чисел, и я вызвался ему помочь. Простые, программные, отсекались сразу - они рано или поздно зацикливаются (период, впрочем, может измеряться многими миллиардами отсчетов), генерируя последовательности, получившие название псевдослучайных, а таковые не подходили по условиям задачи. Приятель подумывал о генераторе на счетчике Гейгера, мне встречались генераторы белого шума на туннельных диодах, дело оставалось за малым - спаять и протестировать. Первое большой проблемы не представляло, а вот второе…

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

Тем не менее, промышленные аппаратные генераторы случайных чисел все же нашлись. Сначала - в разработках некоторых наших компаний-производителей криптопроцессоров: хороший генератор случайных чисел является неотъемлемой принадлежностью многих алгоритмов шифрования. Некоторым из читателей наверняка приходилось набирать на клавиатуре «случайные» комбинации клавиш для генерации открытых и закрытых ключей. Неудобство этой процедуры и, иногда, предсказуемость получаемых таким образом ключей привели к распространению аппаратных генераторов, сначала как отдельных устройств, а затем - не побоюсь этого слова - нашествию генераторов, имплантированных в (некоторые) процессорные чипсеты. Нашествию, притом, тихому - ни один из моих приятелей и не подозревал о столь удивительных возможностях ¹. Да и сам я узнал совершенно случайно во время странствий по Интернету в поисках оптимального решения. А узнав и скачав драйвер, с разочарованием убедился, что ни один из имеющихся в распоряжении компьютеров, даже новенький ноутбук, им не поддерживается - в силу отсутствия самого генератора, неотъемлемой принадлежности всех современных интеловских чипсетов из ряда i810, 815, 820 и последующих… И тут, как иногда бывает, на помощь пришли Евгений Козловский и компания ASUSTeK, любезно согласившаяся предоставить материнскую плату CUSL2.

Излишне говорить, что поведение драйвера преобразилось, как и то, что проводить с ним эксперименты не хотелось совершенно. Размеры дистрибутива - почти два мегабайта - вызывали весьма обоснованные подозрения в чистоте всяческих экспериментов. Тем не менее, интерфейс тестовой программы, поставляемой с драйвером, позволял генерировать длинные тестовые последовательности, правда, с выводом этой и массы другой сопроводительной информации в log-файл. Откуда получившиеся 32-битовые числа (разумеется, в символьном десятичном представлении) можно извлечь с помощью простого текстового фильтра. Замечу, что процесс сбора случайных чисел сопровождается непрерывным тестированием генератора: один тест на каждую тысячу отсчетов ² (см. рис.).

Пришлось засесть за изучение литературы и дополнительных источников, благо их и в Интернете, и в офлайне предостаточно.

Прежде всего скажу немного о том, как устроен тот самый RNG, или Intel Random Number Generator. Источником случайного процесса, в данном случае - теплового шума, служит резистор, вернее, пара резисторов, включенных вместе с усилителем по дифференциальной схеме. Это позволяет в значительной мере подавить воздействие внешних наводок, флуктуаций источника питания и температурного дрейфа самих резисторов. Напряжение с выхода усилителя поступает на генератор, управляемый напряжением, который формирует прямоугольные импульсы с частотой, в несколько раз меньшей частоты опорного, высокочастотного генератора (в случае Intel RNG это отношение порядка 1:100). Прямоугольные импульсы с генераторов поступают на триггер, переключающийся по одному из фронтов низкочастотного шумового импульса. На выходе триггера при условии, что частота низкочастотного генератора меняется в значительных пределах (обычно достаточно девиации в 10-20 периодов частоты опорного генератора), получается случайная двоичная последовательность, причем (из общих соображений) внешние шумы могут только увеличить ее случайный характер (при условии, что они не скоррелированы с тепловым шумом резисторов).

Получившаяся последовательность поступает на фон-неймановский отбеливатель, который устраняет шумы, вызванные «дребезгом контактов» (или, вернее, высокочастотными составляющими теплового шума) и остаточными смещениями генератора.

Принцип работы корректора очень прост: он игнорирует неизменные последовательности нулей и единиц ³.

С выхода корректора поток битов направляется в буфер (FIFO), формирующий из нее случайные байты. Понятно, что путем дальнейшей обработки из этих байтов можно формировать случайные числа любой длины ⁴, в том числе - знакопеременные, что и подтверждает пример из руководства по программированию. Понятно так же и то, что вследствие применения отбеливателя Intel не берется гарантировать частоту обновления случайных чисел - ведь на выходе триггера случайным образом может появиться довольно длинная последовательность нулей или единичек.

Интерфейс с компьютером устроен очень просто: заглянув (под Windows) в менеджер устройств контрольной панели, можно обнаружить, что Intel 82802 Firmware Hub Device занимает адресное пространство FFB80000-FFBFFFFF, а заглянув в [3] - что для обмена с процессором используются три байтовых регистра: Hardware Status, RNG Status и RNG Data. Первый служит индикатором наличия RNG, а также - для перевода его в рабочее состояние. После чего, убедившись, что в RNG Status установлен соответствующий флажок, можно смело считывать данные из RNG Data.

Вот и все. Тем не менее, вследствие того, что написать соответствующий драйвер под Windows 2000 оказалось не просто, а разбираться в таинствах CryptoAPI хотелось еще меньше, пришлось воспользоваться другой операционной системой - Linux, для которой драйвер:

• доступен в исходных кодах;

• весит 20 Кбайт;

• поддерживает работу в двух режимах: как символьное устройство /dev/intel_rng, представляющее собой «трубу» из регистра RNG Data в операционную систему, и в качестве источника энтропии для /dev/random.

Ясно, что из эмпирических соображений меня больше всего интересовало /dev/intel_rng. Для подключения этого устройства под Linux достаточно убедиться, что драйвер входит в ядро (если нет - скачать с sourceforge.net/projects/gkernel) , включить поддержку Intel_rng в конфигураторе ядра (в разделе символьные устройства как модуль или в составе ядра) и перекомпилировать ядро. Подключение устройства производится командами modprobe i810_rng и mknod /dev/intel_rng 10 183.

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

Таковой, в простейшем случае, можно произвести программой ent, доступной в исходных кодах для Linux и, что удобно, с откомпилированным модулем для DOS. Программа производит набор тестов для равномерно распределенных генераторов случайных чисел, подсчитывая энтропию, возможную степень сжатия массива данных, определяя (по методу Монте-Карло) число p (формируя для этого из байтового потока два двухбайтовых числа и определив, принадлежит эта пара окружности или квадрату, а также зная отношение попаданий, можно определить число p??? из предположения, что числа равномерно распределены), критерий c², степень коррелированности отсчетов и арифметическое среднее ряда. Как дополнительные опции можно строить гистограммы ряда или трактовать его как поток случайных битов.

В общем, возможностей предостаточно для того, чтобы вволю поэкспериментировать не только со случайными числами, но и, например, с графическими и текстовыми файлами - скажем, проверить справедливость утверждения, что энтропия типичного текста на английском языке - около полутора бит на символ ⁵, а программы на С - 4,9 бита/символ (соответственно, оптимальный компрессор сожмет такой файл на 38%).

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

Видно, что мой Intel RNG мало чем отличается от доступного в сети RNG на счетчике Гейгера (см. www.fourmilab.ch/hotbits). А вот JPEG-файл, хотя и имеет очень высокую плотность информации (энтропию), не может быть использован как датчик случайных чисел ⁶.

Тем временем о поддержке Intel RNG в своих криптографических продуктах заявили Aladdin Knowledge Systems, Baltimore Technologies, Entrust Technologies, RSA Data Security и SSE. От AMD и других производителей чипсетов пока ничего не слышно…

Источники

[1] developer.intel.com/design/chipsets/rng/docs.htm.

[2] Cryprography Research, Inc. The Intel Random Number Generator.

[3] Intel 82802 Firmware Hub: Random Number Generator. Programmer’s Reference Manual.

[4] Дональд Э. Кнут «Искусство программирования», т. 2. И. д. «Вильямс», 2000.

[5] www.fourmilab.ch/random/.

[i38548]