Генерирование случайных последовательностей с заданным вероят­ностным законом и проверка их адекватности - одни из важнейших проблем современной криптологии. Генераторы случайных последова­тельностей используются в существующих криптосистемах для генера­ции ключевой информации и задания ряда параметров криптосистем. Научная и практическая значимость этой проблемы настолько велика, что ей посвящены отдельные монографии в области криптологии, орга­низуются разделы в научных журналах "Journal of Cryptology", "Cryptologia" и специальные заседания на международных научных конфе­ренциях "Eurocrypt", "Asiacrypt", "Crypto" и др.

В начале XX века случайные последовательности имитировались с помощью простейших случайных экспериментов: бросание монеты или игральной кости, извлечение шаров из урны, раскладывание карт, рулетка и т. д. В 1927 г. Л. Типпетом впервые были опубликованы та­блицы, содержащие свыше 40000 случайных цифр, "произвольно из­влечённых из отчётов о переписи населения". В 1939 г. с помощью специально сконструированного механического устройства - генера­тора случайных чисел, М. Дж. Кендалл и Б. Бэбингтон-Смит создали таблицу, включающую 10 5 случайных цифр. В 1946 г. американский математик Джон фон Нейман впервые предложил компьютерный алго­ритм генерации случайных чисел. В 1955 г. компания RAND Corpora­tion опубликовала получившие широкую популярность таблицы, содер­жащие 10 6 случайных цифр, сгенерированных на ЭВМ.

В настоящее время спрос на генераторы случайных последователь­ностей с заданными вероятностными распределениями, а также на сами случайные последовательности настолько возрос, что за рубежом появи­лись научно-производственные фирмы, занимающиеся производством и продажей больших массивов случайных чисел. Например, с 1996 г. в мире распространяется компакт-диск "The Marsaglia random number CDROM", который содержит 4,8 млрд. "истинно случайных" бит.

Подавляющее большинство современных криптографических систем используют либо поточные, либо блочные алгоритмы, базирующиеся на различных типах шифрах замены и перестановки. К сожалению, практически все алгоритмы, используемые в поточных криптосистемах, ориентированных на использование в военных и правительственных системах связи, а также, в некоторых случаях, для защиты информации коммерческого характера, что вполне естественно делает их секретными и недоступными для ознакомления. Единственными стандартными алгоритмами поточного симметричного шифрования являются американский стандарт DES (режимы CFB и OFB) и российский стандарт ГОСТ 28147-89 (режим гаммирования).

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

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

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

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

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) - алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Можно сформировать три основных требования, которым должны удовлетворять криптографическистойкие генераторы псевдослучайных последовательностей или гаммы.

1. Период гаммы должен быть достаточно большим для шифрования сообщений различной длины.

2. Гамма должна быть трудно предсказуемой. Это значит, что если известны тип генератора и кусок гаммы, то невозможно предсказать следующий за этим куском бит гаммы или предшествующий этому куску бит гаммы.

3. Генерирование гаммы не должно быть связано с большими техническими и организационными трудностями.

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

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

И, наконец, третье требование должно гарантировать возможность практической реализации генераторов псевдослучайных последовательностей с учетом требуемого быстродействия и удобства практичного использования. Рассмотрим теперь некоторые практические методы получения псевдослучайных чисел.

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

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

3.1 Линейный конгруэнтный метод

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

Этот алгоритм заключается в итеративном применении следующей формулы:

где a>0, c>0, m>0 - некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X 0 и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности X j определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m . При этом длина периода равна m тогда и только тогда, когда:

· НОД (c, m) = 1 (то есть c и m взаимно просты);

· a - 1 кратно p для всех простых p - делителей m;

· a - 1 кратно 4, если m кратно 4.

Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором констант a и c при заданной разрядности e . Для этих констант выписаны условия, гарантирующие удовлетворительное качество получаемых случайных чисел.

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

3.2 Метод Фибоначчи

Интересный класс генераторов псевдослучайных последовательностей основан на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0,1,1,2,3,5,8,13,21,34 …} - за исключением первых двух ее членов, каждый последующий член равен сумме двух предыдущих.

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

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность, и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел. В англоязычной литературе фибоначчиевы датчики такого типа называют обычно «Subtract-with-borrow Generators» (SWBG).

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

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:

где X k - вещественные числа из диапазона Vi ] 2 Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]

Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.

Аппаратные ГПСЧ

Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы или держатся в секрете . Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA - или ASIC -ячеек). Из-за таких строгих требований к аппаратным ГПСЧ очень трудно создать криптостойкий генератор, поэтому до сих пор все известные аппаратные ГПСЧ были взломаны. Примерами таких генераторов являются Toyocrypt и LILI-128, которые оба являются LFSR-генераторами, и оба были взломаны с помощью алгебраических атак.

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

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

Последовательность случайных чисел {X n } получается с помощью следующего итерационного равенства:

X n +1 = (a X n + c) mod m

Если m, а и с являются целыми, то создается последовательность целых чисел в диапазоне 0 X n < m.

Выбор значений для а, с и m является критичным для разработки хорошего генератора случайных чисел.

Очевидно, что m должно быть очень большим, чтобы была возможность создать много случайных чисел. Считается, что m должно быть приблизительно равно максимальному положительному целому числу для данного компьютера. Таким образом, обычно m близко или равно 2 31 .

Существует три критерия, используемые при выборе генератора случайных чисел:

1. Функция должна создавать полный период, т.е. все числа между 0 и m до того, как создаваемые числа начнут повторяться.

2. Создаваемая последовательность должна появляться случайно. Последовательность не является случайной, так как она создается детерминированно, но различные статистические тесты, которые могут применяться, должны показывать, что последовательность случайна.

3. Функция должна эффективно реализовываться на 32-битных процессорах.

Значения а, с и m должны быть выбраны таким образом, чтобы эти три критерия выполнялись. В соответствии с первым критерием можно показать, что если m является простым и с = 0, то при определенном значении а период, создаваемый функцией, будет равен m-1. Для 32-битной арифметики соответствующее простое значение m = 2 31 - 1. Таким образом, функция создания псевдослучайных чисел имеет вид:

X n +1 = (a X n) mod (2 31 - 1)

Только небольшое число значений а удовлетворяет всем трем критериям. Одно из таких значений есть а = 7 5 = 16807, которое использовалось в семействе компьютеров IBM 360. Этот генератор широко применяется и прошел более тысячи тестов, больше, чем все другие генераторы псевдослучайных чисел.

Сила алгоритма линейного конгруента в том, что если сомножитель и модуль (основание) соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от последовательности, являющейся случайной из набора 1, 2, ..., m-1. Но не может быть случайности в последовательности, полученной с использованием алгоритма, независимо от выбора начального значения Х 0 . Если значение выбрано, то оставшиеся числа в последовательности будут предопределены. Это всегда учитывается при криптоанализе.

Если противник знает, что используется алгоритм линейного конгруента, и если известны его параметры (а = 7 5 , с = 0, m = 2 31 - 1), то, если раскрыто одно число, вся последовательность чисел становится известна. Даже если противник знает только, что используется алгоритм линейного конгруента, знания небольшой части последовательности достаточно для определения параметров алгоритма и всех последующих чисел. Предположим, что противник может определить значения Х 0 , Х 1 , Х 2 , Х 3 . Тогда:

Х 1 = (а Х 0 + с) mod mХ 2 = (а Х 1 + с) mod mХ 3 = (а Х 2 + с) mod m

Эти равенства позволяют найти а, с и m.

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

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

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

Конструктивний підхід к определению случайной последовательности предложили Блюм, Голдвассер, Микалли и Яо. Их определение считает последовательность случайной, если не существует полиномиального (вероятностного) алгоритма, который сможет отличить ее от чисто случайной. Такая последовательность называется полиномиально неразличимой от случайной илипсевдослучайной .

Этот подход позволяет использовать для формирования псевдослучайных последовательностей (ПСП) детерминированные алгоритмы, реализуемые конечными автоматами. Хотя с математической точки зрения такие последовательности не случайны, так как они полностью определяются начальным заполнением, тем не менее, их практическое использование не дает никаких преимуществ криптоаналитику благодаря “неразличимости” со случайными. Поскольку этот подход представляется более конструктивным, остановимся на нем детальнее.

Случайные последовательности в смысле последнего определения также называют “случайными для всех практических применений”. Генераторы таких последовательностей, называют криптографически надежными (cryptographically strong ) или криптографически безопасными (cryptographically secure ). Псевдослучайность в данном случае есть не только свойство последовательности (или генератора), но и свойство наблюдателя, а точнее его вычислительных возможностей.

Для ПСП доказаны два важных утверждения:

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

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

Наиболее простым датчиком псевдослучайных чисел является линейный конгруэнтный генератор (ЛКГ), который описывается рекуррентным уравнением вида X n = (aX n -1 +b ) mod N , где X 0 – случайное начальное значение, а – множитель, b – приращение, N – модуль.

Период выходной последовательности такого генератора не превышает N , максимальное значение достигается при правильном выборе параметров a,b, N , а именно, когда

· числа N и b взаимнопросты: НОД(N,b)=1 );

· a-1 кратно любому простому p , делящему N ;

· a-1 кратно 4 , если N кратно 4 .

В приведен список констант для ЛКГ, обеспечивающих максимальный период последовательности и, что не менее важно, соответствующие последовательности проходят статистические тесты.

Для реализации ЛКГ на персональных компьютерах с учетом их разрядной сетки нередко используется модуль N=2 31 -1»2.14×10 9 . При этом наиболее качественные статистические свойства ПСП достигаются для константы a=397204094.

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

Недостатком ЛКГ в плане их использования для создания поточных шифров является предсказуемость выходных последовательностей. Эффективные атаки на ЛКГ были предложены Joan Boyar , ей принадлежат методы атак на квадратичные ‑ X n =(aX n -1 2 +bX n -1 +c)modN и кубические ‑ X n =(aX n -1 3 +bX n -1 2 +cX n -1 +d)modN генераторы.

Другие исследователи обобщили результаты работ Boyar на случай общего полиномиального конгруэнтного генератора. Stern и Boyar показали, как взломать ЛКГ, даже если известна не вся последовательность.

Wishmann и Hill , а позже Pierre L’Ecuger изучили комбинации ЛКГ. Результаты не являются более стойкими криптографически, но имеют большие периоды и лучше ведут себя на некоторых критериях случайности.

Регистры сдвига с линейной обратной связью (Linear Feedback Shift Registers - LFSR ) включают собственно регистр сдвига и схему вычисления функции обратной связи (tap sequence ) – см. рис. 12:

Поток бит

n

∙∙∙

2

1

Рис. 2. Регистр сдвига с линейной обратной связью (LFSR )

На схеме содержимое регистра ‑ последовательность бит – сдвигается с приходом тактового импульса (clock pulse ) на один разряд вправо. Бит самого младшего разряда считается выходом LFSR в данном такте работы. Значение самого старшего разряда при этом является результатом сложения по mod2 (функция XOR) разрядов обратной связи.

Теоретически, n -битный LFSR может сгенерировать псевдослучайную последовательность с периодом 2 n -1 бит, такие LFSR называются регистрами максимального периода. Для этого регистр сдвига должен побывать во всех 2 n -1 внутренних состояниях (2 n -1 , т.к. нулевое заполнение регистр сдвига, вызовет бесконечную последовательность нулей).

Напомним, что полином называется неприводимым, если он не может быть выражен как произведение других полиномов меньшей степени отличных от 1 и самого себя.

Примитивный полином степени n – это неприводимый полином, который делит ,но не делит x d +1 для любого d : (2 n-1 │d)

Теорема (без доказательства): Для того, чтобы LFSR имел максимальный период, необходимо и достаточно, чтобы полином, образованный из элементов обратной связи (tap sequence ) плюс единица был примитивным полиномом по модулю 2. (на самом деле, примитивный полином – это генератор в данном поле).

Список практически применимых примитивных полиномов приведен в .

Например, примитивным полиномом является x 32 x 7 x 5 x 3 x 2 x1 . Запись (32,7,5,3,2,1,0 ) означает, что, взяв 32-битный регистр сдвига и генерируя бит обратной связи путем сложения по mod2 7-го, 5-го, 3-го, 2-го и 1-го бита, мы получим LFSR максимальной длины (с 2 32 -1 состояниями).

Заметим, если р(х) – примитивный полином, то x n ×p(1/x) – также примитивный.

Например, если полином (a,b,0) примитивный, то (a,a-b,0) – примитивный. Если полином (a,b,c,d,0) примитивный, то и (a,a-d,a-c,a-b,0) – примитивный и т.д.

Примитивные трехчлены особенно удобны, т.к. складываются только 2 бита регистра сдвига, но при этом они и более уязвимы к атакам.

LFSR – удобны для технической реализации, но имеют неприятные свойства. Последовательные биты линейно зависимы, что делает их бесполезными для шифрования. Даже если схема обратной связи неизвестна, то достаточно 2n выходных бит, чтобы определить ее.

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

Существует еще ряд генераторов ПСП (в т.ч. генераторы чисел Фибоначчи), которые по ряду причин не нашли широкого применения в криптографических системах. Наиболее эффективные решения были получены на основе составных генераторов.

Идея построения составного генератора базируется на том факте, что комбинация двух и более простых генераторов ПСП, в случае правильного выбора объединяющей функции (в т.ч. mod 2 , mod 2 32 -1 и др.), дает генератор с улучшенными свойствами случайности, и, как следствие, с повышенной криптографической стойкостью.

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

Известно 4 подхода к конструированию соответствующих генераторов:

1) системно-теоретический подход;

2) сложностно-теоретический подход;

3) информационно-теоретический подход;

4) рандомизированный подход.

Эти подходы различаются в своих предположениях о возможностях криптоаналитика, определении криптографического успеха и понятия надежности.

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

На основе такого подхода Рюппелем сформулирован следующий набор критериев для потоковых шифров:

1. Большой период выходной последовательности, отсутствие повторений;

2. Высокая линейная сложность, как характеристика нашего генератора через регистр LFSR минимальной длины, который может сгенерировать такой же выход;

3. Неотличимость от РРСП по статистическим критериям;

4. Перемешивание: любой бит ключевого потока должен быть сложным преобразованием всех или большинства бит начального состояния (ключа);

5. Рассеивание: избыточность во всех подструктурах алгоритма работы генератора должна рассеиваться;

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

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

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

Примером удачного построения составного генератора с точки зрения повышения линейной сложности является каскад Голмана (рис. 3).

Каскад Голмана включает несколько регистров LFSR , причем тактирование каждого следующего LSFR управляется предыдущим так, что изменение состояния LFSR -(k+1) в момент времени t происходит, если в предыдущем такте t-1 выход LFSR -k равняется 1, и LFSR -(k+1) не меняет свое состояние в противном случае.

Если все LFSR – длины l, то линейная сложность системы с n регистрами равна l ×(2 l -1) n-1 .

X(t)

LFSR-2

LFSR-3

Такт

Рис. 4. Чередующийся старт-стопный генератор

У этого генератора большой период и большая линейная сложность.

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

Однонаправленную функцию f (x ): D→R легко вычислить для всех x Î D , но очень трудно инвертировать для почти всех значений из R . Иначе, если V – вычислительная сложность получения f (x ), а V * – вычислительная сложность нахождения f -1 (x ), то имеет место неравенство V * >>V. Нетрудно видеть, что кандидатом на однонаправленную функцию может быть степенная функция в некотором конечном поле f (x )=a x , где a,xÎGF(q) – поле Галуа из q элементов.

Нетрудно видеть, что умножение, за счет свойства ассоциативности, можно выполнить за меньшее, чем число x-1 шагов. Например, a 9 =a×((a 2) 2) 2 , что позволяет вычислить искомую степень вместо восьми за четыре шага (вначале a 2 =a × a , затем a 4 =a 2 a 2 , a 8 =a 4 a 4 и, наконец, a 9 =a 8 a ).

Обратная операция – нахождение показателя степени по значению степенной функции (логарифмирование) ‑ в конечном поле пока не может быть решена лучше, чем с помощью оптимизированных методов перебора возможных вариантов. В случае большого размера поля (порядка 2 1024 )эта задача при современном развитии компьютерной техники вычислительно неразрешима.

Примером соответствующего генератора может алгоритм RSA . Пусть параметр N=p×q , где p,q – простые числа, начальное значение генератора x 0 N, e: НОД(e,(p-1)×(q-1) )=1.

x i+1 =x e i mod N

Результат генератора – наименьший значимый бит x i+1 . Стойкость этого генератора эквивалентна стойкости RSA . Если N достаточно большое, то генератор обеспечивает практическую стойкость.

Другой пример генератора, построенного на сложностном подходе, предложен Blum , Blum и Shub (BBS ). На данный момент это один из простых и эффективных алгоритмов. Математическая теория этого генератора – квадратичные вычеты по модулю n .

Выберем два больших простых числа p и q, дающих при делении на 4 остаток 3. Произведение n p q назовем числом Блюма. Выберем х : НОД(n,x )=1. Найдем начальное значение генератора: x 0 =x 2 mod n .

Теперь i -ым псевдослучайным числом является наименьший значимый бит x i , где x i =x 2 i -2 mod n .

Заметим, что для получения i- го бита, не требуется вычисления (i-1 ) состояния. Если мы знаем p,q, то мы можем его вычислить сразу: b i есть наименьшее значение бит:

Это свойство позволяет использовать BBS- генератор для работы с файлами произвольного доступа (random-access ).

Число n можно распространять свободно, для того чтобы каждый абонент сети смог самостоятельно сгенерировать необходимые биты. При этом если криптоаналитик не сможет разложить на простые множители число n , он не сможет предсказать следующий бит, даже в вероятностном смысле, например, «с вероятностью 51% следующий бит равен 1».

Отметим; что генераторы, построенные на однонаправленных функциях, очень медленные, для их практической реализации необходимы специальные процессоры.

Следующие два подхода информационно-теоретический и рандомизированный не нашли широкого практического применения.

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

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

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

Ueli Maurer описал такую схему. Вероятность вскрытия такой криптосистемы зависит от объема памяти, доступного криптоаналитику (но не зависит от его вычислительных ресурсов).

Чтобы эта схема приобрела практический вид, требуется около 100 битовых последовательностей по 10 20 бит каждая. Оцифровка поверхности Луны – один из способов получения такого количества бит.

В заключение отметим, что для построения генератора ПСП необходимо получить несколько случайных бит . Наиболее простой способ ‑ использовать наименьший значимый бит таймера компьютера.

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

Самый лучший способ получить случайное число – это обратиться к естественной случайности реального мира – шумы в результате переходных процессов в полупроводниковых диодах, тепловые шумы высокомных резисторов, радиоактивный распад и т.д. В принципе, элемент случайности есть и в компьютерах:

Время дня;

Загруженность процессора;

Время прибытия сетевых пакетов и т.п.

Проблема не в том, чтобы найти источники случайности, но в том, чтобы сохранить случайность при измерениях.

Например, это можно делать так: найдем событие, случающееся регулярно, но случайно (шум превышает некоторый порог). Измерим время между первым событием и вторым, затем между вторым и третьим. Если t 1,2 t 2,3 , то полагаем выход генератора равным 1; если t 1,2 < t 2,3 , то выход равен 0. Далее процесс продолжим.

Американский национальный институт стандартов (ANSI) разработал метод генерации 64-битных ключей при помощи DES-алгоритма (ANSI X9.17). Его основное назначение состоит в получении большого количества ключей для многократных сеансов связи. Вместо DES-алгоритма можно использовать любой другой стойкий алгоритм шифрования.

Пусть функция Е K (Р) осуществляет шифрование Р по DES-алгоритму на заранее заготовленном ключе К, который используется только для генерации секретных ключей. Пусть далее V 0 является начальным 64-битным значением, которое держится в тайне от противника, а Т i представляет собой отметку даты-времени, когда был сгенерирован i-й ключ. Тогда очередной случайный ключ R i вычисляется с помощью преобразования:

R i = Е К (Е К (Т i) Å V i)

Чтобы получить очередное значение V i , надо вычислить

V i = Е К (Е К (Т i) Å R i)

Существенной проблемой систем генерации случайных данных является наличие отклонений и корреляций в сгенерированной последовательности. Сами процессы могут быть случайными, но проблемы могут возникнуть в процессе измерений. Как с этим бороться?

1) Сложением по mod 2 двух независимых последовательностей:если случайный бит смещен к 0 на величину ε , то вероятность появления 0 может быть записана как P(0)=0.5+ε .

Сложение по mod 2: двух одинаково распределенных независимых бит даст: P(0) =(0.5 +ε) 2 +(0.5-ε) 2 =0.5 +2×ε 2 , сложением четырех бит получим: P (0)=0.5+8 ε 4 и т.д. Процесс сходится к равновероятному распределению 0 и 1.

2) Пусть распределение единиц и нулей в последовательности есть величины p и q соответственно. Воспользуемся методом кодирования: рассмотрим два бита:

Если это одинаковые биты, то отбросим их и рассмотрим следующую пару;

Если биты различны, то в качестве выходного значения возьмем первый бит.

Данный метод позволяет решить проблему смещения, сохранив свойства случайности источника (с некоторой потерей в объеме данных).

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

Факт наличия смещения у генератора случайных чисел, вообще говоря, не означает его непригодность. Например, пусть для генерации 112-битного ключа для алгоритма «тройной» DES (Triple DES ) используется генератор со смещением к нулю: P{x t =0}=0.55, Р{x t =1}=0.45 (энтропия Н= 0.99277 на один бит ключа по сравнению с 1 для идеального генератора).

В этом случае нарушитель может оптимизировать процедуру тотального перебора ключей за счет поиска ключа начиная с наиболее вероятного значения (00…0 ) и заканчивая наименее вероятным (11…1 ). Вследствие наличия смещения, можно ожидать нахождения ключа в среднем за 2 109 попыток. Если бы смещения не было, то потребовалось бы 2 111 попыток. Выигрыш есть, но несущественный.

Заметим, что в идеале кривая плотности распределения случайных чисел выглядела бы так, как показано на рис. 22.3 . То есть в идеальном случае в каждый интервал попадает одинаковое число точек: N i = N /k , где N — общее число точек, k — количество интервалов, i = 1, …, k .

Рис. 22.3. Частотная диаграмма выпадения случайных чисел,
порождаемых идеальным генератором теоретически

Следует помнить, что генерация произвольного случайного числа состоит из двух этапов:

• генерация нормализованного случайного числа (то есть равномерно распределенного от 0 до 1);
• преобразование нормализованных случайных чисел r i в случайные числа x i , которые распределены по необходимому пользователю (произвольному) закону распределения или в необходимом интервале.

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

• физические;
• табличные;
• алгоритмические.

Физические ГСЧ

Примером физических ГСЧ могут служить: монета («орел» — 1, «решка» — 0); игральные кости; поделенный на секторы с цифрами барабан со стрелкой; аппаратурный генератор шума (ГШ), в качестве которого используют шумящее тепловое устройство, например, транзистор (рис. 22.4–22.5 ).

Рис. 22.4. Схема аппаратного метода генерации случайных чисел
Рис. 22.5. Диаграмма получения случайных чисел аппаратным методом

Задача «Генерация случайных чисел при помощи монеты»

Сгенерируйте случайное трехразрядное число, распределенное по равномерному закону в интервале от 0 до 1, с помощью монеты. Точность — три знака после запятой.

Первый способ решения задачи Подбросьте монету 9 раз, и если монета упала решкой, то запишите «0», если орлом, то «1». Итак, допустим, что в результате эксперимента получили случайную последовательность 100110100. Начертите интервал от 0 до 1. Считывая числа в последовательности слева направо, разбивайте интервал пополам и выбирайте каждый раз одну из частей очередного интервала (если выпал 0, то левую, если выпала 1, то правую). Таким образом, можно добраться до любой точки интервала, сколь угодно точно. Итак, 1 : интервал делится пополам — и , — выбирается правая половина, интервал сужается: . Следующее число, 0 : интервал делится пополам — и , — выбирается левая половина , интервал сужается: . Следующее число, 0 : интервал делится пополам — и , — выбирается левая половина , интервал сужается: . Следующее число, 1 : интервал делится пополам — и , — выбирается правая половина , интервал сужается: . По условию точности задачи решение найдено: им является любое число из интервала , например, 0.625. В принципе, если подходить строго, то деление интервалов нужно продолжить до тех пор, пока левая и правая границы найденного интервала не СОВПАДУТ между собой с точностью до третьего знака после запятой. То есть с позиций точности сгенерированное число уже не будет отличимо от любого числа из интервала, в котором оно находится. Второй способ решения задачи Разобьем полученную двоичную последовательность 100110100 на триады: 100, 110, 100. После перевода этих двоичных чисел в десятичные получаем: 4, 6, 4. Подставив спереди «0.», получим: 0.464. Таким методом могут получаться только числа от 0.000 до 0.777 (так как максимум, что можно «выжать» из трех двоичных разрядов — это 111 2 = 7 8) — то есть, по сути, эти числа представлены в восьмеричной системе счисления. Для перевода восьмеричного числа в десятичное представление выполним: 0.464 8 = 4 · 8 –1 + 6 · 8 –2 + 4 · 8 –3 = 0.6015625 10 = 0.602 10 . Итак, искомое число равно: 0.602.

Табличные ГСЧ

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

Таблица 22.1. Случайные цифры. Равномерно распределенные от 0 до 1 случайные числа

Случайные цифры								Равномерно распределенные от 0 до 1 случайные числа
9	2	9	2	0	4	2	6	0.929
9	5	7	3	4	9	0	3	0.204
5	9	1	6	6	5	7	6	0.269

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

Находится таблица, содержащая 500 абсолютно случайных проверенных чисел (взято из книги И. Г. Венецкого, В. И. Венецкой «Основные математико-статистические понятия и формулы в экономическом анализе»).

Алгоритмические ГСЧ

Числа, генерируемые с помощью этих ГСЧ, всегда являются псевдослучайными (или квазислучайными), то есть каждое последующее сгенерированное число зависит от предыдущего:

r i + 1 = f (r i ) .

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

Достоинством данных ГСЧ является быстродействие; генераторы практически не требуют ресурсов памяти, компактны. Недостатки: числа нельзя в полной мере назвать случайными, поскольку между ними имеется зависимость, а также наличие периодов в последовательности квазислучайных чисел.

Рассмотрим несколько алгоритмических методов получения ГСЧ:

• метод серединных квадратов;
• метод серединных произведений;
• метод перемешивания;
• линейный конгруэнтный метод.

Метод серединных квадратов

Имеется некоторое четырехзначное число R 0 . Это число возводится в квадрат и заносится в R 1 . Далее из R 1 берется середина (четыре средних цифры) — новое случайное число — и записывается в R 0 . Затем процедура повторяется (см. рис. 22.6 ). Отметим, что на самом деле в качестве случайного числа необходимо брать не ghij , а 0.ghij — с приписанным слева нулем и десятичной точкой. Этот факт отражен как на рис. 22.6 , так и на последующих подобных рисунках.

Рис. 22.6. Схема метода серединных квадратов

Недостатки метода: 1) если на некоторой итерации число R 0 станет равным нулю, то генератор вырождается, поэтому важен правильный выбор начального значения R 0 ; 2) генератор будет повторять последовательность через M n шагов (в лучшем случае), где n — разрядность числа R 0 , M — основание системы счисления.

Для примера на рис. 22.6 : если число R 0 будет представлено в двоичной системе счисления, то последовательность псевдослучайных чисел повторится через 2 4 = 16 шагов. Заметим, что повторение последовательности может произойти и раньше, если начальное число будет выбрано неудачно.

Описанный выше способ был предложен Джоном фон Нейманом и относится к 1946 году. Поскольку этот способ оказался ненадежным, от него очень быстро отказались.

Метод серединных произведений

Число R 0 умножается на R 1 , из полученного результата R 2 извлекается середина R 2 * (это очередное случайное число) и умножается на R 1 . По этой схеме вычисляются все последующие случайные числа (см. рис. 22.7 ).

Рис. 22.7. Схема метода серединных произведений

Метод перемешивания

В методе перемешивания используются операции циклического сдвига содержимого ячейки влево и вправо. Идея метода состоит в следующем. Пусть в ячейке хранится начальное число R 0 . Циклически сдвигая содержимое ячейки влево на 1/4 длины ячейки, получаем новое число R 0 * . Точно так же, циклически сдвигая содержимое ячейки R 0 вправо на 1/4 длины ячейки, получаем второе число R 0 ** . Сумма чисел R 0 * и R 0 ** дает новое случайное число R 1 . Далее R 1 заносится в R 0 , и вся последовательность операций повторяется (см. рис. 22.8 ).

Рис. 22.8. Схема метода перемешивания

Обратите внимание, что число, полученное в результате суммирования R 0 * и R 0 ** , может не уместиться полностью в ячейке R 1 . В этом случае от полученного числа должны быть отброшены лишние разряды. Поясним это для рис. 22.8 , где все ячейки представлены восемью двоичными разрядами. Пусть R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , тогда R 0 * + R 0 ** = 100110010 2 = 306 10 . Как видим, число 306 занимает 9 разрядов (в двоичной системе счисления), а ячейка R 1 (как и R 0 ) может вместить в себя максимум 8 разрядов. Поэтому перед занесением значения в R 1 необходимо убрать один «лишний», крайний левый бит из числа 306, в результате чего в R 1 пойдет уже не 306, а 00110010 2 = 50 10 . Также заметим, что в таких языках, как Паскаль, «урезание» лишних битов при переполнении ячейки производится автоматически в соответствии с заданным типом переменной.

Линейный конгруэнтный метод

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

r i + 1 = mod(k · r i + b , M ) .

Последовательность случайных чисел, полученных с помощью данной формулы, называется линейной конгруэнтной последовательностью . Многие авторы называют линейную конгруэнтную последовательность при b = 0 мультипликативным конгруэнтным методом , а при b ≠ 0 — смешанным конгруэнтным методом .

Для качественного генератора требуется подобрать подходящие коэффициенты. Необходимо, чтобы число M было довольно большим, так как период не может иметь больше M элементов. С другой стороны, деление, использующееся в этом методе, является довольно медленной операцией, поэтому для двоичной вычислительной машины логичным будет выбор M = 2 N , поскольку в этом случае нахождение остатка от деления сводится внутри ЭВМ к двоичной логической операции «AND». Также широко распространен выбор наибольшего простого числа M , меньшего, чем 2 N : в специальной литературе доказывается, что в этом случае младшие разряды получаемого случайного числа r i + 1 ведут себя так же случайно, как и старшие, что положительно сказывается на всей последовательности случайных чисел в целом. В качестве примера можно привести одно из чисел Мерсенна , равное 2 31 – 1 , и таким образом, M = 2 31 – 1 .

Одним из требований к линейным конгруэнтным последовательностям является как можно большая длина периода. Длина периода зависит от значений M , k и b . Теорема, которую мы приведем ниже, позволяет определить, возможно ли достижение периода максимальной длины для конкретных значений M , k и b .

Теорема . Линейная конгруэнтная последовательность, определенная числами M , k , b и r 0 , имеет период длиной M тогда и только тогда, когда:

• числа b и M взаимно простые;
• k – 1 кратно p для каждого простого p , являющегося делителем M ;
• k – 1 кратно 4, если M кратно 4.

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

Было установлено, что ряд псевдослучайных чисел, генерируемых на основе данных из примера 1, будет повторяться через каждые M /4 чисел. Число q задается произвольно перед началом вычислений, однако при этом следует иметь в виду, что ряд производит впечатление случайного при больших k (а значит, и q ). Результат можно несколько улучшить, если b нечетно и k = 1 + 4 · q — в этом случае ряд будет повторяться через каждые M чисел. После долгих поисков k исследователи остановились на значениях 69069 и 71365 .

Генератор случайных чисел, использующий данные из примера 2, будет выдавать случайные неповторяющиеся числа с периодом, равным 7 миллионам.

Мультипликативный метод генерации псевдослучайных чисел был предложен Д. Г. Лехмером (D. H. Lehmer) в 1949 году.

Проверка качества работы генератора

От качества работы ГСЧ зависит качество работы всей системы и точность результатов. Поэтому случайная последовательность, порождаемая ГСЧ, должна удовлетворять целому ряду критериев.

Осуществляемые проверки бывают двух типов:

• проверки на равномерность распределения;
• проверки на статистическую независимость.

Проверки на равномерность распределения

1) ГСЧ должен выдавать близкие к следующим значения статистических параметров, характерных для равномерного случайного закона:

2) Частотный тест

Частотный тест позволяет выяснить, сколько чисел попало в интервал (m r – σ r ; m r + σ r ) , то есть (0.5 – 0.2887; 0.5 + 0.2887) или, в конечном итоге, (0.2113; 0.7887) . Так как 0.7887 – 0.2113 = 0.5774 , заключаем, что в хорошем ГСЧ в этот интервал должно попадать около 57.7% из всех выпавших случайных чисел (см. рис. 22.9 ).

Рис. 22.9. Частотная диаграмма идеального ГСЧ
в случае проверки его на частотный тест

Также необходимо учитывать, что количество чисел, попавших в интервал (0; 0.5) , должно быть примерно равно количеству чисел, попавших в интервал (0.5; 1) .

3) Проверка по критерию «хи-квадрат»

Критерий «хи-квадрат» (χ 2 -критерий) — это один из самых известных статистических критериев; он является основным методом, используемым в сочетании с другими критериями. Критерий «хи-квадрат» был предложен в 1900 году Карлом Пирсоном. Его замечательная работа рассматривается как фундамент современной математической статистики.

Для нашего случая проверка по критерию «хи-квадрат» позволит узнать, насколько созданный нами реальный ГСЧ близок к эталону ГСЧ , то есть удовлетворяет ли он требованию равномерного распределения или нет.

Частотная диаграмма эталонного ГСЧ представлена на рис. 22.10 . Так как закон распределения эталонного ГСЧ равномерный, то (теоретическая) вероятность p i попадания чисел в i -ый интервал (всего этих интервалов k ) равна p i = 1/k . И, таким образом, в каждый из k интервалов попадет ровно по p i · N чисел (N — общее количество сгенерированных чисел).

Рис. 22.10. Частотная диаграмма эталонного ГСЧ

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет по n i чисел (в сумме n 1 + n 2 + … + n k = N ). Как же нам определить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел n i и «эталонным» p i · N . Сложим их, и в результате получим:

χ 2 эксп. = (n 1 – p 1 · N ) 2 + (n 2 – p 2 · N ) 2 + … + (n k – p k · N ) 2 .

Из этой формулы следует, что чем меньше разность в каждом из слагаемых (а значит, и чем меньше значение χ 2 эксп. ), тем сильнее закон распределения случайных чисел, генерируемых реальным ГСЧ, тяготеет к равномерному.

В предыдущем выражении каждому из слагаемых приписывается одинаковый вес (равный 1), что на самом деле может не соответствовать действительности; поэтому для статистики «хи-квадрат» необходимо провести нормировку каждого i -го слагаемого, поделив его на p i · N :

Наконец, запишем полученное выражение более компактно и упростим его:

Мы получили значение критерия «хи-квадрат» для экспериментальных данных.

В табл. 22.2 приведены теоретические значения «хи-квадрат» (χ 2 теор. ), где ν = N – 1 — это число степеней свободы, p — это доверительная вероятность, задаваемая пользователем, который указывает, насколько ГСЧ должен удовлетворять требованиям равномерного распределения, или p — это вероятность того, что экспериментальное значение χ 2 эксп. будет меньше табулированного (теоретического) χ 2 теор. или равно ему .

Таблица 22.2. Некоторые процентные точки χ 2 -распределения

	p = 1%	p = 5%	p = 25%	p = 50%	p = 75%	p = 95%	p = 99%
ν = 1	0.00016	0.00393	0.1015	0.4549	1.323	3.841	6.635
ν = 2	0.02010	0.1026	0.5754	1.386	2.773	5.991	9.210
ν = 3	0.1148	0.3518	1.213	2.366	4.108	7.815	11.34
ν = 4	0.2971	0.7107	1.923	3.357	5.385	9.488	13.28
ν = 5	0.5543	1.1455	2.675	4.351	6.626	11.07	15.09
ν = 6	0.8721	1.635	3.455	5.348	7.841	12.59	16.81
ν = 7	1.239	2.167	4.255	6.346	9.037	14.07	18.48
ν = 8	1.646	2.733	5.071	7.344	10.22	15.51	20.09
ν = 9	2.088	3.325	5.899	8.343	11.39	16.92	21.67
ν = 10	2.558	3.940	6.737	9.342	12.55	18.31	23.21
ν = 11	3.053	4.575	7.584	10.34	13.70	19.68	24.72
ν = 12	3.571	5.226	8.438	11.34	14.85	21.03	26.22
ν = 15	5.229	7.261	11.04	14.34	18.25	25.00	30.58
ν = 20	8.260	10.85	15.45	19.34	23.83	31.41	37.57
ν = 30	14.95	18.49	24.48	29.34	34.80	43.77	50.89
ν = 50	29.71	34.76	42.94	49.33	56.33	67.50	76.15
ν > 30	ν + sqrt(2ν ) · x p + 2/3 · x 2 p – 2/3 + O (1/sqrt(ν ))
x p =	–2.33	–1.64	–0.674	0.00	0.674	1.64	2.33

Приемлемым считают p от 10% до 90% .

Если χ 2 эксп. много больше χ 2 теор. (то есть p — велико), то генератор не удовлетворяет требованию равномерного распределения, так как наблюдаемые значения n i слишком далеко уходят от теоретических p i · N и не могут рассматриваться как случайные. Другими словами, устанавливается такой большой доверительный интервал, что ограничения на числа становятся очень нежесткими, требования к числам — слабыми. При этом будет наблюдаться очень большая абсолютная погрешность.

Еще Д. Кнут в своей книге «Искусство программирования» заметил, что иметь χ 2 эксп. маленьким тоже, в общем-то, нехорошо, хотя это и кажется, на первый взгляд, замечательно с точки зрения равномерности. Действительно, возьмите ряд чисел 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, … — они идеальны с точки зрения равномерности, и χ 2 эксп. будет практически нулевым, но вряд ли вы их признаете случайными.

Если χ 2 эксп. много меньше χ 2 теор. (то есть p — мало), то генератор не удовлетворяет требованию случайного равномерного распределения, так как наблюдаемые значения n i слишком близки к теоретическим p i · N и не могут рассматриваться как случайные.

А вот если χ 2 эксп. лежит в некотором диапазоне, между двумя значениями χ 2 теор. , которые соответствуют, например, p = 25% и p = 50%, то можно считать, что значения случайных чисел, порождаемые датчиком, вполне являются случайными.

При этом дополнительно надо иметь в виду, что все значения p i · N должны быть достаточно большими, например больше 5 (выяснено эмпирическим путем). Только тогда (при достаточно большой статистической выборке) условия проведения эксперимента можно считать удовлетворительными.

Итак, процедура проверки имеет следующий вид.

Проверки на статистическую независимость

1) Проверка на частоту появления цифры в последовательности

Рассмотрим пример. Случайное число 0.2463389991 состоит из цифр 2463389991, а число 0.5467766618 состоит из цифр 5467766618. Соединяя последовательности цифр, имеем: 24633899915467766618.

Понятно, что теоретическая вероятность p i выпадения i -ой цифры (от 0 до 9) равна 0.1.

2) Проверка появления серий из одинаковых цифр

Обозначим через n L число серий одинаковых подряд цифр длины L . Проверять надо все L от 1 до m , где m — это заданное пользователем число: максимально встречающееся число одинаковых цифр в серии.

В примере «24633899915467766618» обнаружены 2 серии длиной в 2 (33 и 77), то есть n 2 = 2 и 2 серии длиной в 3 (999 и 666), то есть n 3 = 2 .

Вероятность появления серии длиной в L равна: p L = 9 · 10 –L (теоретическая). То есть вероятность появления серии длиной в один символ равна: p 1 = 0.9 (теоретическая). Вероятность появления серии длиной в два символа равна: p 2 = 0.09 (теоретическая). Вероятность появления серии длиной в три символа равна: p 3 = 0.009 (теоретическая).

Например, вероятность появления серии длиной в один символ равна p L = 0.9 , так как всего может встретиться один символ из 10, а всего символов 9 (ноль не считается). А вероятность того, что подряд встретится два одинаковых символа «XX» равна 0.1 · 0.1 · 9, то есть вероятность 0.1 того, что в первой позиции появится символ «X», умножается на вероятность 0.1 того, что во второй позиции появится такой же символ «X» и умножается на количество таких комбинаций 9.

Частость появления серий подсчитывается по ранее разобранной нами формуле «хи-квадрат» с использованием значений p L .

Примечание: генератор может быть проверен многократно, однако проверки не обладают свойством полноты и не гарантируют, что генератор выдает случайные числа. Например, генератор, выдающий последовательность 12345678912345…, при проверках будет считаться идеальным, что, очевидно, не совсем так.

В заключение отметим, что третья глава книги Дональда Э. Кнута «Искусство программирования» (том 2) полностью посвящена изучению случайных чисел. В ней изучаются различные методы генерирования случайных чисел, статистические критерии случайности, а также преобразование равномерно распределенных случайных чисел в другие типы случайных величин. Изложению этого материала уделено более двухсот страниц.