Оценки стойкости систем защиты дискретных данных

• Автор: Семенов, Александр Анатольевич
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Иркутск
• Количество страниц: 106 с.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА I. Теоретико-вероятностное описание анализа криптограммы
1.1. Общая постановка задачи анализа криптоструюгур
£1.1. Индикаторы событий, описывающих анализ криптограммы
1.1.2. Криптологические структуры
1.1.3. Криптоаналитические автоматы
1.2, Пространство исходов криптоаналитического автомата
и общие подходы к оценкам стойкости криптосистем
1.2.1. Отношения порядка на множестве секретных ключ ей
1.2.2. Пространство исходов криптоаналитического автомата
1.2.3. Вычислительная сложность криптосистем
1.2.4. Подход к определению стойкости криптосистем
ГЛАВА 11. Оценки стойкости некоторых классов криптологических структур
11.1. Общий подход к оценке стойкости блочных шифров
11.1.1. О понятиисемантичностикриптограммы
11.1.2. Постановка задачи криптоанализа для двоичной криптосистемы с коротким псевдослучайным ключом
11.1.3. Два подхода к анализу криптосистем
класса А3[ (2, к, Тт)
11.2. Анализ стойкости криптоструктур класса (X,S(D)) с множеством состояний при общих предположениях
ГЛАВА III. Системы, обеспечивающие совершенную аутентичность
на базе кодов, исправляющих ошибки
III. 1. Анализ возможности имитации
111. 2. Анализ возможности подмены
III. 3. Примеры построения систем аутентификации и возникающие в связи с этим комбинаторные задачи
111. 4. Оценки аутентичности систем, образованных
семействами кодов
III. 5. Системы аутентификации на основе других
кодовых конструкций
111. 6. Заключительные замечания
ПРИЛОЖЕНИЕ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ
Предлагаемая диссертация является работой в области теории систем защиты передачи данных. В западной литературе эта отрасль получила название криптологии. Стремление человека к обеспечению защиты пере-дачи жизненно-важной информации прослеживается с глубокой древности. Одним из наиболее известных примеров криптологического подхода к этой проблеме является так называемый шифр Цезаря, которым по достоверным историческим данным пользовался Гай Юлий Цезарь. Помимо этого в литературе (в том числе и художественной) описано огромное количество различных способов создания шифров и не меньшее число способов их раскрытия.
Всю историю криптологии принято делить (согласно замечанию Дж. Л. Месси) на два этапа. Первый, донаучный — с глубокой древности и до !949г.. Второй, научный — с 1949г. и по сей день. Такой подход продиктован тем, что в 1949г. вышла работа К. Э. Шеннона “Теория связи в секретных системах” [1], которая остается наиболее значимой работой по теории криптосистем с секретным ключом. За, почти полвека, прошедших с момента ее публикации по данной тематике вышло (в открытой печати) незначительное количество статей (см., например, работы [14], [19], [20]), содержащих результаты, сопоставимые по своей значимости с результатами упомянутой работы Шеннона.
Остановимся подробнее на некоторых основных моментах этой работы.
Прежде всего приведем определение (общую схему) секретной системы данное Шенноном.
Согласно этой схеме, сообщение от источника передается на шифрующее устройство, на которое также подается некоторый секретный ключ. “Смешивая” сообщение с секретным ключом, шифратор образует криптограмму, которая отправляется в открытый канал. Секретный ключ по закрытому каналу передается на дешифратор где происходит обратное шифрующему преобразование и к получателю поступает исходное сообщение (открытый текст). Предполагается, что криптоаналитик противника оказывается в состоянии перехватить криптограмму, но у него нет доступа к закрытому каналу, поэтому ему не известен секретный ключ. Предполагается также, что криптоаналитику известны собственно шифрующее и дешифрующее преобразования и, таким образом, секретность криптограммы определяется только секретностью ключа (так называемое правило Керкхоффа).
Опишем теперь модель секретной системы Шеннона математически, следуя работе Дж. JI. Месси (см. [3]).
Базовыми объектами являются множества X,Y,Z соответственно открытых текстов, криптограмм и секретных ключей. Элементы этих множеств— следующие векторы:
Х = (хьх2
у = Ez(x),x = Dz(y),
если элементы множеств X,Y,Z— двоичные векторы одинаковой длины, то в качестве шифрующего и дешифрующего преобразований может выступать сложение соответствующих двоичных последовательностей по mod 2.
Фиксированные элементы множеств XJ,Z далее будем обозначать верхним нулевым индексом. Предполагается, что криптоаналитику доступны множества X,Y,Z, преобразования EZ,DZ и криптограмма у0. Не известны ему лишь истинный открытый текст х° и истинный секретный ключ z°. Таким образом, при известной криптограмме стойкость криптосистемы определяется только секретностью ключа (правило Керкхоффа).
Событие {х = х0} состоит в том, что выбранный криптоаналитиком элемент х е X (оценка истинного открытого текста), при условии, что ему

Предположим, что рассматриваемая криптосистема принадлежит классу TVern2. Найдем сложность произвольной криптограммы данной криптосистемы. Прежде всего, предполагаем, что имеет место:
ZlZ = Vk,Zi=Zi_lzi_l,Vk=2k =и.
По условию вероятность выбора истинного секретного ключа z0 из множества Zj не зависит от произвольно заданного на Zi отношения порядка Tj, и выбор оценки ключа на каждом шаге производится абсолютно случайным образом, то есть для любого события Dz. = {zt =z0} его вероятность зависит только от номера события i. Для таких вероятностей, оче-
1 1 {'
видно, имеет место: р* = — -
Zj n-i + l

Iv =|Z|= и и V/ .В самом деле, согласно формуле (2.2.5),

выполняется:
1 /1 К, 1 Ч 1 /1 Л ! 1 W1 I 1 Л
А=-й=0— )(—Д =0-Д---Д-1)'(——)=0
п п п— п П-1+1 п П-1+1 п
Очевидно, что в этом случае шенноновское (для которого явно не задано вероятностное пространство) событие, описываемое как “выбор истинного секретного ключа reZ:z = 20” эквивалентно произвольному событию D,, где / по вероятностной мере. Действительно, в случае шен-
ноновского события такая мера есть P{z = z0} = — для произвольного

z eZ и, согласно доказательству Шеннона, имеет место:
P{Z Щ z0} = Р{х = Х0у = у0} = Р{Х т Х0}
(совершенная секретность), а в случае алгебры событий Dt получаем:
P{D- } - Pi = — = — и тогда справедливо: п Z
P{Zi =z0} = Pi =-,Vi{ n
Посчитаем сложность криптосистемы класса TVern2, согласно предложенному выше подходу. Из всего сказанного следует, что для таких криптосистем существует единственное вероятностное пространство (А А,Р). В самом деле, вероятность выбора истинного секретного ключа на каждом шаге работы автомата не зависит от произвольного отношения порядка на соответствующем множестве Zhi е{1