В поисках случайности

Ничто не случайно, а только не определено.
Nothing is random, only uncertain.
Гейл Гэсрэм

Упомянутый в преамбуле парадокс на самом деле отражает особенности двух важнейших областей применения компьютеров -- коммерческих и научных вычислений. С одной стороны, коммерция озабочена безопасностью -- особенно в условиях, когда среднестатистический общедоступный ПК вырвался за рамки производительности суперкомпьютеров пятнадцатилетней давности, а по сложности ПО вообще не имеет исторических прецедентов, подходящих для сравнения. С другой -- потребности в мощных научных вычислителях намного обгоняют возможности совершенствования сложных архитектур многопроцессорных систем, и, что главное, эти потребности очень плохо согласуются с реальными бюджетами научных организаций. Как ни странно, но в обеих ситуациях роль генератора псевдослучайных (или случайных) чисел крайне важна. Характеристики систем безопасности в большинстве своем зависят от характеристик их криптографических подсистем, которые определяются не только алгоритмикой, но и качественными показателями именно используемых ГПЧ или ГСЧ. Потребность в росте быстродействия на фоне неизменного (или сокращающегося) бюджета научных организаций буквально вынуждает создавать кластерные вычислители на основе самых заурядных "настольных и офисных" технологий, что делает актуальным применение подходящих для подобных архитектур математических методов (в первую очередь, разновидностей метода статистических испытаний, иначе называемого "Монте-Карло"). И здесь эффективность этого метода во многом (часто -- практически во всем) определяется качественными показателями используемых ГПЧ или ГСЧ.

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

Генераторы случайных чисел

Типичный АГСЧ "паразитного" класса -- вид "начинки". В правом углу платы -- большой "шумящий" диод. Остальной аппаратный "набор" примитивен -- микросхема усилителя и формирователя сигналов интерфейса RS-232

"Иcточник энтропии" проекта Lavarnd

Минимизация расходов в действиии -- каждая лишняя операция должна быть устранена. Наверное, по этой причине разработчики из Lavarnd оставили QuickCam "в товарном виде", даже не разбирая ее корпуса...

Генерация случайных чисел на фотонном уровне -- блок-схема швейцарской экспериментальной разработки

Эта категория "источников случайности" -- самая экзотическая и от "чистого" программирования весьма далека. Все дело в том, что по ряду причин все программные реализации "ГСЧ" следует правильно называть исключительно генераторами псевдослучайных чисел (к слову, эта причинно-следственная связь имеет строгое математическое обоснование). Что означает -- даже невероятно хороший программный генератор всегда будет подпадать под определение Гейла Гэсрэма, использованное в качестве эпиграфа к статье (Гейл Гэсрэм -- автор одного из самых мощных программных инструментальных комплектов, предназначенных для тестирования ГСЧ и ГПЧ). А вот это для разработчиков систем шифрования с высокой криптостойкостью является синонимом или к жесткому вердикту "не годится", или к более мягкой формулировке "подходит с ограничениями". Короче говоря, "псевдо-" -- оно и есть "псевдо-". И было бы удивительно, если бы разработчики этого не знали и такое знание не переросло в потребность в... одних из самых необычных периферийных устройств -- аппаратных генераторах случайных чисел. А раз есть потребность -- значит, подобные устройства непременно возникнут. И они, естественно, существуют, причем разнообразие используемых технических приемов и решений в этой области способно действительно поразить воображение.

Самые простые аппаратные ГСЧ (АГСЧ) основаны на тех свойствах элементов электронных схем, с которыми так долго и упорно боролись инженеры-схемотехники. Это свойство -- собственные шумы электронного прибора -- всегда доставляло немало хлопот при проектировании прецизионной или высокочувствительной электроники. Но для создателей ГСЧ "шумящий" элемент является ключевым. Будь то топорно изготовленный резистор, фотодиод или обычный диод -- он в той или иной степени пригоден для создания ГСЧ (поэтому класс подобных АГСЧ можно смело назвать "паразитным"). Достаточно обеспечить этому элементу такой режим работы, при котором его шумовые параметры по классике электроники будут наихудшими, и можно ожидать очень неплохого результата: усиление сигналов собственного шума элемента и превращение их из аналоговой в цифровую форму -- задача, в общем, несложная, а с использованием современной элементной базы -- тривиальная. Основанные на подобных принципах аппаратные ГСЧ малосерийно производятся фирмами самых разных стран (правда, не стоит обольщаться элементарностью их конструкции -- как и во всех случаях, здесь цена конечного изделия определяется не столько затратами на его разработку и изготовление, сколько соотношением последних с емкостью рынка, так что стоят они недешево, что подогревает интерес многочисленных самодельщиков из далеко не бедных государств).

В отдельный подкласс подобных АГСЧ стоит вынести экзотические разработки, основанные на том же принципе (использование собственных шумов электронного прибора), но радикально отличающиеся сложностью этого прибора. Здесь вместо дискретного электронного компонента применяется куда более сложный источник естественной случайности. Например, в "отпочковавшемся" от лабораторий знаменитой SGI проекте Lavarnd в качестве источника шума применяется... ПЗС-матрица обычной бытовой компьютерной видеокамеры QuickCam. Помещенная в специальный футляр при полном отсутствии света ПЗС-матрица камеры "загоняется" управляющей программой в наихудший (как для видеокамеры) режим, при котором шумовые характеристики максимальны и картинка чистого, природного хаоса (для нее достаточна только одна составляющая сигнала -- яркость) пригодна к дальнейшей обработке. Забавное техническое решение, позволяющее минимизировать затраты на аппаратные средства, реализовав программно весь тракт дальнейшего формирования последовательности случайных чисел из двухмерной картины хаоса...

Второму обширному классу АГСЧ лучше всего подойдет название "функциональный". Здесь в качестве "источника энтропии" используются фундаментальные функциональные свойства электронных приборов, например счетчиков Гейгера--Мюллера. В остальном, по большому счету, технические нюансы построения АГСЧ остаются такими же, как и в классе "паразитных" АГСЧ (разве что могут отличаться измеряемые величины, на основании которых формируются случайные числа, но в данной ситуации это несущественно). Правда, неприятной особенностью подобных устройств является необходимость применения радиоизотопных источников -- в принципе, можно обойтись и без них, за счет естественного радиационного фона, но генератор случайных чисел, выдающий несколько значений за пару десятков секунд, неинтересен даже владельцу игровых заведений. А если учесть, что, например, в Лабораториях Ферми подобный АГСЧ "упрятан" в подземный бассейн емкостью 70 тыс. литров... такой экзотике действительно трудно найти коммерческое применение, сколь бы ни были хороши ее технические показатели.

Третий класс АГСЧ наиболее экзотический. Настолько экзотический, что коммерческие изделия, которые можно к нему отнести, практически отсутствуют на рынке. Он представлен всего несколькими экспериментальными разработками академической науки. "Фундаментальный" -- никаких других подходящих слов для его названия найти просто невозможно.

Наиболее яркий представитель "фундаментальных" АГСЧ -- разработка группы исследователей Женевского университета "оптический квантовый генератор случайных чисел". Надо отдать должное академической науке Швейцарии -- несмотря на всю "экзотику", этот АГСЧ соединяется с компьютером вполне "одомашненным" и актуальным интерфейсом USB. А вот "фундаментальность", скрытая под коробкой скромного размера... В этом АГСЧ излучаемый сверхслабым импульсом лазерного светодиода поток фотонов направляется в двухметровый сегмент обычного одномодового оптоволокна (что обеспечивает фактически независимость потока фотонов на противоположном "выходе" такой системы от различных флуктуаций параметров излучателя). За "выходным срезом" первого сегмента оптоволокна на расстоянии нескольких миллиметров располагаются один к одному два оптоволоконных сегмента разной длины, на "выходе" одного из которых фотон появляется на 60 нс позже. Именно эта задержка и позволяет "выявить хаос" -- она дает возможность определить, по какому отрезку (короткому или длинному) многомодового оптоволокна "пробежал" фотон -- а уж это дело чистого случая. Обнаружение отдельных (!) фотонов возложено на пассивно охлаждаемый кремниевый лавинный фотодиод (Si APD). Еще одно, без сомнения, забавное устройство, в котором фундаментальные физические принципы, наносекундная синхронизация и самая современная электроника подчинены решению самой утилитарной задачи -- получению случайных чисел, обновляющихся 100 тыс. раз в секунду.

Четвертый класс АГСЧ можно условно назвать "паразитным персонально-компьютерным". В его представителях используются те отвратительные нюансы "поведения" фактически стандартных компонентов обычного современного ПК (в первую очередь -- звуковых адаптеров), с которыми так старательно борются их разработчики. К этим нюансам относятся прежде всего тепловые шумы и флуктуации в подсистеме аналогового ввода/вывода звукового адаптера. Привлекательность представителей такого класса, естественно, заключается и в характеристике "cost for nothing" ("забесплатно"), и в возможности развитой программной реализации самых изощренных механизмов обработки для получения почти идеального ГСЧ. Но и здесь есть свои "но" -- подобные АГСЧ (одна из самых развитых и весьма совершенных разработок этого класса -- ГСЧ turbid Джона Денкера, доступна пользователям Unix-подобных систем на условиях Open Source) нуждаются в тщательных процедурах настройки и калибровки.

В отдельный класс "курьезных" АГСЧ можно выделить самые немыслимые среди существующих разработки, например специализированных роботов, методично бросающих... обычные игральные кости и оснащенных системой технического зрения для считывания выпавших очков. Впрочем, курьезность этих проектов (большие затраты на реализацию, сверхнизкая частота обновления информации на "выходе" устройства) иногда оправдывается. А именно, в изделиях последнего, рассматриваемого нами, класса.

"АГСЧ-файлы" и "АГСЧ-серверы" -- после некоторых раздумий автор решил все-таки выделить эти странные разновидности в отдельный класс. "АГСЧ-файлы" -- это записанные в большие файлы результаты работы аппаратных генераторов случайных чисел и высококлассных специалистов математической статистики и теории вероятностей, и наконец, мощных инструментальных средств. Короче говоря, это фрагменты хаоса, тщательно проверенные на хаотичность. Их можно легально бесплатно загрузить, например, с сайта www. random.org/files/ или с персонального ресурса Гейла Гэсрэма (файлы bits.01-bits.60). "АГСЧ-серверы" -- это серверы публичного доступа, избавляющие разработчика прикладного ПО от необходимости использовать собственный АГСЧ (например, на этапах тестирования и отладки). Наиболее известный подобный ресурс -- www.random.org -- предоставляет в распоряжение программистов сервис АГСЧ посредством HTTP-протокола или как удаленный CORBA-компонент, а также целый букет готовых фрагментов клиентских программ в исходных текстах (от Perl до C#).

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

Если взыскательным специалистам по криптографии АГСЧ буквально необходимы, то для специализирующихся на решении разнообразных вычислительных задач прикладной математики инженеров и ученых чаще всего подобные технологические ухищрения избыточны. Здесь достаточен просто очень хороший программный ГПЧ (что означает в данном случае "хороший" -- вопрос весьма сложный, и эту характеристику надо или принимать на веру, или серьезно "зарываться" в глубокие математические дебри). Таким без всякой натяжки можно считать ставшую уже знаменитой крохотную программу Mersenne Twister, автором которой является японский математик и программист Макото Мацумото. Доступная на основе самой либеральной лицензии в исходных текстах Mersenne Twister обладает буквально сногсшибательными характеристиками: так, период повторения псевдослучайной последовательности, генерируемой этим ГПЧ, представляется совершенно астрономической цифрой 219937-1, т. е. десятичным числом примерно из двух тысяч цифр (!). Пожалуй, на кратком описании этой программы можно было бы и остановиться... если бы не одно маленькое "но"...

В большинстве задач прикладной математики, решаемых стохастическими методами, исключительно важным является весьма специфическое свойство "равномерности распределения" случайных чисел, генерируемых ГПЧ. Специфическое потому, что оно радикально отличается от понятия, описываемого тем же термином в математической статистике. Чтобы не было подобной путаницы, термин "равномерность распределения" часто заменяют на "хорошую распределенность" и подчеркивают, что он относится именно к последовательности чисел ("хорошо распределенная последовательность" или "well distributed sequence"). Как и в случаях с АГСЧ, когда хотя и неявно, но подразумевалось, что за аппаратными средствами ГСЧ стоит мощная и сложная программная поддержка, так и в вычислительных применениях ГПЧ даже над таким совершенным генератором, как Mersenne Twister, для получения высоких показателей надо "надстраивать" программную прослойку, формирующую из последовательности случайных чисел хорошо распределенную последовательность. Но это -- предмет отдельного обсуждения, выходящий за рамки статьи. Заинтересованные читатели могут попытаться отыскать информацию о well distributed sequences в Сети или, что более вероятно, найти старые книги в хороших технических библиотеках.