Кольцом называется множество с двумя бинарными операциями, обозначаемыми символами “+” и “*”, такими что:

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). Если кратно 9, то либо , либо и .

Свойство . Если , то наибольший период тогда и только тогда, когда - нечётно, - чётно, - нечётное число, удовлетворяющее соотношению

.

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

(

где - обратный к элемент по модулю , т.е. - параметры генератора.

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

(

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

()

Параметрами нелинейного конгруэнтного генератора (), () является .

Рекуррентны в конечном поле. Обращение мультикапликативной конгруэнтной последовательности является линейная рекуррентная последовательность порядка над конечным полем ( - простое число):

 ()

где - коэффициенты рекуррентны, а - начальные значения рекуррентны.

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

()

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

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

, ()

где - параметры генератора, . В случае или - целые числа .

4. Первый этап развития криптографии

Защита информации может быть двух видов: шифрование и передача по закрытому каналу.

Предполагается, что сообщения передаются по так называемому “открытому” каналу связи, в принципе доступного для прослушивания некоторым другим лицам, отличным от получателя и отправителя.

Будем считать, что A (Алиса) - отправитель сообщения, а В (Боб) - корреспондент (получатель) сообщения, Е (Елена) - некий враг.

Классическая система секретной связи показана на рис. 1.

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

Шифрование осуществляется в соответствии с этой подстановкой. Величина не является единственно возможной.

Криптоанализ этого шифра очень прост. Для любого современно языка вычислены частотные характеристики букв, т.е. относительные частоты их появления в “нормальных” текстах.

Модулярный шифр.

Выберем число , взаимно просто с модулем. Пусть р - буква английского алфавита, отождествлённая со своим порядковым номером (0,1,…,25). Тогда ,, где - фиксировано. В этом случае ключом является пара чисел . Условие взаимной простоты необходимо для обратимости шифра.

Гомофоническое шифрование.

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

Полиграммное шифрование.

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

Замена биграмм производится по правилам:

1) если и находятся на одной строке, то биграмма шифруется диаграммой , где буквы и являются правыми соседями букв и соответственно, если правого соседа нет, то берется буква строки.

2) если и находятся на одном столбце, то берутся нижние соседи с аналогичной оговоркой.

3) если , то в незашифрованном тексте между ними вставляется незначащая буква (например, ).

4) при нечетном количестве букв в незашифрованном тексте к нему дописывается незначащая буква.

5) в наиболее вероятном количестве, когда и расположены в разных столбцах и строках, и выбираются, как показано на схеме:

Код Энигма.

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

Страницы: 1, 2, 3, 4, 5