Пусть по модулю принадлежит показателю . Тогда делится на . Таким образом, показатели, которым числа принадлежат по модулю , есть делители . Числа, принадлежащие показателю (если такие существуют), называются первообразными корнями по модулю .
Символ Лежандра. Функция чисел и , определенная для простых нечетных и целых , не делящихся на называется символом Лежандра и обозначается
, если сравнение разрешимо, в противном случае же случае
Символ Якоби. Символ Якоби является обобщением символа Лежандра и служит для упрощения вычисления последнего. Пусть - нечетное натуральное число, - его разложение на простые множители. Для всякого целого , , символ Якоби определяется по формуле:
Цепные дроби. Цепная дробь - один из важнейших способов представления чисел и функций. Цепная дробь есть выражение вида
где - любое целое число, - натуральные числа, называемые неполными частными.
2. Алгебраические основы
Понятие группы.
Группой называется непустое множество с алгебраической операцией * на нём, для которой выполняется первые 3 из четырёх следующих аксиом.
1). Операция * ассоциативна, т.е. для любых .
2). В G имеется единичный элемент (или единица) e такой, что для любого
3). Для каждого a G существует обратный элемент такой, что
4). Для любых
Если дополнительно группа удовлетворяет четвертой аксиоме, то группа называется абелевой или коммутативной.
Множество образует группу относительно операции сложения. То же можно сказать относительно рациональных чисел , вещественных чисел и комплексных чисел .
Через будет отличать аддитивную группу классов вычетов по модулю m.
Если взять все классы вычетов, взаимно простые с модулем m, и определить их умножение по модулю m, то получится группа, обозначаемая через . Число элементов конечной группы называется порядком группы и обозначается через .
Группа называется циклической, если она порождена одним элементом, т.е. в ней имеется такой элемент a, что любой другой элемент представим в виде . Если - отрицательное, то под понимается произведение
Циклическими являются группы и . Группа - циклическая лишь в случае, когда по модулю m существует первообразный корень.
Циклическая группа всегда коммутативна.
Подгруппы групп.
Подмножество группы называется подгруппой этой группы, если H образует группу относительно операции группы .
Подгруппы группы , отличные от тривиальных групп , называется собственными подгруппами.
Гамоморфизмы групп.
Отображение группы в группу называется гомоморфизмом, если оно согласовано с операциями на группах и , т.е. для любых элементов
Кольца и поля.
Кольцом называется множество с двумя бинарными операциями, обозначаемыми символами “+” и “*”, такими что:
1). - абелева группа;
2). Операция умножения ассоциативна, т.е. для всех ;
3). Выполняются законы дистрибутивности, т.е. для всех
и ;
Подкольца.
Подмножество кольца называется подкольцом этого кольца, если оно замкнуто относительно имеющихся операций сложения и умножения и само образует кольцо относительно этих операций.
Гомоморфизмы колец.
Пусть и - кольца. Гомоморфизмом называется отображение, для которого , , при всех
3. Генераторы случайных последовательностей
3.1 Равномерно распределённая случайная последовательность и её свойства
Случайные числа и их генераторы являются неотъемлемыми современных криптосистем. Приведём конкретные примеры использования случайных чисел в криптологии:
1). Сеансовые и другие ключи для симметрических криптосистем, таких как DES, ГОСТ 28 147-89, Blowfish;
2). Стартовые значения для программ генерации ряда математических величин в асимметрических криптосистемах, например, “больших простых чисел” в криптосистемах RSA, ElGamal;
3). Случайные слова, комбинируемые с парольными для нарушения “атаки угадывания” пароля криптоаналитика;
4). Вектор инициализации для блочных криптосистем, работающих в режиме обратной связи;
5). Случайные значения параметров для многих систем электронной цифровой, например DSA;
6). Случайные выборы в протоколах аутенфинации, например в протоколе Цербер (Kerberos);
7). Случайные параметры протоколов для обеспечения уникальности различных реализаций одного и того же протокола, например в протоколах SET и SSL.
Отметим, что для некоторых из этих криптографических применений необходимы огромные массивы случайных чисел, которые по своему назначению требуют конфиденциального использования. Например, в протоколе Цербер сетевой сервер генерирует тысячи сессионных ключей ежечасно. К сожалению, компьютеры по своей конструкции предназначены быть детерминированными системами, поэтому на современных компьютерах генерация случайных чисел весьма затруднительна.
Известно, что проблема генерации случайной последовательности с произвольным законом распределения вероятностей сводится к проблеме генерации так называемой равномерно распределённой случайной последовательности (РРСП), или, как её часто называют в криптографических приложениях, “число случайной” последовательности.
РРСП - случайная последовательность со значениями в дискретном множестве, определённая на вероятностном пространстве и удовлетворяющая двум свойствам - и .
Свойство . Для любого и произвольных значений индексов случайные величины независимы в совокупности.
Свойство . Для любого номера случайная величина имеет дискретное равномерное на распределении вероятностей:
Из базовых свойств и вытекают следующие дополнительные свойства, используемые при генерации случайных чисел.
Свойство . Если - РРСП, то для любого и любой фиксированной последовательности индексов -мерное дискретное распределение вероятностей вектора (слова) является равномерным:
Свойство . Если - элемент РРСП, то справедливы следующие выражения его начального и центрального моментов - го порядка:
Где - числа Бернулли.
Свойство . Для новариационной функции и спектральной плотности РРСП справедливы следующие выражения:
Свойство . (воспроизводимость при прореживании). Для любой фиксированной последовательности моментов времени при “прореживании” РРСП возникает последовательность
,
которая тоже является РРСП.
Свойство . (воспроизводимость при суммировании). Если - РРСП, а - произвольная неслучайная либо случайная последовательность, не зависящая от , то случайная последовательность также является РРСП.
Свойство . Если - РРСП, то количество информации по Шеннону, содержащейся в отрезке последовательности , о будущем элементе равно нулю:
поэтому для любого алгоритма прогнозирования вероятность ошибки не может быть меньше, чем для “угадывания по жребию”:
.
Свойство . Если - РРСП, то для любого и произвольной борелевской функции переменных , при имеет место сходимость “почти наверное”:
Свойство . Если - равномерно распределенная последовательность порядка , то - РРСП.
С учетом свойств определим понятия генератора случайной последовательности и его типов.
Генератор РРСП - устройство, позволяющее по запросу получить реализацию равномерно распределенной случайной последовательности длиной ; элементы этой реализации принято называть случайными числами. Существует три типа генераторов РРСП:
1. Табличный.
2. Физический.
3. Программный.
В следующем разделе мы рассмотрим программный генератор.
Программный генератор РРСП - программа имитации на компьютере реализации РРСП. Имитируемая последовательность называется псевдослучайной, так как она вычисляется на компьютере по известному детерминированному (обычно рекуррентному) соотношению, и в то же время её статические свойства “близкие” к свойствам РРСП.
В разделе “Алгоритмы генерации псевдослучайных последовательностей” мы познакомимся с основными методами генерации псевдослучайных последовательностей, а в разделе “Методы генерации истинно случайных последовательностей” мы рассмотрим различные методы повышения “случайности” генераторов РРСП.
3.2 Алгоритмы генерации псевдослучайных последовательностей.
Классификация существующих алгоритмов генерации псевдослучайных последовательностей представлена на рис. Выделяются три основных подхода к построению алгоритмов генерации:
1). Прямые методы построения элементарных рекуррентных последовательностей:
2). Методы «улучшения элементарных последовательностей», заключающиеся в специальных функциональных преобразованиях этих последовательностей для уменьшения отклонения их статистических свойств от свойств РРСП.
3). Комбинирование алгоритмов генерации, построенных с помощью первого или второго подхода.
Линейные и мультипликативные конгруэнтные генераторы. Линейным конгруэнтным генератором (ЛКГ) с параметрами () называется программный генератор РРСП, порождающий псевдослучайную последовательность ,, с помощью рекуррентного соотношения
(3.2.1)
Параметры этого генератора (3.2.1) имеют следующий смысл:
- начальное или стартовое значение;
- не нулевой множитель;
- приращение;
- модуль, равный мощности алфавита .
Страницы: 1, 2, 3, 4, 5, 6
