Оценки стойкости систем защиты дискретных данных тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Семенов, Александр Анатольевич

• Семенов, Александр Анатольевич
• кандидат технических наук
• 1998

Оглавление диссертации кандидат технических наук Семенов, Александр Анатольевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА I. Теоретико-вероятностное описание анализа криптограммы

1.1.1. Индикаторы событий, описывающих анализ криптограммы

1.1.2. Криптологические структуры

1.1.3. Криптоаналитические автоматы

1.2.4. Подход к определению стойкости криптосистем

ILL Общий подход к оценке стойкости блочных шифров

II.1 Л. О понятии семантичности криптограммы

III.2. Постановка задачи криптоанализа для двоичной криптосистемы с коротким псевдослучайным ключом

11.1.3. Два подхода к анализу криптосистем

класса Ащ (2, к, Тт ib

11.2. Анализ стойкости криптоструктур класса (X,S(D)) с

III. 1. Анализ возможности имитации

111. 2. Анализ возможности подмены

III. 3. Примеры построения систем аутентификации и возникающие в связи с этим комбинаторные задачи

111. 4. Оценки аутентичности систем, образованных семействами кодов

III. 5. Системы аутентификации на основе других

Г

ПРИЛОЖЕНИЕ

' ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Введение диссертации (часть автореферата) на тему «Оценки стойкости систем защиты дискретных данных»

ВВЕДЕНИЕ

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

Всю историю криптолоши принято делить (согласно замечанию Дж. Л. Месси) на два этапа. Первый, донаучный — с глубокой древности и до 1949г.. Второй, научный — с 1949г. и по сей день. Такой подход продиктован тем, что в 1949г. вышла работа К. Э. Шеннона "Теория связи в секретных системах" [1], которая остается наиболее значимой работой по теории криптосистем с секретным ключом. За, почти полвека, прошедших с момента ее публикации по данной тематике вышло (в открытой печати) незначительное количество статей (см., например, работы [14], [19], [20]), содержащих результаты, сопоставимые по своей значимости с результатами упомянутой работы Шеннона.

Остановимся подробнее на некоторых основных моментах этой работы.

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

Опишем теперь модель секретной системы Шеннона математически, следуя работе Дж. Л. Месси (см. [3]).

Базовыми объектами являются множества Х,У,2 соответственно открытых текстов, криптограмм и секретных ключей. Элементы этих множеств— следующие векторы:

* = (*Ь*2>->*#(х))> У= (УъУ2>->УМ(у))> 2 = •

Компоненты векторов могут выбираться из некоторых алфавитов, объемы которых есть соответственно Ь{х\Ь(у),Ь{£) (на практике чаще всего компоненты любого из векторов выбираются из {0,1}). Шифрующее и дешифрующее преобразования записываются в следующем виде:

у = Ех(х),х = В2(у),

если элементы множеств Х,У,2— двоичные векторы одинаковой длины, то в качестве шифрующего и дешифрующего преобразований может выступать сложение соответствующих двоичных последовательностей по тосИ2.

Фиксированные элементы множеств Х,У,2 далее будем обозначать верхним нулевым индексом. Предполагается, что криптоаналитику доступны множества X, У,2, преобразования Е2,В2 и криптограмма у0. Не известны ему лишь истинныи открытый текст х и истинныи секретный ключ 2°. Таким образом, при известной криптограмме стойкость криптосистемы определяется только секретностью ключа (правило Керкхоффа).

Событие {х = х0} состоит в том, что выбранный криптоаналитиком элемент хеХ (оценка истинного открытого текста), при условии, что ему

у = у° совпадет с х°. Вероятность этого

— Р{х = х°|_у = j0} Шеннон и определяет как меру раскрываемости крип-

9 N

о том, что кри:

теоретической или практической криптостойкостью. Теоретически стойкие криптосистемы (по Шеннону) — это криптосистемы, для раскрытия

называемые совершенно-секретные системы. Согласно подходу Шеннона, совершенная секретность определяется следующим условием:

р{х = х° \у = у°} = Р{х = х0},

то есть вероятность раскрытия криптограммы 3;° равна вероятности нахождения истинного открытого текста криптоаналитиком при неизвест-

"выбор истинного открытого текста из X" равна его апостериорной вероятности. Далее Шенноном было показано, что такие криптосистемы ре=

стема Вернама. В этой криптосистеме элементы множеств Х,У,2 представляют собой двоичные векторы одинаковой длины и каждый бит от-

ных (то есть каждый последующий бит секретного ключа выбирается из алфавита {0,1} совершенно случайно и не зависимо от предыдущих).

Для получения соотношений, связывающих длину секретного ключа с длиной открытого текста, Шеннон использует понятие информационн-ной энтропии, введенное им годом раньше в работе "Математическая теория связи" (1948 г.) (см. [2]). Энтропия системы 9? с п состояниями, в каждое из которых она переходит с вероятностями #, / е {!,...,»} есть

Н(Ш) = ^"Рг log—, '-1 Pi

здесь log—логарифм по основанию 2. В применении к криптологии, например, если для криптоаналитика все открытые тексты из некоторого

$ ^ 1

X с! равновероятны и Vz е{1,...,[Х |}=>рг- =—г-, то энтропия (неопре-

\Х I

из X есть

1 'log|X*|= log|X*|, если X* = X и X-

\x*\

можных двоичных последовательностей длины к, то Н(х) = к .

H(z) > Н(х),

В случае, когда L(x) = L(z), получаем:

N{z) > N(x).

Вывод, следующий из последнего неравенства: для совершенно-секретных систем при L(x) = L(z) необходимо чтобы длина секретного

Очевидно, что 1фиптоеиетемы, для которых выполняется (1) и, в ча= стности, криптосистемы Вернама (для которых в (1) достигается равенство) не являются практически выгодными, поскольку требуют передачи по

Осознавая, что на практике все равно придется использовать кришго-системы, в которых совершенно случайная "часть" ключа короче открытого текста, Шеннон вводит понятие ненадежности ключа.

/(и)— это неопределенность (энтропия) ключа при п известных знаках криптограммы. Число п такое, что /(л)«О Шеннон назвал расстоянием единственности и заметил, что имея в распоряжении и знаков шифртек-ста, криптоаналитик раскрывает криптограмму, однако, в общем случае, для этого он должен обладать неограниченными вычислительными ресурсами. Далее предпринято исследование на предмет ненадежности некото-

криптостойкости техникой, предложенной Шенноном, применительно к практически используемым криптосистемам представляется весьма непростым (это косвенно отмечено в работе [3] и в примечании редакторов жош перевода работы [1]).

Придя к таким выводам, Шеннон вводит понятие практической крип-

крытая которых потребуются вычислительные ресурсы, несоизмеримо-большие, чем ценность скрываемой информации. В связи с этим Шеннон определяет рабочую характеристику Ш{п) (мера практической крипто-

стойкости) шифра, (см. также [3]) как среднее количество шагов работы некоторого вычислительного устройства, раскрывающего криптограмму длины п, подразумевая, что при этом используется наилучший криптоа-политический алгоритм.

Особый интерес представляет значение W{ri), когда п неограниченно возрастает. По поводу получения оценок величины W{ri) можно процитировать Дж. Л. Месси (см. [3]): "На сегодняшний день не известно (по крайней мере специалистам, занятым открытыми работами) ни одной практической криптосистемы, для которой была бы определена сколько-нибудь содержательная нижняя граница W(°o) „"

Часть работы [1], посвященная изучению оценок величины W(ri) носит, в основном, эмпирический характер, хотя здесь впервые Шеннон неявно вводит понятие индикатора события "выбранная оценка совпала с наперед заданным открытым текстом'5. Об этом говорят следующие цитаты: "Хотя в принципе всегда можно найти эти решения (Например, испытывая все возможные ключи), но для различных систем нужно будет затратить весьма различный объем работы." и "Предположим далее, давая противнику все возможные преимущества, что он сконструировал электронное устройство для испытания ключей со скоростью один ключ в одну мксек (скажем, с помощью автоматического выбора и проверки с помощью критерия значимости %2). Можно ожидать, что он выберет правильный ключ примерно после половины всех возможных испытаний..."

В последнем случае Шеннон совершенно прав (для определенного класса шифров) и это будет строго показано в данной работе. Доказательства же подобных утверждений в работе Шеннона отсутствуют.

Остановимся теперь на спорных моментах работы Шеннона. Прежде всего, отметим, что используя понятие вероятности, Шеннон нигде не определяет строго само вероятностное пространство, описывающее эксперимент по раскрытию криптограммы. Схему общей секретной системы Шеннона вообще невозможно интерпретировать математически корректно, поскольку с одной стороны задача "раскрытие криптограммы" должна иметь единственное решение, а с другой Шеннон предполагает, что крип-тоаналитик может находиться в положении, когда он не в состоянии относительно некоторого множества оценок открытого текста сказать "да" или "нет" на предмет того являются ли эти оценки изначально заданным открытым текстом. Тем не менее, ясно, что такой подход выбран совершен-

но осознано и в соответствии с текущим моментом, поскольку Шеннон отмечает: "... в применении к физическим ситуациям, особенно когда дело касается "субъективных" вероятностей и неповторимых экспериментов, возникают многочисленные вопросы, связанные с логическим обоснованием. Например, при нашем подходе к проблеме секретности допускается, что априорные вероятности различных ключей и сообщений известны шифровальщику, но как он может определить их даже при использовании всех своих сведений о данной обстановке? " Еще одна цитата также объясняет, почему Шеннон не использовал строгого аксиоматического описания вероятностной картины эксперимента, а предпочел более технический подход: "...в других случаях, которые можно себе представить, например, при перехвате сообщений, передаваемых между собой марсианами, высадившимися на землю, априорные вероятности были бы настолько неопределенными, что не имели бы никакого значения. "

В последнее время, особенно с развитием информационных технологий, появились объекты, представляющие собой секретные системы (в несколько ином смысле, чем в определении Шеннона), в которых крип-тоаналитик (противник) может эффективно получать ответ на вопрос: "является ли найденная им оценка открытого текста собственно заданным наперед открытым текстом? " Допуская некоторую нестрогость, отметим, что примером таких секретных систем являются системы защиты, основанные на пароле: вводя некоторую оценку заданного наперед пароля, противник эффективно получает ответ "да" или "нет". Строгое описание подобных секретных систем дается в первой главе диссертации.

Г II 1 ^^ ^ _______!»_« ^

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

ределений Шеннона теоретической и практической стойкости, а также предлагается общая идея получения оценок стойкости криптосистем с секретным ключом, то есть оценок величины W(n).

Вторая глава посвящается более подробному развитию (на примере практически используемых конструкций) основных результатов первой. В частности, рассматривается подход к оценке стойкости класса блочных шифров, при этом наряду с идеей подхода первой главы используется идея трактовки процесса криптоанализа таких шифров некоторой мартовской цепью. Общий смысл данной идеи следует приписать Шеннону (см. [2]). Мерой раскрываемости шифра при предлагаемом подходе является семантичность криптограммы. Понятие семантичности, вводимое в самом начале второй главы шире шенноновского понятия ненадежности, поскольку не предполагает какого либо специального подхода к неопределенности сообщения. Второй подраздел второй главы посвящен исследованию систем защиты, основанных на пароле (строгое определение этого класса систем дается в первой главе) и, в частности, их разновидности, которая может рассматриваться, как модель сети со множеством входов (глобальная или локальная сеть со множеством терминалов). Показано, что задача оценки вероятности проникновения в такую сеть может быть сформулирована и решена, как разновидность так называемой задачи о совпадениях (при этом используются и такие классические вероятностные

66 99

задачи, как задача парадокса дней рождения и задача о размещении частиц по ячейкам).

Наиболее новым направлением в криптологии считается теория аутентификации. И хотя оригинальной статьей по этому вопросу правильнее считать работу [21], "творцом53 теории аутентификации признан Г. Дж. Симмонс, а основополагающей—его работа "Authentication theory/Coding theory55 (см. [15]). Не смотря на то, что теория аутентификации, по меньше мере, на 25 лет "моложе55 теории секретных систем Шеннона, количество публикаций по вопросам аутентификации сообщений намного превосходит число публикаций по теории секретных систем и продолжает расти, (см., например, [22]- [43])

Теория аутентификации занимается изучением обеспечения и установления подлинности отправляемых по открытым каналам сообщений. Для рассмотрения вопросов, возникающих в рамках теории аутентификации, приведем схему передачи данных (предложенную Симмонсом), не-

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

шифратор криптоаналитик дешифратор получатель

-(Ы

1з

лирует секретный канал.

следует, что криптоаналитик он, как и в

в данном случае для него не проще, чем в случае схемы Шеннона. Одна-

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

тиком, за подлинную ет с истинной).

(даже если впоследствии окажется, что стратегия—стратегия подмены. В истинную криптограмму и

поддельную, которую ной, если получатель.

■чит открытый текст отличный от того, который содержался в грамме, перехваченной криптоанашитиком. Поддельная может быть распознана при дешифровке и не доставлена

Р7, а

служит вероятность обмана Р4 = тах{/>7,/>5}.

по

сообщения из некоторого

тель ожидав/

ряжении получателя, но неизвестного криптоаналитику. Поэтому, если криптоаналитик посылает криптограмму, которая расшифровывается получателем в сообщение, принадлежащее множеству X то

обман (в случае попытки имитации сообщение даже может

"-""ИТОГЕ

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

множеством допустимых криптограмм.

В основе всех оценок аутентичности, полученных Симмонсом лежит так называемая функция аутентификации: ф{у,%) равная 1, если крипто= грамма является допустимой при фиксированном секретном ключе г е I и равная 0 в противном случае. Тоща вероятность того, что у допустимая криптограмма для любого секретного ключа ^ из некоторого множества принимает вид:

допустима} = ф (.у, ■ Р{%} (2)

Далее используя соотношение (2), формулу для информационной эн= тропии и выпуклость функции t■\o%t, Симмонс показывает, что имеет место неравенство:

1о§Р; >-1(у; I), (3)

где 1(у;ж) = Н(у)-Л(у\ г)— средняя взаимная информация между у иг. Из последнего неравенства и определения вероятности обмана следует так называемая граница совершенной аутентичности Симмонса:

!О8Р, >-1(у;г), (4)

равенство в которой Симмонс и определил, как совершенную аутешшч-ность. Теория стойкости систем аутентификации развита значительно слабее теории стойкости секретных систем. В общем случае не известны! условия при которых существуют системы, обеспечивающие совершенную аутентичность. Большинство же явных конструкций имеют вид примеров, которые хотя и позволяют понять общие идеи теории аутентификации, не дают общей картины объектов, укладывающихся в ее рамки.

Рассмотрим пример (см. [3]) системы шифрования, описывающейся следующей таблицей:

0 1

0 0 0 1 1 0 1 1 00 01 10 11 11 10 01 00

ности

э! у

= 1/2 =

1

1У) =

ют

ii, =

ШЯЯРТ

криптограмму у, криптоаналитик заменяет ее на двоичный вектор Ф11 и отправляет получателю. Согласно данной таблице, получатель принимает такую поддельную криптограмму за подлинную и, расшифровывая ее, получает текст отличный от истинного, следовательно вероятность подмены Р3 = 1 и данная система не обеспечивает защиты от подмены и не обеспе-

Можно привести примеры, аналогичные данному, систем, обеспечи-»вершенную секретность и защиту от подмены, но не обеспечивающих защиту от имитации, систем не обеспечивающих ни совершенной

секретными и обеспечивающих совершенную аутентичность. Недостаток такого подхода заключается в том, что алгоритм шифрования носит в та-

аблицы и не может быть использован практически

третьей главе диссертации предложен подход к описанию класса 1утентификации на основе алгебраических кодов, исправляющих ошибки. Найдены достаточные условия того, чтобы предложенные системы асимптотически обладали совершенной аутентичностью. Для построения систем аутентификации используются коды, достигающие ниж-

ней границы Варшамова-Гилберта (см [16]). Возникающие при этом задачи имеют отношение как собственно к теории кодирования, так и к некоторым вопросам алгебраической комбинаторики и теории конечных геометрий.

Также предлагаются конструкции систем аутентификации на основе кодов, достигающих границы Варшамова-Грайсмера. Показано ([17], [16], также см. [7]), что для произвольного линейного g-ичного (иД,^)=кода справедливо следующее соотношение:

4t (5)

q

Соотношение (5) носит название границы Варшамова-Грайсмера (в других источниках—границы Грайсмера), а выражение, стоящее в правой части (5), обозначают g{k,d). Линейные коды, для которых в (5) достигается равенство называют кодами, достигающими границы Варшамова-Грайсмера. Класс кодов на границе Грайсмера весьма широк и разбивается на множество подклассов. Для случая q = 2 такие коды детально исследованы в работах [44]—[49]. Для произвольного простого или являющегося натуральной степенью простого q структурный анализ кодов на границе Грайсмера предпринимался в работах [18], [50], [51], в частности, в [50], [51] показано, что задача классификации таких кодов напрямую связана с задачей классификации М.Д.Р. кодов, которая полностью не решена по сей день. В работе [50] также исследовался вопрос о представлении порождающих матриц антикодов g-ичных кодов, достигающих границы Грайсмера, в так называемой канонической форме. Примерами кодов с порождающей матрицей антикода в канонической форме являются коды класса Соломона-Штиффлера. Как будет видно из результатов главы 3 данной диссертации, представимость порождающей матрицы антикода кода в канонической форме зачастую дает возможную основу для построения системы аутентификации.

I. ТЕОРЕТИКО-ВЕРОЯТНОСТНОЕ ОПИСАНИЕ АНАЛИЗА КРИПТОЛОПМЕСКИХ СТРУКТУР

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

1ЛЛо Ишуржапгоры шбытшй, ©шгасыюшшщих анализ пфшштограммы

Рассматриваем непустые конечные или счетные множества Х,У,2 соответственно открытых текстов, криптограмм и секретных ключей (это, так называемые, базовые множества). Скажем, что произошло событие В - {х = х0}, если выбранная некоторым (быть может случайным) образом оценка открытого текста х е X совпала с наперед заданным истинным открытым текстом х0 е! (или просто "открытым текстом"). Кроме того, предполагаем, что задана некоторая функция /: X х 2 -»7, всякой паре (х,г) сопоставляющая элемент уеУ, причем определена обратная функция g :¥ х2 X, любой паре (у, г): сопоставляющая эле-

мент х е X. Событие, состоящее в том, что для фиксированного >>0 ё7 м выбранного некоторым (быть может случайным) образом г е 2 значение функции g(yo,z) совпало с наперед заданным истинным открытым текстом: х = g(yQ,z) = х0, обозначаем далее {х = х0-}. Относительно по= следнего события будем также говорить, что произошло раскрытие криптограммы у = уо. Под криптосистемой будем понимать кортеж

{Х,У,2,у,/,8\Уу^У (1.1.1)

Ниже будет дано более общее определение криптоструктур, включающее в себя понятие криптосистем.

Очевидно, что задачу нахождения единственного х е X такого, что х = х0 из условий заданных набором (1.1.1) нельзя назвать математически

В работе [1] (также см. [3]) фигурирует понятие вероятности события

{х = Хф}

/ Э

рова, такое, что события йсП. Если А некоторая алгебра подмножеств множества О (которое конечно или счетно), например, алгебра всех его подмножеств, то тройка (О,А,Р) представляет собой вероятностное пространство в широком смысле.

Определение (см. [11])

Индикатором множества В называется функция, равная единице во всех точках множества В и равная нулю во всех точках дополнения В (до

извольной оценки открытого текста х е X определим индикатор события 1) с П: 1) = {х = х0}, как следующую функцию:

[1, <=> X = х0 [О, о х Ф х0

Таким образом, индикатор события В позволяет сказать "да" если выбранная оценка открытого текста совпала с наперед заданным открытым текстом х0 еХ и сказать "нет" в противном случае.

'Я

произвольное значение которой может быть вычислено при помощи неко-

торой массовой задачи называется функция / (х), равная наибольшему

видуальным задачам данной массовой при объеме входных данных, выраженном значением х. При этом предполагается, что все входные дан-

Говорят, что алгоритм решения некоторой массовой задачи с ДМТГ-программой М имеет полиномиальную вычислительную (временную) сложность, если количество шагов работы ДМТ с программой М есть функция /(х) = 0(р(х)), где х—объем входных данных при фиксированной схеме кодирования, а р(х) есть, некоторый полином.

Определение

Если произвольное значение некоторой функции / может быть найдено при помощи ДМТ-программы, имеющей полиномиальную вычислительную сложность, то функцию / назовем р -эффективно-вычислимой.

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

1о1о2о Кргаттологотеоше структуры

С формальной позиции под криптологической структурой (крипто-струюгурой) будем понимать кортеж

(Х,¥,2,у,/^),\/уе¥,¥*0 Х,!/¥ = 0

все параметры которого определены выше (см. (1.1.1)).

Если 7^0, то множество ¥ можно записать как результат отображения /(х,г): X х 2 -» ¥ в следующем виде:

I7 = Гх = {7 е 7 : у = Дх, г), V* е 2}хеХ = 7Х, (1.2.2) таким образом, 7 = ¥х есть объединение множеств возможных (допустимых) криптограмм, по всем открытым текстам при отображении /. Тогда для всякого хе! кортеж

(х,¥х,2,Л (1.2.3)

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

(1.2.1)

Аналогичным образом множеству криптограмм 7^0 сопоставим результат отображения g(y,z}:Yx X и запишем это следующим образом:

X = Ху = {х е X : х = V* е г}уеГ = иуеГ Ху . (1.2.4) Тогда кортеж

(у,Ху,2,8) (1.2.5)

= 0 ' 1 ' '

где 1В (х) для \/хё1 представляет собой индикатор события О = {х = х0} в некоторым образом определенном вероятностном пространстве (определение см. выше). Криптоструктуры такого вида называем далее криптост-руюгурами с заданным индикатором. Если индикатор 1в(х) представляет собой р -эффективно-вычислимую функцию, то обозначаем его 8{П) и называем проверкой. Для соответствующей криптоструктуры говорим, что задана криптоструктура с проверкой. Введение индикаторов, очевидно, делает задачу раскрытия криптосистемы криптоаналитиком корректно поставленной (поскольку в этом случае существует единственное ее решение).

Относительно стратегий криптографа и криптоаналитика далее полагаем два возможных варианта.

Первый состоит в том, что криптограф некоторым образом задает открытый текст х0 (быть может, выбирая его из X совершенно случайным образом). Криптоаналитик в этом случае должен верно угадать заданный х0 е1. Тогда, очевидно, ¥=0. Таким образом, данная криптоструктура имеет единственное базовое множество — X. Состояние (неизвестное криптоаналитику) такой криптоструктуры есть пара (Х,х0). Если при этом задан индикатор /^(х) (доступный криптоаналитику), являющийся р -эффективно-вычислимой функцией, то можно дать следующее

В случае 7 = 0 для криптоструктуры (1.2.6) с проверкой (X, $(£>)), В = {х = х0} фиксированное ее состояние х0 е X назовем паролем, множество X представляет собой множество всех возможных оценок пароля.

Вторая стратегия заключается в том, что криптограф, выбирая некоторый открытый текст х0 еХ, при помощи секретного ключа е/ и отображения / образует криптограмму у е 7. Криптоаналитик, имея (или не имея) в распоряжении криптограмму у е 7, пытается восстановить х0 В этом случае 7 ф 0 и криптоструктура превращается в обычную криптосистему в смысле Шеннона. Если при этом задан индикатор 1В (х), являющийся р -эффективно-вычислимой функцией, то получаем криптосистему с проверкой„

Имея в распоряжении одну или несколько криптограмм одной криптосистемы, криптоаналитик может попытаться раскрыть криптосистему на основе анализа шифртекста (см. [!])„

В случае криптоструктуры (X, 8 (В)) в распоряжении криптоаналити-ка нет криптограммы, то есть вероятность события В = (х = х0} зависит только от распределения вероятностей на множестве X. В частности, если изначально некоторый пароль х0 выбирался (криптографом) из X совершенно случайно, то для любого хе1=>Р{х = х0} = — (равномерное

|Х|

распределение), и единственной стратегией раскрытия криптоструктуры в состоянии х0 является стратегия простого перебора. При этом полагаем, что для любого х е X существует р -эффективно-вычислимая функция 8 такая, что 8 (х) = 1 о х = х0 и 8(х) = 0 в остальных случаях.

По аналогии с обычными криптосистемами предположим, что такая криптоструктура находится одновременно в нескольких состояниях и для каждого определена проверка 8 . В этом случае криптоаналитик также не располагает криптограммой и при абсолютно случайной генерации паролей вынужден для подбора паролей использовать простой перебор на множестве X (например, множестве слов некоторого языка над конечным алфавитом А). Однако здесь могут возникать ситуации, значительно упрощающие задачу раскрытия такой криптоструктуры. Остановимся на этом моменте подробнее.

Истинный пароль /' -того входа есть фиксированное состояние х^, а все элементы х' е! есть оценки пароля хо (если $(х') = 0, то говорим,

что х' —ошибочный пароль). Например, если пароль хд есть двоичная последовательность фиксированной длины к, то все возможные его оценки включая *о > образуют векторное пространство У^ над полем GF(2).

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

Проверкой I-того состояния криптоструктуры (1.2.6) при ¥ = 0 назовем некоторую ДМТ-программу—процедуру, реализуемую на одно-ленточной ДМТ, входом которой является произвольный элемент х ■ из

некоторого множества Х\ а выходом элемент множества {хго,0} (здесь под 0 понимается пустое слово), кроме того определена следующая функция:

Последовательность значений этой функции ф = где J{í) <|Х'|

представляет собой управляющую последовательность в том смысле, что машина Тьюринга останавливается либо при 8 u{i)(xJ(i)) = 1Д ^ J{i) <| |, и

выход в этом случае есть хд, либо при 8 ц = 0,...,8.. =0, в этом случае на

(|Д |

выходе получаем 0. Очевидно, что выходом данной программы является 0 тогда и только тогда, когда хг0 &Хг.

Предположим, что т паролей выбираются с возвращением

из Х:\Х\ =п независимо и совершенно случайно. Событие В, заключающееся в том, что среди выбранных наудачу оценок паролей х1,...,хт хотя бы одна оценка совпадет с истинным паролем, то есть

В = {3/ е{!,...,м}:х; =х^} назовем раскрытием криптоструктуры (Х,8(В)).

Событие В) - (х-7 = х^} заключается в раскрытии ] -того состояния (пароля) криптоструктуры. Предположим, что для рассматриваемой криптоструктуры имеет место условие статистической независимости состояний, то есть для VI,у е{1,...,/»}:/' *] имеет место: P{Bi\Bj} = РЩ}. Опишем процедуру проверки такой криптоструктуры.

Сопоставим данной криптоструктуре т -ленточную машину Тьюринга Тт, каждая i -тая лента которой (г е{!,...,т}) соответствует i -тому входу-состоянию криптоструктуры. Проверкой криптоструктуры является программа МТт, вход которой есть вектор оценок, соответствующих состояний (x1,...,xw), i -тая компонента которого является входом для i -той ленты ( i е{!,...,m}).- j-тому шагу машины Тьюринга с программой МТт соответствует двоичный вектор

i -тая компонента которого есть соответствующая компонента управляющей последовательности i-той ленты, i <={\,...,т}. Тогда, очевидно, что событие D происходит тогда и только тогда, когда Е\j :wt(Sj)>l (здесь wt(t) подразумевает вес Хэмминга двоичного вектора t) и в этом случае наступает остановка машины.

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

Простейший криптоанализ описанной криптоструктуры возможен, в предположении, что она находится одновременно в т = п состояниях и все изначально выбранные пароли xo,...,xq* различны. В этом случае задача определения вероятности события D представляет собой задачу о совпадениях (см., например, [8]) или "задачу о встречах5' (см. [9]) на множестве X. В самом деле, поскольку подбор последовательности паролей в данном случае представляет собой произвольную перестановку на множестве X и все возможные перестановки (которых и!) предполагаются рав-новозможными (случайность выбора элементов if), то требуется найти вероятность того, что при произвольной случайной перестановке изначально упорядоченных определенным образом т= \Х\ элементов, хотя бы один остался на своем месте. Как известно, при от оо искомая вероятность

Рх

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

1ЛоЗ„ Криштдааиалитичтем© автоматы

Далее рассматриваем только такие криптосиситемы, которым сопоставляется индикатор 1В (х): 1В (х) = 1 о х = х0, выделяющий событие В = {х = х0}. Из результатов предыдущего пункта следует, что если заранее известны множества Х,1 и функция 1в(х) р-эффективно-вычислима, то можно построить вычислительное устройство, которая осуществляет процесс анализа произвольной криптограммы у е ¥ рассматриваемой криптосистемы. Опишем это устройство в виде автомата с конечным числом состояний.

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

Проверкой корректности построений могут служить совершенно-секретные (по Шеннону) криптосистемы. Согласно определению, вероятность нахождения истинного открытого текста в таких криптосистемах не зависит от имеющейся в наличии криптоаналитика криптограммы (см. [1]). Поэтому для криптоаналитического автомата должно иметь место следующее условие: вероятность раскрытия произвольной криптограммы совершенно секретной криптосистемы в произвольном фиксированном состоянии криптоаналитического автомата не должна отличаться от вероятностей ее раскрытия в предыдущих состояниях автомата, то есть должна оставаться постоянной в любом состоянии„

Если криптосистема допускает анализ открытого текста на основе криптограммы (не является совершенно секретной), то вероятность рас-

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

Определим процедуру проверки оценки открытого текста на одно-ленточной машине Тьюринга. Это ДМТ-программа М, входом которой является множество Ху возможных оценок открытого текста, соответствующее криптограмме у е 7, а выходом искомый открытый текст х0 еХу„ Причем для любого хеХу определена функция /£)(х):1) = {х = х0}, здесь предполагаем, что В с О, где (О, А, Р) некоторое вероятностное пространство, удовлетворяющее аксиоматике Колмогорова. Далее предполагаем, что такая функция р -эффективно-вычислима и обозначаем ее ¿>(х):

8(х) = {¿<=>х_х°. Условие х0 еХу говорит о том, что выходом программы М не может быть пустое слово, поэтому произвольной криптограмме у е¥ можно сопоставить множество значений функции {£>(х)}Х(гХу, которые образуют двоичную последовательность длины 1у : 81у (х1у) = 1, таким образом, 1у <|Ху| и V/ е {1,...,1у -1} => 8,(хг-) = 0, а выход М есть х1 =х0.

Сама процедура выбора и проверки может быть организована следующим образом. Предполагаем, что из множества секретных ключей 2 на каждом шаге выбирается оценка г е{!,..., 1у) истинного секретного

ключа 20 (то есть такого ключа, что у , ) = ) и вычисляется g{y,zi) = xi. Тогда оценкам секретного ключа , где =г0 соот-

у у

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

На первом шаге программы некоторого реалистического вычислительного устройства, раскрывающего криптограмму у е 7, образуется множество 21 = 2; затем на 2\ устанавливается некоторое отношение порядка т1 такое, что 21 обладает нижней гранью при тъ после чего нахо-

дится Множество 7* всегда можно выбрать конечной

мощности (в крайнем случае, оно всегда может состоять из единственного

*

при помощи соответствующих индикаторов). Если г0 £7*, то произвола ~ *

72 = 7\7* = 7^7^ и

юрядка Т1,...,Т]

1ъ...,11у : 2 = 7Т з 72 з... з 21у, где

= 7,7у = \

и соответствующие им оценки секретного ключа =

Из всего сказанного следует, что строго определить вычислительное

7

5 Г / ?

множествах 7у-. Обозначим г = иД17у, тогда множество 5 = {(2]-,т]-)}]-у=1

Ф{7-}, , г,- = т£ 7 ;) = ) = *,-,

а ф является функцией переходов:

, гу, г,-) = (7;>1, г/+1 )е5.

Таким образом, на каждом шаге автомат выдает некоторые оценки сек= ретного ключа и открытого текста. Конечное состояние определяется сле-

Зепа = (21у»%): Ф(г!у>%, % = ^ 21у) = g(y, г1у) = х0

Далее будем часто говорить о вычислительной сложности того или иного автомата А (понимая под этим, конечно, сложность соответствующей программы), сопоставляемого некоторой криптограмме у е Y. Поскольку все функции Ij)(x) предполагаются далее /»-эффективно-вычислимыми, то мерой сложности автомата А при заданной мощности множеств X,Z является число его шагов до момента остановки. Существенным является также следующее предположение: предположим, что

количество шагов автомата, затраченных на проверку гипотезы zQ е Z*, ограничено некоторым полиномом p{t), аргумент которого есть средний объем оценок секретного ключа при некоторой универсальной схеме кодирования. Например, если | Z* |= 1 (если каждое множество Z, вполне упорядочено, то | Z* |=1), то данное предположение справедливо в силу того, что индикатор события {zi =z0}—р-эффективно вычислимая функция, то же самое имеет место и для множеств Z* конечной мощности. Таким образом, общее число шагов реалистического вычислительного устройства, раскрывающего криптограмму, есть величина - 0(p(t> | S |), где S —множество состояний автомата.

12. Пространство исходов криптоаналитического автомата и общие подходы к оценкам стойкости криптосистем с

секретным ключом

Idolo Отшшшеним Егормдпш на мшшшстве секретных клшнеш

Рассматриваем криптосистемы в смысле Шеннона, в предположении, что существуют р -эффективно-вычислимые индикаторы IDx (х) и ID (г),

где Dx = {х = х0\у~j0},VxgX, Dz ={z = z0 ¡y = y0},VzEZ —события, заключающееся соответственно в истинном выборе открытого текста и секретного ключа при известной криптограмме (индикаторы ID (z) существуют и р -эффективно-вычислимы, если существуют и р -эффективно-вычислимы индикаторы Id (х) и функция g(y,z) р -эффективно вычислима для любых z е Z). В таких криптосистемах произвольной крипто-

грамме у g Y сопоставляется построенный в предыдущем пункте автомат А.

Предположим, выполненной аксиому выбора (Цермело) и, соответственно, справедливой теорему Цермело о полном упорядочении произвольного множества (см. [10]). Сопоставим каждому множеству 51 множество всех возможных на нем отношений полного порядка Т^. Если два элемента 91 сравнимы по т обозначаем это символом -<г. Покажем, что имеет место следующее утверждение.

Список литературы диссертационного исследования кандидат технических наук Семенов, Александр Анатольевич, 1998 год

ЛИТЕРАТУРА

[1] Шеннон К. Э. Теория связи в секретных системах. В кн.: Шеннон К.Э. Работы по теории информации и кибернетике. М.: ИЛ, 1963, с. 333=402.

[2] Шеннон К. Э. Математическая теория связи В кн.: Шеннон К.Э. Работы по теории информации и кибернетике. М„: ИЛ, 1963, с. 243-332.

[3] Месси Дж. Л. Введение в современную криптологию. ТИИЭР, т. 76, 1988, с. 24-42.

[4] Феллер В. Введение в теорию вероятностей и ее приложения, т.2 М.: Мир, 1984. 751с.

[6] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. "Мир" 1982. 416с.

[7] Левенштейн В.И. Элементы теории кодирования. В кн. Дискретная математика и математические вопросы кибернетики, под общ. ред. С.В. Яблонского и О.Б. Лупанова. М. "Наука" 1974. с. 207-305.

[8] Боровков А. А. Теория вероятностей. М.: "Наука", 1976.

[9] Сачков В. Н. Комбинаторные методы дискретной математики. М. : "Наука", 1977.

[10] Ван дер Варден Б.Л. Алгебра. М. "Наука" 1976. 623с.

[11] Феллер В. Введение в теорию вероятностей и ее приложения, т.1 М,: Мир, 1984. 527с.

[12] Брикелл Э. Ф., Одлижко Э. М. Криптоанализ: Обзор новейших результатов. ТИИЭР, т. 76, 1988, с. 75-94.

[13] Гнеденко Б.В. Курс теории вероятностей. М.: Наука, 1988.

[14] Штарьков Ю. М. Некоторые теоретико-информационные задачи защиты дискретных данных. // Нробл. передачи информ. 1994. Т. 30. № 2. С. 49-60.

[15] Simmons G. J. , "Authentication theory/coding theory" , in Advances in Cryptology, Proceedings of CRYPTO 84, G. R. Blakley and Chaum, Eds. Lectures and Notes in Computer Science, No. 196 New York, NY: Springer, 1985, pp. 411-431.

[16] МакВильямс Ф. Дж., Слоэн H. Дж., Теория кодов, исправляющих ошибки. М., "Связь", 1979.

[17] Griesmer I. Н. A bound for Error-Correcting Codes // IBM J. Res. And Develop. 1960. V. 4 № 4. P. 532-542.

[18] Haniada N. Characterization resp. nonexistence of certain q-ary linear codes attaining the Griesnier bound, Bull. Osaka Women's Univ. 22 (1985) p. 1-47.

[19] Hellman M. E. An Extension of the Shannon Theory Approach to Cryp-tology //ШЕЕ Trans. Inform. Theory. 1977. V. 23. № 3. P. 289-294.

[20] AMswede R. Remarks on Shannon's Secrecy Systems // ProbL Control and Inform. Theory. 1982. V. ll.№4. P.301-318.

[21] E. N. Gilbert, F. J. Mac Williams and N. J. A. Sloane, Codes with detect deception, Bell Syst. Tech. I., 53 (1974) 405-424.

[22] Бассапыш Л. А., Бурнашев M. В. Оценка максимального числа собщений при заданной вероятности успешной подмены. // Пробл. передачи информ. 1994 Т. 30. № 2. С. 42-48.

[23] Бассалыго Л. А. Нижние границы для вероятности успешной подмены сообщения. // Пробл. передачи информ. 1993. Т. 29. № 2. С. 104-108.

[24] I. L. Massey, "Cryptography—A selective survey," presented at Intl. Tirrenia Workshop on Digital Communications, Tirrenia, Italy, Sept. 1-6,1985; in Alta Freq., vol. LV #1, pp. 4-11, jan.-Feb. 1986.

[25] P. D. Merillat, "Secure stand-alone positive personnef identity verification system (SSA-PPIV)," Sandia National Laboratories Tech. Rep. SAND79-0070, Mar. 1979.

[26] C. EL Meyer and S. M. Matyas, Cryptography: A New Dimension on Computer Data Security. New York, NY: Wiley, 1982.

[27] M. O. Rabin, "Digitized signatures and pubic-key functions as intractable as factorization," M.l.T. Lab. for Computer Science, Tech. Rep. LCS/TR-212, 1979.

[28] R.A. Rivest,A. Shamk.and L.Adleman, "A method for obtaining digital signatures and public-key cryptosystems," Common;^i^. Comput. Mac/)., voi. 21, no. 2, pp. 120-126,1978.

1985, pp. 47-53.

[31] G. j. Simmons and D. B. Holdridge, "Forward search as a cryptanalytic tool against a public key privacy channel," in Proc. IEEE Computer Soc. 1982 Syrnp. on Security and Privacy, (Oakland, CA), pp. 117-128, April 26-28,1982.

IEEE Computer Soc. 1983 Symp. on Security and Privacy, (Oakland, CA), pp. 61-66, Apr. 25=27,1983.

[33] G. J. Simmons, "A system for verifying user identity and authorization at

Piehler, Ed. W: Berlins Springer-Verlag, 1986, pp. 261-272.

G. I. Simmons, "Authentication codes that permit arbitration," presented at

j

the

s, Graph Theory

Boca Raton,-FL, Feb. 23-27, 275-290, Mar. 1988.

receiver disputes," presented at Eurocrypt'87, Amsterdam, The Nether 13-15,1987; to appear in Advances in Cryptotogy, W. L. Price

11,

[37] G. I. Simmons, "A natural taxonomy for digital information authentication

CA, Aug. 16-20,1987; in

I J.

11:

=V<

il r.-Hiri iP

GA.Aug. 16 [41] H. C.

procedure," IEEE Trans. Informal. Theory, vol. IT-26, no. 6, pp. 726-729, Nov.

[42] Симмонс Г. Дж. Обзор методов аутентификации информации // т. 76, 1988, с. 105-125.

/

[43] Симмонс Г. Дж. Как обеспечить доверие к данным, используемым при проверке соблюдений договоров // ТИИЭР, т. 76, 1988, с. 126-133.

[44] Solomon G., Stiffler I. X Algebraically Punctured Cyclic Codes // Inform and Control. 1965. V. 8. № 2. P. 170-179.

[45] Белов Б. И., Логачев В. Irl, Сандимиров В. П. Построение класса линейных двоичных кодов, достигающих границы Варшамова - Грайсмера // Пробл. передачи информ. 1974. Т. 10. № 3. С. 36-44.

[46] Логачев В. Н. Новые достаточные условия существования кодов, достигающих границы Варшамова - Грайсмера //Пробл. передачи информ. 1986. Т. 22. № 2. С. 3-26.

[47] Логачев В. П. О характеризации и условиях существования кодов, достигающих границы Варшамова - Грайсмера // Пробл; передачи информ. 1988. Т. 24. № 3. С. 24-41.

[48] Helleseth Т. Further Classification of Codes Meeting the Griesmer Bound // IEEE Trans. Inform. Theory. 1984. V. 30. № 3. P. 395-403.

[49]. Helleseth T. A Characterization of Codes Meeting The Griesmer Bound // Inform and Control. 1981. V. 50. № 2. P. 128-159.

[50] Семенов А. А. О существовании некоторых линейных кодов размерности 3 над GF(q), q>4, достигающих границы Грайсмера // Компьютерная логика, алгебра, и интеллектное управление, сб. трудов Всероссийской школы т.4 С. 215-229, Иркутск 1995.

[51] Семенов А. А. Справедливость гипотезы о кодах с максимально-достижимым расстоянием над GF(q) для некоторых новых значений q // Методы оптимизации и их приложения, 10-я Байкальская школа-семинар, тез. докл. С. 120-121 Иркутск 1995.

[52] Семенов А. А. О линейных кодах над GF(q), достигающих границы Грайсмера // Функционирование региональных рынков: поиски, проблемы, решения, тез. докл. Международного симпозиума, Иркутск 1995.

[53] Семенов А. А. К вопросу нестойкости некоторых криптосистем // Материалы городской конференции молодых ученых, тез. докл. С. 43=44. ИПГЭА. Иркутск 1998.

[54] Семенов А. А. О существовании нестатистических алгоритмов сжатия дискретных данных // Методы оптимизации и их приложения, труды 11 Международной Байкальской школы-семинара, т.З, С. 170-174, Иркутск, 1998.

[55] Семенов А. А. Вычислительная сложность криптосистем с секретным ключом // препринт, изд. ИГЭА, Иркутск 1998, 33 с.