Цифровой журнал «Компьютерра» № 42

нулей и единиц (это соответствует двоичному представлению целых чисел). Такое представление соответствует способу получения этих последовательностей. Берется некоторый «шумящий» прибор, который в данный момент времени может как выдать, так и не выдать определенный сигнал (в зависимости от результата в шифр заносится единица или нуль). Имеется довольно большое разнообразие таких приборов. Главные критерии их качества — быстрота фиксации и «непредсказуемость» наличия сигнала.

В частности, в октябрьском номере журнала Nature Photonics сообщается, что группа ученых из Германии и Дании создала квантовый генератор хаотических сигналов, который стал одним из лучших в мире по указанным критериям. Как пишет журнал «Успехи физических наук», принцип работы генератора основан на случайном характере вакуумных колебаний электромагнитного поля.

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

О том, в чем схожи и различны понятия и способы реализации случайного числа в криптографии и в вычислительной математике, рассказывает доктор физико-математических наук, ведущий научный сотрудник Института вычислительной математики и математической геофизики Сибирского отделения РАН, профессор кафедры вычислительной математики Новосибирского государственного университета, специалист в области теории методов Монте-Карло Антон Войтишек.

- Антон Вацлавович, чем различаются случайные и псевдослучайные числа в теории методов Монте-Карло? Как они соотносятся с понятием случайного числа в криптографии?

- При применении методов численного статистического моделирования требуется получать на компьютере выборочные значения случайных величин с различными законами распределения. Здесь используются различные формульные и алгоритмические преобразования стандартных случайных чисел ?_j которые распределены равномерно в интервале (0,1) («на пальцах» это означает, что частота появления этих чисел в различных частях единичного интервала одинакова). А вот для получения чисел ?_j используются датчики (генераторы) стандартных случайных чисел.

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

Конструирование физических датчиков основано на том, что двоичное представление стандартного случайного числа ? (а именно такое представление чисел реализуется в компьютере) имеет вид

? = 0,10011001010...

то есть целая часть числа равна нулю (ведь ? расположено между нулем и единицей), а в «хвосте», следующем после запятой (этот «хвост» по научному называется мантиссой, а нули и единицы заполняют разряды мантиссы), стоят нули и единицы. Появление нуля и единицы (вне зависимости от значений в соседних разрядах) происходит с равной вероятностью (то есть с вероятностью 1/2).

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

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

К слову, при получении чисел (шифров) в криптографии последнее требование желательно, но не обязательно. Здесь нет нужды увязывать наборы нулей и единиц с приведенным выше представлением стандартного числа ?_j. Если обнаруживаются слишком длинные серии нулей или единиц, то реализуются специальные алгоритмы, удаляющие следы повторяемости. Это тоже обуславливает существенное отличие «криптографических» чисел от стандартных случайных чисел, используемых в методах Монте-Карло: для последних длинные серии нулей и единиц в мантиссе вполне допустимы.

- Какие сигналы можно использовать в физических датчиках?

- Можно крутить рулетку, раскрасив предварительно круг в два цвета (например, в красный и черный); красный цвет может соответствовать единице, черный — нулю. К слову, этот возможный способ получения стандартных случайных чисел обусловил название методов Монте-Карло, ведь в знаменитом игорном центре тоже крутят рулетку. Недостаток этого способа получения случайных чисел: долгое время реализации и отсутствие автоматизации процесса получения случайных нулей и единиц. Зато здесь более- менее гарантирована вероятность 1/2, если круг раскрашен двумя цветами пополам.

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

Проблему получения равных вероятностей появления нуля и единицы часто решают следующим образом. Сигнал замеряют дважды. Возможны следующие исходы: оба раза сигнал был (состояние СС), оба раза сигнала не было (состояние НН), первый был — второго не было (состояние СН) и первый не был — второй был (состояние НС). Если даже вероятность появления сигнала не равнялась в точности 1/2, то все равно состояния НС и СН являются равновероятными. То есть можно фиксировать только эти два состояния (приписав, например, состоянию НС единицу, а СН — нуль), а состояния СС и НН игнорировать.

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

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

Поэтому большинство расчетов по методу Монте-Карло производится с использованием генераторов псевдослучайных чисел.

- Как устроены генераторы псевдослучайных чисел?