Простейшие алгоритмы генерации
Заслуга конструирования длинных псевдослучайных рядов с хорошими статистическими свойствами полностью принадлежит криптографии. Не следует думать, что они нужны лишь криптографам - картирование Венеры стало возможным, когда длина периода случайного ряда импульсов превысила 10**40. Фотографирование этой планеты нельзя было сделать потому, что она всегда закрыта плотным слоем облаков. Локация же ее с Земли затруднена обилием помех и высокими требованиями к разрешению. Поэтому зондирование выполнялось случайной последовательностью импульсов указанного периода. После 300 зондирований, на что ушло более полгода, была получена карта, где различимы объекты размером около километра, а по высоте разрешение получено такое, какое достигнуто не везде на Земле. Генераторы псевдослучайных чисел используются очень широко в сотнях программных приложений от конструирования ядерных реакторов и радиолокационных систем раннего обнаружения до поисков нефти и многоканальной связи. Генерация псевдослучайных последовательностей давно занимала математиков. Одним из первых было предложение получать их как значения дробной части многочлена первой степени:
Yn = Ent (a*n+b)
Если n пробегает значения натурального ряда чисел, то поведение Yn выглядит весьма хаотичным. Еще Карл Якоби доказал, что при рациональном коэффициенте а множество {Yn} конечно, а при иррациональном бесконечно и всюду плотно в интервале от 0 до 1. Для многочленов больших степеней такая задача была решена лишь в 1916 году выдающимся математиком нашего века Германом Вейлем. Кроме того, он установил критерий равномерности распределения любой функции от натурального ряда чисел. Небезынтересно привести его в краткой формулировке.
КРИТЕРИЙ ВЕЙЛЯ. Чтобы ряд х1, х2, x3, ... был распределен равномерно в интервале от 0 до 1, необходимо и достаточно, чтобы для любой интегрируемой по Риману функции f(x) было справедливо соотношение P{=Mf(x)}=1.
Это соотношение выражает свойство, называемое эргодичностью и заключающееся в том, что среднее по реализациям псевдослучайных чисел равно среднему по всему их множеству с вероятностью 1. Таким образом, Вейль доказал, что эргодичность гарантирует отсутствие экзотичности в поведении последовательности Xn.
Однако эти результаты далеки от практики получения псевдослучайных рядов чисел. Дело в том, что теорема Якоби относится к действительным числам х и у, которые не могут быть использованы при вычислениях, потому что иррациональные действительные числа требуют для своей записи бесконечного числа знаков. Попытки замены настоящего иррационального числа его приближением на ЭВМ для генерации псевдослучайной последовательности опасны, так как получаемые последовательности оканчиваются циклами с коротким периодом. Завершают доказательство непригодности полиномиальных и других функциональных преобразований натурального ряда чисел для получения псевдослучайных последовательностей результаты Пуанкаре. В частности он установил, что непрерывное отображение Т области U числового пространства в себя обязательно приводит к короткой цикличности траекторий Tn(х) для всюду плотного в U множества точек, если учитывать попадание траекторий точек в их сколь угодно малые окрестности или ряды чисел, созданные таким методом, отягчены периодичностями.
Несмотря на непригодность для криптографии простых последовательностей чисел, рассмотрим все же самые распространенные из них. Наиболее древний вычислительный способ генерации псевдослучайных чисел на ЭВМ принадлежит Джону фон Нейману и относится к 1946 году. Этот способ базировался на том, что каждое последующее случайное число образуется возведением предыдущего в квадрат и отбрасыванием цифр с обоих концов. Способ Неймана оказался ненадежным и очень быстро от него отказались. Из простейших процедур, имитирующих случайные числа, наиболее употребляем так называемый конгруэнтный способ, приписываемый Д.Х. Лемеру:
G(n+1)=KGn+C MOD M
В нем каждое последующее псевдослучайное число G(n+1) получается из предыдущего Gn умножением его на К, сложением с С и взятием остатка от деления на М. Весь фокус здесь в том, чтобы подобрать хорошие значения К, С и М, на что были потрачены десятилетия работы математиков. Подбор почти иррациональных К ничего не дает. Например, выбрав закон генерации последовательности G(N+1) = Ent (sqr(2)*Gn) на IBM PC при формате представления чисел с плавающей запятой IEEE в 4 байта, получим псевдослучайные ряды, обязательно заканчивающиеся циклами с периодами длиной всего лишь 1225 и 147 в зависимости от начального заполнения. Разумнее вычисления вести в целых числах. Для них было установлено, что при С=0 и М=2**N наибольший период М/4 достигается при K=3+8*i или K=5+8*i и нечетном начальном числе. При достаточно больших К ряд производит впечатление случайного. Насколько это верно читатель может выяснить самостоятельно следующей программой:
'----------проверка случайности ряда чисел
DEFINT A-Z: SCREEN 2: CLS
n = 1
DO
nold = n: n = FnRnd% (n)
PSET (nold/64,CVL(MKI$(n)+MKI$(0) )\512)
LOOP UNTIL n = 1
END
'----генерация ряда чисел с периодом 16384
DEF FnRnd% (n) =CVI(LEFT$(MKL$(1381&*n) ,2))
В ней случайность ряда проверяется отображением на экране дисплея пар его чисел (Gn+1, Gn) в прямоугольнике размером 128 х 512. Это простой и удобный способ проверки случайности рядов чисел, так как на глаз заметны малейшие закономерности в получаемом орнаменте. Из опытов с этой программой можно убедиться, что как ни экспериментируй с подбором К, все равно закономерности видны и чисто случайного рада чисел не получишь. Вспомните ехидное предложение Додо "становиться строго в беспорядке" из "Алисы в стране чудес". Результат можно несколько улучшить. Если С нечетно и K=1+4*i, то период ряда равен М. После долгих поисков К исследователи остановились на значениях 69069 и 71365. Кроме значений М=2**N широко используются выборы простых М, например, простого числа М=2**31-1, известного со времен Эйлера (Это число "плохо" тем, что в двоичной записи содержит лишь единицы. Однако оно может использоваться, если вычисления выполняются в десятичной арифметике.)
Однако обратимся к фактам. В 1948 году фон Нейман предложил генератор псевдослучайных чисел, который через год подвергся резкой критике. В 1972 году в пакете прикладных программ IBM 360 на языке Фортран появилась программа RANDU, а в 1977-м Форсайт показал, что тройки ее последовательных значений лежат на 15 параллельных плоскостях. В 1979 году Скраг опубликовал компактный алгоритм генерации псевдослучайных чисел, а через год Плаке доказал его статистическую неудовлетворительность. Этому списку нет конца: более месяца работы автор потерял из-за некомпетентно сделанного генератора случайных чисел в системе М86 ЕС 1840, который использовался для моделирования сложных процессов. В журнале "Наука и жизнь" за октябрь 1986 года М. Максимов поместил статью-предупреждение под названием "Случайны ли случайные числа?", где совершенно справедливо отметил негодность используемых генераторов. По его данным, генератор FRAN у БК-0010 имеет длину периода всего лишь 2**15, а бьет рекорды бессмыслицы генератор Бейсика ДВК, который имеет период лишь 8192 и последовательные тройки его "случайных" чисел, функционально связанные уравнением Gn-6*G(n+1)+9*G(n+2), равны целым числам. Не иначе, как от отчаяния, рад исследователей одновременно использует два и даже три разных генератора, смешивая их значения. Если разные генераторы независимы, то сумма их последовательностей обладает дисперсией, равной сумме дисперсий отдельных последовательностей. Иначе говоря, случайность рядов возрастает при их суммировании. Это дает слабую надежду на возможность конструирования генератора с приемлемыми для криптографии свойствами: случайностью и большой длиной периода.
Заметим, что некоторые "запутывания" последовательностей псевдослучайных чисел лишь ухудшают их статистические свойства. Далеко не всегда сложность формирования рада порождает случайность распределения. Например, генератор случайных чисел из игровой программы неизвестного происхождения для программируемого калькулятора использовал в качестве случайных чисел первые цифры последовательности {83**K}. Легко доказывается, что такой генератор будет на 14% чаще давать цифру 7, чем 8. В литературе приводится громадное количество формул для генерации случайных рядов, и автору довелось испытать их не один десяток, но, не то чтобы хорошей, а даже удовлетворительной по статистическим свойствам найти не удалось. Сдается, что часть подобных способов генерации случайных рядов предложена в качестве шутки криптографами, желающими упростить себе работу. Однако в системах программирования обычно используют все же конгруэнтные генераторы по алгоритму, предложенному Национальным бюро стандартов США, который, имея длину периода 2**24, обеспечивает очень неплохие статистические свойства. К сожалению, длина его периода для криптографии слишком мала и, кроме того, было доказано, что последовательности, генерируемые конгруэнтными генераторами, не являются криптографически стойкими. Если дана часть такой последовательности достаточной длины, то ее параметры могут быть восстановлены.
Интересный класс генераторов случайных чисел неоднократно предлагался многими специалистами целочисленной арифметике, в частности Джорджем Марсалиа и Арифом Зейманом. Генераторы этого типа основаны на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0, 1, 1, 2, 3, 5, 8, 13, 21, 34...}. За исключением первых двух ее членов, каждый последующий член равен сумме двух предшествующих. Если брать только последнюю цифру каждого числа в последовательности, то получится последовательность чисел {0, 1, 1, 2, 5, 8, 3, 1, 4, 5, 9, 4...} Если эта последовательность применяется для начального заполнения массива большой длины, то, используя этот массив, можно создать генератор случайных чисел Фибоначчи с запаздыванием, где складываются не соседние, а удаленные числа. Марсалиа и Зейман предложили ввести в схему Фибоначчи "бит переноса", который может иметь начальное значение 0 или 1. Построенный на этой основе генератор "сложения с переносом" приобретает интересные свойства, на их основании можно создавать последовательности, период которых значительно больше, чем у применяемых в настоящее время конгруэнтных генераторов. По образному выражению Марсалиа, генераторы этого класса можно рассматривать как усилители случайности. "Вы берете случайное за- полнение длиной в несколько тысяч бит и генерируете длинные последовательности случайных чисел". Однако большой период сам по себе еще не является достаточным условием. Слабые места гамм бывает трудно обнаружить и аналитику требуется применять утонченные методы анализа последовательностей, чтобы выделить определенные закономерности, которые скрыты в большом массиве цифр.
Последнее, на чем следует остановить внимание, это особенности использования стандартных генераторов случайных чисел в различных языках программирования, если уж ими пришлось воспользоваться. Так отметим, что известный в Бейсике оператор RANDOMIZE (Он такой же, как и во всех других языках программирования. например. Pascal или C++.) , применяемый для начальной установки генератора случайных чисел, может ошарашить пользователя. Ибо после выполнения:
RANDOMIZE 231
х = RND
RANDOMIZE 231
у = RND
необязательно получится х=у, потому что оператор RANDOMIZE переустанавливает не всё случайное число из 3 байт, а лишь его часть из 2 байт. Точная установка может быть произведена функцией RND, как x=RND(-231). Не нужно думать, что эта проблема встречается лишь при программировании на Бейсике. Паскаль и Си всех фирм дают те же результаты. А вот увеличение периода последовательности сделать несколько сложнее. Для этого можно использовать функцию:
FUNCTION Rand (х, у)
х = RND (-х)
у = RND (-у): IF у = О THEN у = RND (-у)
Rand = (х+у) MOD 1
END FUNCTION
Период такой функции равен 2**24-(2**24-1), но вот свойства его ряда не обязаны при любых исходных х и у быть такими же хорошими, как у RND.
При создании с помощью встроенного генератора случайных чисел объектов, имеющих число состояний большее, чем у генератора, его приходится использовать несколько раз, переустанавливая по заранее заданному ключу. Например, следующий фрагмент программы:
FOR i = 1 ТО 5
х = RND (-gamma (i))
FOR j = 0 TO 32
SWAP map (j), map (32 * RND)
NEXT: NEXT
производит случайную перестановку 33 элементов массива map, которая может быть сделана примерно 2**118 способами, и при длине периода генератора в 2**24, его нужно запустить не менее 5 раз, чтобы реализовать все варианты перестановки.
