Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

253

=|хнАг+ (\А|-1 |) |А-1[|хр|Аг-1 ] (Аг'охнАг1—I)1.

Таким образом,

Е(|83|)=|хр|А|^+ (I А |-1 |) |А г'[|ХйАг-1] (Аг'ОХцАг'-о-'+ос^г1).

Окончательный результат получается подстановкой этого значения в полученную ранее формулу

■ Е Т = |Х |]Г е ^ |. ,

1=о

Опробование в методе использования гомомор­ физмов

Напомним сначала основйые понятия, связанные с определением гомо­ морфизма автоматов.

Пусть А=(1а,8а,Оа, (5,Л)161,((3,А)|е|) и В=(1в,8в,Ов, (5,в);е 1,СР1В)1еО два

автомата. Тройку сюрьективных отображений (ц/,ф,г|) \|/: 1д—>1в> ф:§А—>§в; грОд—>Ов

называютгомоморфизмом автомата А на автомат В, если для любых 1е1А, зе8А выполняются следующие равенства:

ф61А3=6у1Вф8,

Г1Р1А8=Ру®ф8.

Автомат В в этом случае называют гомоморфным образом автомата А. Если отображения (\|/,ф,г|) биективны, то гомоморфизм называют изоморфизмом ав­ томатаА на автомат В.

Следующее, легко проверяемое исходя из определения гомоморфизма, утверждение является основой для построения методов определения начально­ го состояния автомата А по его входной й выходной последовательностям.

УТВЕРЖДЕНИЕ. Пусть 3=1(1),1(2),...,1(Ь) - произвольная входная по­ следовательность автомата А, 8 - произвольное его начальное состояние, А($,3)=У=у(1),у(2),...,у(Ь) - выходное слово автомата А, отвечающее его на­ чальному состоянию зе8А и входному слову 3, а (ф,ф,г|) - гомоморфизм А на В.Тогда выходное слово В(ф8,\|/3) автомата В, соответствующее его начально­ му состоянию фзе8в и входному слову фЗ=\|л(1),ф1(2),..,,ф1(Ь) есть

В(ф8,\]/3)= г|у(1), туу(2),..., г|у(Ь)

Рассмотрим задачу определения начального состояния 8 автомата А по известным входному слову ЗеГ1"и выходному слову А(з,3)=У, то есть задачу нахождения решений зеЗд уравнения А(з,1(1),1(2),...,1(Ь))=у(1),у(2),...,у(Ь).

ч254

При этом предполагаются известными автоматы А, В и гомоморфизм (ф,ф,г|) А на В.

На основании сформулированного выше утверждения исходную задачу для автомата А можно редуцировать в аналогичную задачу для автомата В, именно будем искать все решения ф8бЗв уравнения

В(ф§, ф1(1),ф1(2),...,\|/1(Ь)= цу(1), г|у(2),..., г|У(Ь)- Цель такой редукции заключается в том, что автомат В может иметь

более простое строение, чем автомат А (например, иметь меньшее число со­ стояний, или быть линейным). Поэтому для него задача определения начально­ го состояния может решаться проще (с меньшей трудоемкостью), нежели ис­ ходная задача. Однако при такой редукции теряется часть первоначальной ин­ формации, так как произошла замена последовательностей 3, У на последова­ тельности фЗ, г)У. В этой связи в результате редукции йсходная задача реша­ ется с дополнительной многозначностью, то есть получаются лишние решения. Для того чтобы их отбросить, надо снова использовать первоначальную ин­ формацию. Поэтому, найдя все решения 8(фЗ,г|У) уравнения В(ф8,ф1(1),ф1(2),...,У|п(Ь)==г|у(1), г|у(2),..., г|у(Ь), а затем все состояния 8еЗА, для которых ф8б5(фЗ,1]У), следует проверить, какие из этих состояний являются решениями первоначального уравнения

А(8,1(1),1(2),...,1(Ь))=у(1),у(2)„.,,у(Ь).

При расчете трудоемкости данного метода будем использовать сле­ дующие предположения: каждое из рассматриваемых уравнений

А(8,1(1)Д2),... Д(Ь))=у(1),у(2),... ,у(Ь),

В(ф8, ф1(1),1|/1(2),...,1|/1(Ь)= ЛУ(1), Т1У(2),—, ЛУ(Ь)

имеет единственное решение; нахождение решения второго уравнения прово­ дится тотальным методом; не учитывается трудоемкость определения всех ре­ шений ф 'вв уравнения ф8=8В, а последующий отсев этих решений проводится тотальным методом в автомате А.

Трудоемкость метода гомоморфизма слагается из трудоемкости опре­ деления решения 8В уравнения

В(ф8, \|п(1),\|п(2),...,\|л(Ь)= ЛУ(1), ЛУ(2),-.-, ЛУ(Ь),

ваний состояний 8€ф_18В в уравнении

А(8,1(1),1(2),...,1(Ь))=у(1),у(2),...',у(Ь),

которое равно — (|ф_,8В н-1|).

255

При необходимости общую трудоемкость метода усредняют по воз­ можным значениям |ф-18в|, а также рассчитывают ее в менее жестких предпо­ ложениях.

. Опробование в методе встречных атак для опре­ деления начального состояния последовательного соединения автоматов

Рассмотрим задачу определения состояний 31,52 последовательного сое­

динениядвух автоматов А1=(1(1),8(1),0(1),81,р1) и А2=(1(2),8(2),0(2),82,р2), 0(1)=1(2) по известному входному слову Зе1(1)ь и выходному слову УеО1",

0(2)=О.

Будем предполагать, что автомат А(2) обратим, то есть по его началь­ ному состоянию и выходному слову можно однозначно определить его входное слово.

Разобьем слова 3=1|,12,...,1ь У=уьу2,...,уь на отрезки длины I, V, Ь-1-у.

3=30)3(2)3(3); 3(1)е1(1)*, 3(2)е1(1)у, 3(3)€1(1)ы-у; У=У(1),У(2),У(3); У(1)еО', У(2)еОу, У(3)еОы‘у.

Алгоритм решения задачи состоит из трех этапов, которые проводятся для каждого слова МД1 )=21,22,...,2, из 0(1)*.

На первом этапе для слова 2( 1 )=2!,22,... ,2, и каждого )€ 1,1 последовате­

льно строят множества 81(11,12, 22,...,2!)={з(1): з(1)б 8(1), А1(з(1),

• •,!)) 2],22,.. >,2)}.

Для чего при слове 21,22,...,2, проводят последовательное опробование $(1)еЗ(1). Опробуя все состояния з(1)еЗ(1), находят множество 8 (;г(), опро­ буя состояния из 81(1ь2,), находят 81(11,12;2|,22) и так далее до определения множества 81(3(1),2 (1)), для чего требуется провести

Т,(А,)= |3(1)|+|81(1ь21)|+...+ 181(119..*,1(-1>2,,...,2^_()|

опробований (на один такт работы автомата). Далее для каждого 8е81(3 (1 ),2 (1)) при данном 2 (1) вычисляют 2 (2)еО (1 )у, именно

А.(з,3(1),3(2))=2(1),2(2)

и по адресу 2(2) записывают з в память П. Трудоемкость этой части алгоритма есть

Т2(А,)=|3.(3(1),2(1))|(1+у)+|31(3(1),2(1))|, где первое слагаемое является трудоемкостью вычисления адресов, а второе -

число обращений к памяти П. Поэтому для фиксированного 2(1) общая трудое­ мкость первого этапа алгоритма есть величина Т1= Т1(А1)+ Т2(А1).

256

Второй этап аналогичен первому. Для данного слова 2 ( 1)=2Ь22,...,2( по­

следовательно находят множества Зг^ьу,), 32(21,22;уьу2),..., 52(2(1);У(1)),

где 32(2ь...,^;уь...,у])={5(2):8(2)еЗ(2),А2(8(2),21,...,^)=уь...,Уз}. Для нахожде­

ния этих множеств потребуется провести Т,(А2)=|3(2)|+| 82(2ьу,)|+...+|32(2,,...,2м;у1,...,у,-1)|

опробований на один такт работы автомата А2. Для каждого з(2)е82(2(1);У(1)) вычисляют 2 (2)

А2(з(2),2( 1),2(2))=У(1),У(2),

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

Т2(А2)=|32(2( 1 );У(1)|0+у)+ 152(2( 1);У(1))|, и суммарная трудоемкость второго этапа есть Т2= Т|(А2)+ Т2(А2).

На третьем этапе совокупность пар (з(1),8(2)), содержащихся в каждой адресной ячейке «согласуют» на оставшемся материале. Именно, для каждой пары (з(1),з(2)) опробованием проверяют выполнение равенства

А(з(1),з(2), 3(1),3(2),3(3))=У(1),У(2),У(3), которое по определению пар (з(1 ),з(2)) может не выполняться лишь на послед­

них Ь-1-у тактах работы последовательного соединения А=А,-»А2 автоматов

А), А2. Трудоемкость такой проверки в числе опробований (на один такт) равна

Тз=|3(3(1),3(2);У(1),У(2))|(1+у+1)+|8(1,,...,11+у+1.;Уь...,У1+у+1)|+...

...+|30ь...,1ц;у.,...,Уи)|-НЗ(3(1),3(2);У(1),У(2))|, где 8(11,...,^;у1,...,у}) - множество пар (8(1),з(2))е 8( 1)х8(2), для которых

А(з( 1),з(2),11,... ,^)=у1,... ,у).

Последнее слагаемое в формуле для Тз учитывает обращения в память П. Общая трудоемкость трех этапов при фиксированном 2(1)еО(1)‘ есть

Т(2(1))=Т1+Т2+Тз. Все три этапа алгоритма проводятся для каждого 2(1)е0(1)‘. Поэтому общая трудоемкость метода есть

Т==|0(1)|* Т(2(1)).

При необходимости оценивают среднее значение Т, исходя из возмож­ ных значений параметров З^ ьЬ ,...,^ 2Ь22,...,2|), 52(2|,...,2^у|,...,у}), 3(1,, ...,1];уь...,у|).

257

Параграф 5.4 Принципы построения статистических методов

криптоанализа.

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

Ниже под моделью А* автомата А мы понимаем некоторый новый ав­ томат, позволяющий с помощью А* решать поставленную для А задачу. Обыч­ но эти автоматы зависимы и А* имеет некоторые количественные характерис­ тики «похожести» на А.

1. Рассмотрим задачу восстановления ключа х=(ХьХ2) по известной выходной последовательности А(х)=уьУ2>-"Уь--- шифрующего автомата А с помощью

построения его модели А*.

Пусть модель А* шифрующего автомата А такова, что ее выходная по­ следовательность при произвольном ключе х=(ХьХг) зависит только от первой части XI ключа и при случайно и равновероятно выбранном ключе х=(ХьХг)

между последовательностями

А(Х 1 ,Х 2 )= У 1 ,У 2 ,...,У Т ,

А*(х0 =У*1,У*2,...,У*т

имеется кореляционная связь, а при ключах вида х=(ХьХ2) и X 1^X1 такой связи

в последовательностях

А ( х ь Х 2) = У ь У 2,...,У т ,

А*(Х'0 =У'ьУ'2,...,У'т

не проявляется.

а). Один из способов нахождения истиной части Х\ ключа %по выходной по­ следовательности А(хьХг) состоит в опробовании вариантов х' 1 в А*, т. е. вы­ числении последовательности А*(х' 0=у' |,у'г>- • -,У т для каждого варианта х'1 и

ввыявлении статистическим методом корреляционой зависимости между А(ХьХг) и А*(хО при истинном варианте б). Пусть при истиной части Х1 ключа х=(ХьХг) последовательности А(хьХг),

А*(хО близки по Хэммингу. Предполагаем, что такой близости нет при ложной части Х1 ключа х=(ХьХг)- В этом случае задачу определения истиной части %\ ключа можно свести к решению уравнения А*(хО =у*ьУ*2>--->У*т с искажен­

ной правой частью, а записав это уравнение в координатной форме, - к реше­ нию системы уравнений

258

Ф*.(Х1)=У*., 1е{1,...,Т}

сискаженной правой частью уьу2,...,ут(см.параграф 5.5).

2.Рассмотрим задачу определения части %\ ключа х=(ХьХ2)^К1хК2 из уравне­ ния Ф(ХьХ2)=У, где Ф: К1ХК2—>У, уеУ. Предположим, что она решается мето­ дом частичного опробования. Именно, опробуются все варианты х'1 €К( и для

каждого варианта проверяется разрешимость уравнения Ф(х ьХг)=У относите­ льно %2-

Положим: У'(Х1)= {У=Ф(ХьХ2)-’ (ХиХг)^ {XI}ХК2) и введем индикаторную

функцию:

В этих обозначениях критерий разрешимости уравнения Ф(х ьХг)=У относительно %2описывается логическим правилом

,Х'(ХьУ)=0 ■=> XI —ложный вариант,

Х'(ХьУ)=1 => XI —истиный вариант.

Поиск эффективного критерия разрешимости уравнения Ф(х ьХг)=У в веденных терминах сводится к поиску «легко» реализуемых алгоритмов вы­ числения индикаторной функции или, что то же самое, к конструктивному описанию множеств У'СхО, Х^^ч.

Нередко, ввиду сложности отображения Ф, найти индикаторную функ­ цию не удается, т.е. не удается конструктивно описать множества У'(Х|)>

XIеКр Чтобы обойти эту трудность, обычно пытаются аппроксимировать мно­ жества У'(хО, XI некоторыми «хорошими» множествами У(хО, Х1е Кь Если

такие множества найдены, то опробование вариантов XIеК] проводят на основе вычисления значения новой индикаторной функции

«*,*>-{ *• во"-увУ<ь>.

О, если уёУ С хО

Естественно, при использовании аппроксимаций в принятии решения по пра­ вилу

могут возникать ошибки. Далее процедуры такого вида будут называться X- процедурами (Х-критериями).

Характеристики Х-процедур. Пусть значение у(0)=Ф(х(1),х(2)) полу­ чено при неизвестном ключе (х(1),х(2))- Будем определять часть ключа х(1) с помощью Х-процедуры. Оценим эффективность метода определения части

260

Теорема. При любой Х-процедуре и любой мере Р на К параметры л=Р{(х(1)6 (Хь МХь у(0))=1} - надежность Х-процедуры и ЕХ - средняя мощ­ ность множества {%\. Х(Хь у(0))= 1} при случайном и равновероятном выборе части ключа Х(1)еК] выражаются через ошибки а и р критерия (Т(0),Т(1),Х)в виде

я=1-а, Е(Х)=|К1|[(1-а)|К,Г1+р(1-|К1Г1)].

ДОКАЗАТЕЛЬСТВО. Функция

■МхьуИ 1- если-у еУ (5 " )

0, если уёУ С хО представляет собой индикатор события

XIе (Х ь ^-(Х 1>У(0))= 1}

и поэтому я=1-а.

Далее заметим, что

КХС Х(Хь у(0))= 1}|=| {XI: ЧХи Ф(х(1),Х(2)))=1}|=Х Х(Х„ Ф(Х(1),Х(2)))=

XI

=[К,| Е(Х0( Х(Х|, Ф(Х(1),Х(2)))),

где Е(Х1)(Х(Х1,Ф(Х(1)»Х(2)))) - среднее значение случайной величины Х(ХьФ(Х(1),Х(2)) по возможным значениям Х1бК1 при равномерной мере на К!

(вероятность события: Х(ХьФ(Х(1),Х(2)))=1 при случайном равновероятном вы­ боре Х1?К1 при фиксированном (Х(1),Х(2))еК).

Усредним теперь значения |К1|Е(Х|)( Х(Хь Ф(Х(1),Х(2))) по всем

(Х(1),Х(2))еК. Получим (будет использована теорема Фубини):

ЩХ)=Е (|{Х1: Х(Хь у(0))=1}|)=|К,| Е(ХьХ(1),Х(2))(Х(ХьФ(Х(1),Х(2)))), где Е(Х|,Х( 1),Х(2))(Х(Х1,Ф(Х(1),Х(2)))) - среднее значение случайной величины (Х(ХьФ(Х(1),Х(2))) при равновероятном выборе Х1еК 1 и случайном выборе (Х(1),Х(2))еК с распределением Р(Х), ХеК 1хКг. Другими словами, величина

Е(Х1,Х(1),Х(2))(Х(Х|,Ф(Х(1),Х(2))))

есть вероятность Р события: Х(Х|,Ф(Х(1),Х(2)))=1. Из определений ошибок а, р по формуле полной вероятности непосредственно получаем

/М 1-а)|К 1Г1+ р(1-|К1Г').

Таким образом, ^-процедуры можно описывать на языке математиче­ ской статистики.

Построение таких статистических процедур нахождения части ключа Х(1) из уравнения у(0)=Ф(х(1), %(2)) нередко проводят по следующей общей

схеме.