Защита информации 2 5 (стр. 4 из 14)

и ;

Подкольца.

Подмножество

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

Гомоморфизмы колец.

Пусть

и – кольца. Гомоморфизмом называется отображение, для которого , , при всех

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

3.1 Равномерно распределённая случайная последовательность и её свойства

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

1). Сеансовые и другие ключи для симметрических криптосистем, таких как DES, ГОСТ 28 147-89, Blowfish;

2). Стартовые значения для программ генерации ряда математических величин в асимметрических криптосистемах, например, “больших простых чисел” в криптосистемах RSA, ElGamal;

3). Случайные слова, комбинируемые с парольными для нарушения “атаки угадывания” пароля криптоаналитика;

4). Вектор инициализации для блочных криптосистем, работающих в режиме обратной связи;

5). Случайные значения параметров для многих систем электронной цифровой, например DSA;

6). Случайные выборы в протоколах аутенфинации, например в протоколе Цербер (Kerberos);

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

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

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

РРСП – случайная последовательность

со значениями в дискретном множестве , определённая на вероятностном пространстве и удовлетворяющая двум свойствам - и .

Свойство

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

Свойство

. Для любого номера случайная величина имеет дискретное равномерное на распределении вероятностей:

Из базовых свойств

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

Свойство

. Если – РРСП, то для любого и любой фиксированной последовательности индексов –мерное дискретное распределение вероятностей вектора (слова) является равномерным:

Свойство

. Если – элемент РРСП, то справедливы следующие выражения его начального и центрального моментов – го порядка:

Где

– числа Бернулли.

Свойство

. Для новариационной функции и спектральной плотности РРСП справедливы следующие выражения:

Свойство

. (воспроизводимость при прореживании). Для любой фиксированной последовательности моментов времени при “прореживании” РРСП возникает последовательность

,

которая тоже является РРСП.

Свойство

. (воспроизводимость при суммировании). Если - РРСП, а – произвольная неслучайная либо случайная последовательность, не зависящая от , то случайная последовательность также является РРСП.

Свойство

. Если - РРСП, то количество информации по Шеннону, содержащейся в отрезке последовательности , о будущем элементе равно нулю:

,

поэтому для любого алгоритма прогнозирования

вероятность ошибки не может быть меньше, чем для “угадывания по жребию”:

.

Свойство

. Если - РРСП, то для любого и произвольной борелевской функции переменных , при имеет место сходимость “почти наверное”:

Свойство

. Если – равномерно распределенная последовательность порядка , то – РРСП.