Математические основы криптологии и криптографические методы и средс

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

Обратите внимание, что число, полученное в результате сумми­ рования R0* и R0**, может не уместиться полностью в ячейке R\. В этом случае от полученного числа должны быть отброшены лиш­ ние разряды. Поясним это для рис. 14, где все ячейки представлены

Как видим, число 306 занимает 9 разрядов (в двоичной системе счис­

убрать один «лишний», крайний левый бит из числа 306, в результате чего в /?1 пойдет уже не 306, а 001100102 = 5010. Также заметим, что в таких языках, как Паскаль, «урезание» лишних битов при перепол­ нении ячейки производится автоматически в соответствии с задан­ ным типом переменной.

Мультипликативный метод генерации псевдослучайных чи­ сел был предложен Д.Г. Лехмером (D.H. Lehmer) в 1949 году. В этом методе используется операция х (mod у), возвращающая остаток от деления первого аргумента на второй. В качестве текущего значения случайного числа выделяют остаток от деления произведения пре­ дыдущего случайного числа и постоянного множителя к на постоян­ ное число М:

г, = к Гм + 6(тосШ),

где к, М - постоянные числа; г,— случайное число.

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

г,- = к гм + 6(modA/),

где М - модуль (0 < М); к - множитель (0 < к <М);

b - приращение (0 < b <М);

г0- начальное значение (0 < r0 <М).

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

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

ской операции «AND». Также широко распространен выбор наи­ большего простого числа М, меньшего, чем 2Ы: в специальной лите­ ратуре доказывается, что в этом случае младшие разряды получаемо­ го случайного числа г/ + 1 ведут себя так же случайно, как и старшие, что положительно сказывается на всей последовательности случай­ ных чисел в целом. В качестве примера можно пивести одно из чисел Мерсенна, равное 231 - 1, и таким образом, М = 231 - 1.

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

Теорема 15. Линейная конгруэнтная последовательность, опре­ деленная числами М9к, b и г0, имеет период длиной М тогда и только тогда, когда

числа Ь и М взаимно простые;

к- 1 кратнор для каждого простогор, являющегося делителем М\

к- 1 кратно 4, если М кратно 4.

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

Пример 48.

M =2N

к - 3 + 8 • q (или к = 5 + 8 q) Ь^О г0- нечетно.

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

Пример 49

А/ = 231 - 1 к = 1 220 703 125 6 = 7

го = 7 Генератор случайных чисел, использующий данные из примера

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

1.3.4. Проверка качества работы ГСЧ

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

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

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

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

Методы проверки равномерности распределения

1. ГСЧ должен выдавать близкие к следующим значения стати­

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

2. Частотный тест Частотный тест позволяет выяснить, сколько чисел попало в ин­

тервал {тг~ а,; т,- + оЛ), т.е. (0,5 - 0,2887; 0,5 + 0,2887), или в конеч­ ном итоге (0,2113; 0,7887). Поскольку 0,7887-0,2113 = 0,5774, за­ ключаем, что в хорошем ГСЧ в этот интервал должно попадать около 57,7 % из всех выпавших случайных чисел (рис. 15).

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

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

вестных статистических критериев; он является основным методом, ис­ пользуемым в сочетании с другими критериями. Критерий х2 был пред­ ложен в 1900 году Карлом Пирсоном. Его замечательная работа рас­ сматривается как фундамент современной математической статистики.

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

Частотная диаграмма эталонного ГСЧ представлена на рис. 16. Поскольку закон распределения эталонного ГСЧ равномерный, то (теоретическая) вероятность /?, попадания чисел в /-й интервал (всего этих интервалов к) равна /?, = 1/к. И, таким образом, в каждый из к интервалов попадет ровно по pi N чисел (N - общее количество сге-

Реальный ГСЧ будет выдавать числа, распределенные (причем не обязательно равномерно) по к интервалам, и в каждый интервал попадет по щ чисел (в сумме щ + п2+ + л* = N). Как же нам опре­ делить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел и, и «эталонным» pt N. Сложим их и в результате получим

Х2эксп~ (п\ ~ Р \ N )z + (n2 - p 2 N)2 + + (nk- p k N)2.

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

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

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

В табл. 5 приведены теоретические значения «хи-квадрат» (Х2теоР). где v =N - 1 - это число степеней свободы, ^ - э т о довери­ тельная вероятность, задаваемая пользователем, который указывает, насколько ГСЧ должен удовлетворять требованиям равномерного распределения, или р - это вероятность того, что экспериментальное значение х^ксп будет меньше табулированного (теоретического) х^ор или равно ему.

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

Если Х2эксп много больше х^еор (т.е. р - велико), то генератор не удовлетворяет требованию равномерного распределения, так как на­ блюдаемые значения л, слишком далеко уходят от теоретических р( 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теоР (т.е. р - мало), то генератор не удовлетворяет требованию случайного равномерного распределения, так как наблюдаемые значения л, слишком близки к теоретическим Pi N и не могут рассматриваться как случайные.

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

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

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

1.Диапазон от 0 до 1 разбивается на к равных интервалов.

2.Запускается ГСЧ N раз (N должно быть велико, например Nik > 5).

3.Определяется количество случайных чисел, попавших в каж­ дый интервал: nh i = 1, ..., к.

4.Вычисляется экспериментальное значение х^эксп по следую-

теоретическая вероятность попадания чисел в к-й интервал.

Путем сравнения экспериментально полученного значения х2эксп с теоретическим х2теор (см. табл. 5) делается вывод о пригодности ге­ нератора для использования. Для этого:

1. Входим в табл. 4 ( v = количество экспериментов - 1).

♦ Сравниваем вычисленное х2,ксп с х^ор, встречающимися в строке.

При этом возможно три случая.

♦Первый случай: х2эксп много больше любого х2теоР в строке - гипотеза о случайности равномерного генератора не выпол­ няется (разброс чисел слишком велик, чтобы быть случай­ ным).

♦Второй случай: %2ЭКСПмного меньше любого %2теоР в строке — гипотеза о случайности равномерного генератора не выпол­ няется (разброс чисел слишком мал, чтобы быть случайным).

♦Третий случай: х2эксп лежит между значениями х2теор двух ря­ дом стоящих столбцов — гипотеза о случайности равномер­ ного генератора выполняется с вероятностью р (т.е. в р слу­

чаях из 1 0 0 ).

Заметим, что чем ближе получается р к значению 50 %, тем луч­

ше.

Проверка ГСЧ на статистическую независимость. Проверка на частоту появления цифры в последовательности. Рассмотрим пример. Случайное число 0,2463389991 состоит из цифр 2463389991, а число 0,5467766618 состоит из цифр 5467766618. Соединяя после­ довательности цифр, имеем 24633899915467766618.

Понятно, что теоретическая вероятность у>, выпадения г'-й цифры

цифра 1 выпала 2 раза из 20, а цифра 6 выпала 5 раз из 20.

Далее считают оценку и принимают решение по критерию «хиквадрат».

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

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

п 2 = 2.

Вероятность появления серии длиной в L: рь = 9 КГ2, (теорети­ ческая), т.е. вероятность появления серии длиной в один символ рав­ на: р/ = 0,9 (теоретическая). Вероятность появления серии длиной в два символа: р2 = 0,09 (теоретическая). Вероятность появления се­ рии длиной в три символа: р2 = 0,009 (теоретическая).

Например, вероятность появления серии длиной в один символ p i = 0,9, так как всего может встретиться один символ из 1 0 , а всего символов 9 (ноль не считается). А вероятность того, что подряд встретится два одинаковых символа «XX» равна 0,1 *0,1 -9, т.е. веро­ ятность 0,1 того, что в первой позиции появится символ «А”», умножает­ ся на вероятность 0,1 того, что во второй позиции появится такой же символ «А"» и умножается на количество таких комбинаций 9.

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

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

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

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

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