Оглавление
1 Введение. 3
2 Генератор псевдослучайных чисел. 4
3 Методы получение псевдослучайных чисел. 6
3.1 Линейный конгруэнтный метод. 7
3.2 Метод Фибоначчи. 8
3.3 Линейный регистр сдвига с обратной связью… 10
3.4 Вихрь Мерсенна. 11
4 Тестирование псевдослучайных последовательностей. 12
4.1 Графические тесты… 12
4.2 Статистические тесты… 13
4.2.1 Основные принципы… 14
4.2.2 Тесты Д. Кнута. 14
4.2.3 Пакет статистических тестов NIST. 15
4.2.4 Тесты Diehard. 22
5 Вывод. 24
6 Список используемой литературы… 25
Приложение А… Ошибка! Закладка не определена.
1 Введение
Генерирование случайных последовательностей с заданным вероятностным законом и проверка их адекватности — одни из важнейших проблем современной криптологии. Генераторы случайных последовательностей используются в существующих криптосистемах для генерации ключевой информации и задания ряда параметров криптосистем. Научная и практическая значимость этой проблемы настолько велика, что ей посвящены отдельные монографии в области криптологии, организуются разделы в научных журналах "JournalofCryptology", "Cryptologia" и специальные заседания на международных научных конференциях "Eurocrypt", "Asiacrypt", "Crypto" и др.
В начале XX века случайные последовательности имитировались с помощью простейших случайных экспериментов: бросание монеты или игральной кости, извлечение шаров из урны, раскладывание карт, рулетка и т. д. В 1927 г. Л. Типпетом впервые были опубликованы таблицы, содержащие свыше 40000 случайных цифр, «произвольно извлечённых из отчётов о переписи населения». В 1939 г. с помощью специально сконструированного механического устройства — генератора случайных чисел, М. Дж. Кендалл и Б. Бэбингтон-Смит создали таблицу, включающую 105 случайных цифр. В 1946 г. американский математик Джон фон Нейман впервые предложил компьютерный алгоритм генерации случайных чисел. В 1955 г. компания RANDCorporationопубликовала получившие широкую популярность таблицы, содержащие 106 случайных цифр, сгенерированных на ЭВМ.
В настоящее время спрос на генераторы случайных последовательностей с заданными вероятностными распределениями, а также на сами случайные последовательности настолько возрос, что за рубежом появились научно-производственные фирмы, занимающиеся производством и продажей больших массивов случайных чисел. Например, с 1996 г. в мире распространяется компакт-диск "TheMarsagliarandomnumberCDROM", который содержит 4,8 млрд. «истинно случайных» бит.
Подавляющее большинство современных криптографических систем используют либо поточные, либо блочные алгоритмы, базирующиеся на различных типах шифрах замены и перестановки. К сожалению, практически все алгоритмы, используемые в поточных криптосистемах, ориентированных на использование в военных и правительственных системах связи, а также, в некоторых случаях, для защиты информации коммерческого характера, что вполне естественно делает их секретными и недоступными для ознакомления. Единственными стандартными алгоритмами поточного симметричного шифрования являются американский стандарт DES (режимы CFB и OFB) и российский стандарт ГОСТ 28147-89 (режим гаммирования).
Основу функционирования поточных криптосистем составляют генераторы случайных или псевдослучайных последовательностей. Рассмотрим этот вопрос более подробно. 2 Генератор псевдослучайных чисел
Секретные ключи представляют собой основу криптографических преобразований, для которых согласно правилу Керкгоффса[1], стойкость криптосистемы определяется лишь секретностью ключа. Основной проблемой классической криптографии долгое время являлась трудность генерации секретного ключа. Физическое моделирование случайности с помощью таких физических явлений как, например, радиоактивное излучение или дробовой шум в электронной лампе является довольно сложным и дорогостоящим, а использование нажатия клавиш и движение мыши требует усилий пользователя и к тому же не дают полностью настоящих случайных процессов. Поэтому вместо физического моделирования используют методы математического моделирования случайности и генерации случайных последовательностей в виде программ для ЭВМ или специализированных устройств.
Эти программы и устройства хотя и называются генераторами случайных чисел, на самом деле генерируют детерминированные последовательности, которые только кажутся случайными по своим свойствам и поэтому называются псевдослучайными последовательностями. От них требуется, чтобы, даже зная закон формирования, но, не зная ключа в виде заданных начальных условий, никто не смог бы отличить генерируемую последовательность от случайной, как будто она получена путем бросания идеальных игровых костей.
Генератор псевдослучайных чисел(ГПСЧ, англ. Pseudorandom number generator, PRNG) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).
Можно сформировать три основных требования, которым должны удовлетворять криптографическистойкие генераторы псевдослучайных последовательностей или гаммы.
1. Период гаммы должен быть достаточно большим для шифрования сообщений различной длины.
2. Гамма должна быть трудно предсказуемой. Это значит, что если известны тип генератора и кусок гаммы, то невозможно предсказать следующий за этим куском бит гаммы или предшествующий этому куску бит гаммы.
3. Генерирование гаммы не должно быть связано с большими техническими и организационными трудностями.
Самая важная характеристика генератора псевдослучайных чисел — это информационная длина его периода, после которого числа будут либо просто повторяться, либо их можно будет предсказать. Эта длина практически определяет возможное число ключей криптосистемы. Чем эта длина больше, тем сложнее подобрать ключ.
Второе из указанных выше требований связано со следующей проблемой: на основании чего можно сделать заключение, что гамма конкретного генератора действительно является непредсказуемой? Пока в мире нет универсальных и практически проверяемых критериев для проверки этого свойства. Интуитивно случайность воспринимается как непредсказуемость. Чтобы гамма считалась случайной и непредсказуемой как минимум необходимо, чтобы ее период был очень большим, а различные комбинации бит определенной длины равномерно распределялись по всей ее длине. Это требование статистически можно толковать и как сложность закона генерации псевдослучайной последовательности чисел. Если по достаточно длинному отрезку этой последовательности нельзя ни статистически, ни аналитически определить этот закон генерации, то в принципе этим можно удовлетвориться.
И, наконец, третье требование должно гарантировать возможность практической реализации генераторов псевдослучайных последовательностей с учетом требуемого быстродействия и удобства практичного использования. Рассмотрим теперь некоторые практические методы получения псевдослучайных чисел. 3 Методы получение псевдослучайных чисел
Одним из первых таких методов был метод, предложенный в 1946 году Д. фон Нейманом. Этот метод базировался на том, что каждое последующее число в псевдослучайной последовательности формировалось возведением предыдущего числа в квадрат и отбрасыванием цифр с обоих концов. Однако этот метод оказался ненадежным, и от него быстро отказались. Другим методом является так называемый конгруэнтный способ. 3.1 Линейный конгруэнтный метод
Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.
Этот алгоритм заключается в итеративном применении следующей формулы:
, (1)
где a>0, c>0, m>0 — некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X0 и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности Xj определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим 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).
Наибольшую популярность фибоначчиевы датчики получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а фибоначчиевы датчики естественно реализуются в вещественной арифметике.
Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:
(2)
где Xk — вещественные числа из диапазона [0,1), a,b — целые положительные числа, называемые лагами. Для работы фибоначчиеву датчику требуется знать max{a,b} предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max{a,b} случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.
Лаги a и b — «магические» и их не следует выбирать произвольно. Рекомендуются следующие значения лагов: (a, b)=(55,24), (17,5) или (97,33). Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.
Значения (a,b) = (17,5) можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения (a,b) = (55,24) позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения (a,b) = (97,33) позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Описанный фибоначчиев датчик случайных чисел (с лагами 20 и 5) используется в широко известной системе Matlab.
Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам. Период фибоначчиева датчика может быть оценен по следующей формуле:
,
где — число битов в мантиссе вещественного числа.3.3 Линейный регистр сдвига с обратной связью
Сдвиговый регистр с обратной связью (LFSR — Linear feedback shift register состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр — последовательность битов. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на одну позицию. Новый крайний слева бит определяется функцией остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший, значащий бит. Период сдвигового регистра — длина получаемой последовательности до начала ее повторения.
Для LFSR функция обратной связи представляет собой сумму по модулю 2 (xor) некоторых битов регистра (эти биты называются отводной последовательностью).
LFSR может находиться в 2n − 1 внутренних состояниях, где n — длина сдвигового регистра. Если сдвиговый регистр заполнен нулями, то такое состояние будет порождать на выходе только нули (так как в качестве функции обратной связи используется xor), поэтому такое состояние бесполезно. Теоретически LFSR может генерировать последовательность с длиной 2n − 1 бит, так как длина последовательности совпадает с количеством внутренних состояний. LFSR будет проходить все внутренние состояния (иметь максимальный период) только при определённых отводных последовательностях — если многочлен, образованный из отводной последовательности и константы 1, является примитивным по модулю 2.
Степень многочлена — длина сдвигового регистра. Примитивный многочлен степени n — это неприводимый многочлен, который является делителем , но не является делителем xd + 1 для всех d, делящих 2n − 1.
Например, чтобы проверить будет ли LFSR с отводной последовательностью, состоящей из первого и четвертого битов, генерировать последовательность максимальной длины (15 для 4-битного регистра), нужно проверить, будет ли многочлен x4 + x + 1 примитивным.3.4 Вихрь Мерсенна
Вихрь Мерсенна (Mersenne twister) — это генератор псевдослучайных чисел, основываный на свойствах простых чисел Мерсенна и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков присущих другим ГПСЧ таких как малый период, предсказуемость, легко выявляемая статистическая зависимость. Тем не менее этот генератор не является криптостойким, что ограничивает его использование в криптографии.
Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register, TGFSR). «Вихрь» — это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5-ю измерениями). Поэтому корреляция между последовательными значениями в выходной последовательности Вихря Мерсенна пренебрежимо мала.
Вихрь Мерсенна имеет огромный период, а именно, доказано, что его период равен числу Мерсенна 219937−1, что более чем достаточно для многих практических приложений.
Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2-3 раза быстрее линейных конгруэнтных генераторов). Вихрь Мерсенна реализован в библиотеке gLib и стандартных библиотеках для PHP, Python и Руби.
Алгоритм основан на следующем рекуррентном выражении:
где n — целое, которое обозначает степень рекуррентности,
m — целое, 1
А — матрица размера WxW, с элементами из F2.
В правой части обозначает «старшие w-r бит» , и , «младшие r бит» Хк+1. 4 Тестирование псевдослучайных последовательностей
Псевдослучайные последовательности, порождаемые любым генератором для криптографических целей, подлежат обязательному тестированию.
Тестирование псевдослучайных последовательностей — совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т. п.
Существует несколько методов тестирования ПСП:
Ø Графический тест
Ø Статистический
4.1 Графические тесты
К этой категории относятся тесты, результаты которых отображаются в виде графиков, характеризующих свойства исследуемой последовательности. Среди них:
1. гистограмма распределения элементов последовательности(позволяет оценить равномерность распределения символов в последовательности и определить частоту повторения каждого символа);
2. распределение на плоскости(предназначено для определения зависимости между элементами последовательности);
3. проверка серий(позволяет определить равномерность отдельных символов в последовательности, а так же равномерность распределения серий из k бит);
4. проверка на монотонность(служит для определения равномерности исходя из анализа невозрастающих и неубывающих подпоследовательностей);
5. автокорреляционная функция(предназначена для оценки корреляции между сдвинутыми копиями последовательностей и отдельных подпоследовательностей);
6. профиль линейной сложности(тест оценивает зависимость линейной сложности последовательности от ее длины);
7. графический спектральный тест(позволяет оценить равномерность распределения бит последовательности на основании анализа высоты выбросов преобразования Фурье).
Результаты графических тестов интерпретируются человеком, поэтому на их основе выводы могут быть неоднозначными.
4.2 Статистические тесты
В отличие от графических тестов, статистические тесты выдают численную характеристику последовательности и позволяют однозначно сказать, пройден ли тест. Наиболее известные тесты:
§ Подборка статистических тестов Д. Кнута;
§ DIEHARD;
§ CRYPT-X;
§ NIST STS;4.2.1 Основные принципы
Зная вероятностные свойства истинно случайной последовательности, можно на их основе проверять гипотезу о том, на сколько сгенерированная последовательность похожа на случайную. Для этого для каждого теста подбирается подходящая статистика, вычисляется её значения для идеальной и сгенерированной последовательности. Если разность этих значений превышает некоторое критическое значение, установленное заранее, то последовательность считается неслучайной. Для „хороших“ последовательностей вероятность такого события крайне мала(допустим ~0,001 и обозначим её α). Однако, существует вероятность того, что „плохая“ последовательность удовлетворит критерию и будет сделан вывод о ее случайности(обозначим вероятность такого события β). На практике значения длины последовательности n, α и β связаны, задается α и подбирается n такое, чтобы минимизировать β.
Определим величину P-value как вероятность того, что идеальный генератор сгенерировал последовательность менее случайную, чем исследуемый. Тогда если P-value больше α, то исследуемая последовательность считается случайной и наоборот в противном случае.
Кратко шаги статистического тестирования можно изобразить в виде таблицы:4.2.2 Тесты Д. Кнута
Тесты Кнута основаны на статистическом критерии χ2[2]. Вычисляемое значение статистики χ2 сравнивается с табличными результатами, и в зависимости от вероятности появления такой статистики делается вывод о ее качестве. Среди достоинств этих тестов — небольшое их количество и существование быстрых алгоритмов выполнения. Недостаток — неопределенность в трактовке результатов. Вот краткое описание этих тестов:
1. Проверка несцепленных серий. Последовательность разбивается на m непересекающихся серий и строится распределение χ2 для частот появления каждой возможной серии.
2. Проверка интервалов. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя длины подпоследовательностей, все элементы которых принадлежат определенному числовому интервалу.
3. Проверка комбинаций. Последовательность разбивается на подпоследовательности определенной длины, и исследуются серии, состоящие из различных комбинаций чисел.