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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

char Randpool[16];

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

является в некоторой мере чем-то непредсказуемым. */

void churnrand(char *randevent,unsigned lnt randlen) { MD5 CTX md5; MD5Init(&md5);

MD5Update(&md5, Randpool , sizeof(Randpool)); MD5Update(&md5 , randevent , randlen ); MD5Final(Randpool,&md5);

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

long Randcnt;

void genrand(char *buf,unsigned int buflen) { MD5 CTX md5; char tmp[16]; unsigned int n; while(buflen != 0) {

/* Пул хэшируется счетчиком */

MD5Init(&md5);

MD5Update(&md5, Randpool, sizeof(Randpool)); MD5Update(&md5,(unsigned char *)&Randcnt,sizeof(Randcnt)); MD5Final(tmp,&md5);

Randcnt++; /* Инкрементируем счетчик */

/Копируем 16 или запрошенное число байтов, если оно меньше 16, в буфер пользователя*/

n = (buflen < 16) ? buflen : 16; memcpy(buf, tmp, n); buf += n ; buflen -= n;

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

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

Но остается одна проблема. Прежде, чем в первый раз будет вызвана genrand() в массиве Randpool[] должно быть накоплено достаточно случайных данных . Если система какое-то время работала с локальным пользователем, что-то печатающим на клавиатуре, то проблем нет . Но как насчет независимой системы, которая перегр у-жается автоматически, не обращая внимания ни на какие данные клавиатуры или мыши ?

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

Решением этой проблемы является хэширование массива Randseed[] перед его сохранением, может даже вызовом genrandO. При перезагрузке системы вы считываете данные из стартового файла, передаете их

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