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

231

но хороша ложка к обеду! В ряде случаев не полученная вовремя информация теряет свою ценность. Так, сведения о погоде, о временных дорогах и перепра­ вах и т. д. теряют свою ценность по истечении определенного времени. Учет «старения информации» может быть проведен аналогично учету порчи про­ дуктов питания на овощных и продовольственных складах, аналогично учету старения словарей, т. е. учету не используемых слов из старых словарей. Такой учет может проводится по так называемому правилу «постоянного процента», Щ1)=и(0)ед' , здесь 11(0) - начальное количество «продукта», 11(1) - количество

«продукта» через I единиц времени. Эту же формулу иногда записывают в виде Щ1:)=11(0)(1- а)‘, а - коэффициент старения 0<а<1 .

Параграф 5.2 Принципы построения методов определения ключей

шифрсистем .

Пусть (Х,У,К,1) - модель шифра по К. Шеннону. Рассмотрим задачу определения ключа х^К по известным открытому х и соответствующего ему шифрованному у текстам, то есть задачу нахождения решения %уравнения

Г(х,х)=у Частным случаем этой задачи является задача определения ключа х по

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

А(х)=у.

К решению уравнения вида

Ф(х)=У,

(где Ф: К—»У), сводится и первая поставленная задача. Действительно, так как С ХхК—»У, то при фиксированном хеХ индуцируется отображение Ф=ГХ: К—»У, Ф(х)=Г(х,х).

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

Ф(х)=У-

В ряде случаев такие уравнения записываются в «координатной фор­

ме»:

Ф.(ХьХ2,..-,Хп)=У., *е{1,...,Т}.

Здесь: Ф„ 1е {1,...,Т} - координатные функции функции Ф, Х=(ХьХ2,---,Хп)> У=(УьУ2,-..,Ут).

232

О бщ ая к о н ц е п ц и я р е ш е н и я ук а за н н о й задачи сост оит в сведении ее к более прост ы м задачам , р еш а ем ы м и зве с т и вш и («базовим и») а лго р и т ­ м ам и .

Ниже дается краткое описание базовых алгоритмов и методов сведения

к ним.

Базовые алгоритмы: алгоритмы поиска, алгоритмы решения систем линейных и нелинейных уравнений над различными алгебраическими структу-

^рами (поля, кольца и т. д.), итерационные методы.

Каждый базовый алгоритм, как и метод сведения к нему, содержит ши­ рокий круг разнообразных методов, связанных собственной «иерархией». Ниже приводится их краткая характеристика.

Алгоритмы поиска. Любой алгоритм нахождения решения х' уравнения

Ф(х)=У представляет собой последовательность действий на основе системы тестов и

может быть описан как алгоритм поиска элемента % в массиве К. В криптогра­ фической литературе под алгоритмами поиска нередко понимают узкий класс алгоритмов поиска - метод последовательного перебора (метод тотального опробования), в соответствии с которым опробуются поочередно в некотором порядке элементы %множества К. Для каждого опробуемого варианта %вычи­ сляется ух=Ф(х) и сравнивается с у по критерию на совпадение. При принятии решения о несовпадении ух с у опробуемый вариант %отбраковывается. При известной структуре (частичной структуре) множества К применяют «упорядо­ ченный», «направленный» перебор элементов из К. Так, например, при струк­ туре множества «больше - менше»:

У1 <У2<* •*<У|К|

для нахождения номера заданного элемента у сравнивают у со «средней точ­ кой» у[|Г2|/2] массива и выбирают ту половину его, в которой лежит у, затем •

сравнивают у со «средней точкой» выбранного «половинного массива» и так далее до идентификации элемента у. Число операций такого способа оценива­ ется величиной 1о§2К. Иногда удается сгруппировать элементы массива в «лег­

ко различимые» между собой группы и вначале определять номер группы, в . которой лежит у, а затем определять номеру, ведя поиску в этой выделенной группе. Сократить число операций при структуре ключей «больше - меньше» возможно, если использовать предварительную кодировку у-ов и «удобно» расположить у-ки в соответствии с их адресами (см. Зубков А.М., Клыкова Н.В. Построение баз данных с ограниченным временем поиска. Симпозиум по прикладной и промышленной математике. Тезисы доклада. 2001 г., стр. 185186).

233

Характерной особенностью алгоритмов поиска является то, что струк­ тура отображения Ф фактически не учитывается (возможно учитывается лишь дляпредварительного группирования элементов массива V).

Алгоритмы решения систем линейных и нелинейных уравнений над раз­ личными алгебраическими структурами (поля, кольца и т.д.). Для решения си­ стемлинейных уравнений в этих структурах существует широкий круг извест­ ных «стандартних» алгоритмов, таких как - алгоритмы Гаусса, Штрассена, Коновальцева для решения общих систем линейных уравнений над конечными полями и кольцами; алгоритмы решения некоторых специальных систем ли­ нейных уравнений - например, ганкелевых систем или систем с разреженной матрицей. Из алгоритмов решения систем нелинейных уравнений отметим ал­ горитм Лазера.

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

Методы частичного опробования. В методах этого класса пытаются «разбить» ключ х на две части хьХ2 и представить его в виде х=(ХьХг) таким

образом, чтобы при каждом варианте уравнение Ф(ХьХг)=У относительно %2 решалось достаточно «просто», например, с трудоемкостью меньщрй, чем по­ лный перебор возможных значений %2. При выполнении этих условий решают уравнение Ф(ХьХ2)=У перебором возможных вариантов х '1 с последующим ре­

шением уравнения Ф(х'ьХг)=У Для каждого опробуемого варианта х'ь Приме­ ром такого метода служит метод решения нелинейных булевых уравнений пу­ тем линеаризации за счет опробования части переменных.

Методы последовательного опробования. Этот метод является развити­ ем метода частичного опробования. В этом методе также пытаются «разбить» ключ х на две части хьХг и представить его в виде х=(ХьХ2) таким образом, чтобы при каждом варианте для уравнения Ф(хьХ2)=У относительно %2до­

статочно «просто» устанавливалось, разрешимо оно или нет. Если при варианте X I оно неразрешимо относительно %2, то вариант % \ отбраковывается и опро­ буется следующий вариант. В случае же положительногр ответа уравнение Ф(ХьХг)=У пытаются решить всеми возможными средствами, например, пы­ таются применить метод частичного опробования для части %2, всего ключа х- В последнем случае и говорят о применении метода последовательного опро­ бования.

234

Методы сведения к базовым алгоритмам основаны:

—на преобразовании как уравнений, так и множества неизвестных; на исполь­ зовании различных моделей алгебраических структур (гомоморфные образы автоматов, алгебр, их приближенные модели и т. д.);

—на использовании частичного и последовательного опробования.

Неизвестные параметры ХьХ2>--->Хп - части ключа %, относительно ко­

торых решается уравнение, могут быть заданы в различной форме, влияющей как на выбор способов решения уравнения, так и на их сложность. Так, напри­ мер, подстановка может быть задана в обычной двухстрочной форме, или в ма­ тричной форме; двоичная функция может быть задана таблично, в виде много­ члена Жегалкина, в виде вектора ее коэффициентов Фурье по любому базису 11-

мерного векторного пространства над полем вещественных чисел или над ко­ нечным полем и т. д. Собственно сам метод сведения к базовым алгоритмам и состоит в выборе способа представления, «кодирования» частей ключа.

Преобразования уравнений шифрования. Многие методы преобразова­ ния системы уравнений шифрования нацелены на получение уравнений - след­ ствий, которые могут быть решены известными способами. Например, подби­ рают множество У' совместно с отображением (р: У-»У' так, чтобы новое уравнение-следствие

ф( ф (х))=ф(у)

решалось достаточно просто. Найдя все множество М решений этого уравне­ ния, решают, относительно /еМ , начальное уравнение Ф(%)=у, например, оп­ робуя элементы множества М. К таким методам относятся так называемые «методы сведения»: выделение из системы уравнений

Ф.(ХьХ2,...,Хп)=у(, *е{1,...,Т}

«хороших уравнений», например линейных, или выделение уравнений, из ко­ торых можно составить систему уравнений «треугольного типа» и т. д.

Преобразование неизвестных. Один из способов преобразования неиз­ вестных состоит в поиске нового множества К' и отображений ср: К—»К', \р: К'-»У так, чтобы Ф(х)=Н/(ф(х))- В этом случае задача поиска решения уравне­ ния Ф(х)=У сводится к решению двух уравнений

ф(х')=у.

ф(х)=х'-

При таком сведении задачи поступают следующим образом. Находят все реше­ ния % первого уравнения, а затем решают второе уравнение для каждой правой части найденной ранее. Типичным примером преобразования неизвестных при решении системы нелинейных уравнений является введение новых пере­ менных, приводящих систему уравнений относительно этих новых переменных к системе линейных уравнений.

235

Методы использования гомоморфизмов. Итак, мы изучаем возможно­ сти определения прообраза %отображения Ф: К—»У по известному образу

У=Ф(Х)- Ищутся такие подходящие множества К' и У’ и отображения ср: К—>К',

\|/:У->У', РК'—»У', чтобы была коммутативна следующая диаграмма:

к	ф
	-> У
ф -1	1	ф
К'	У'

Сначала решается уравнение Дх )=У >относительно % еК' при у'=ф(у). Это уравнение называют гомоморфным образом уравнения Ф(у)=у.

Затем для каждого найденного решения % решается уравнение ф(х)=Х • Обоз­ начим через М все найденные таким образом решения (объединение всех ре­ шений уравнения <р(х)=х' по всем решениям х' уравнения С(х )=У)- Далее решают начальное уравнение Ф(х)=У относительно х^М.

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

Наряду с использование базисных алгоритмов и методов сведения к ним при решении задачи определения ключа нередко используют и дополните­ льные предположения, облегчающие расчет параметров эффективности испо­ льзуемого метода решения. Например, предполагают, что решение уравнения Ф(Х)=У единственно, в частности, используемый шифр не имеет эквивалентных ключей, объем Т материала больше расстояния единственности шифра.

Параграф 5.3 Методы опробования

Тотальный метод

Пусть А - шифр с алгеброй шифрования (Х,КШ,У,Г), алгеброй расшиф­ рования (У,Кр,Х,Р) и уеУ - известный шифрованный текст, полуденный при зашифровании некоторого содержательного открытого текста х0 при неизвес­

236

тном ключе Хое Кш. Задача состоит в нахождении открытого текста х0, т.е. в решении уравнения Г(х0, х 0) = У относительно х0при известном у и известном

шифре А. Одним из методов решения этого уравнения для известного симмет­ ричного шифра является опробование пар элементов (х',%') из ХхКш. Для каж­ дой пары (х',х ) вычисляется значение !(х',х )=У' и сравнивается у су '. Для несимметричного шифра (шифра с открытым ключом) проводится опробова­ ние х' е Х . В э т о м случае проводится сравнение значения Г(х',х0)=у' с у. Откры­

тый текст х, при котором у=у\ считается решением задачи. Как правило, при надежном шифре А такой способ дешифрования неэффективен из-за большого числа опробований, необходимых для определения открытого текста. Сокра­ тить число опробований можно путем опробования ключей х*^Кр при исполь­ зовании алгебры расшифрования шифра с последующим применением крите­ рия на открытый текст к получаемому расшифрованному тексту Р(у,х*)- Имен­ но этот метод дешифрования и получил название «тотальный метод».

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

Предполагается, что проверка на принадлежность расшифрованного те­ кста множеству содержательных текстов проводится с помощью некоторого «гипотетиченского статистического критерия на содержательные тексты», имеющего ошибки первого и второго рода: а - вероятность отбраковки содер­ жательного текста (в т^ш нах статистического критерия - отбраковки гипоте­ зы Н(0), отвечающей вероятностному распределению Р(0)); р - вероятность принять несодержательный текст за содержательный текст (принять гипотезу Н(0), когда верна гипотеза Н(1) - выборка из распределения Р(1), отвечающего нечитаемым текстам). Далее везде Р5* 1.

Предполагается также, что опробование ключей заключается в после­ довательном случайном и равновероятном опробовании без повторений г клю­ чей из Кр. Процесс опробования заканчивается при опробовании %ключей; ^=) - номер первого ключа ( 1 <)<г), при котором соответствующий расшифрован­

ный текст будет признан критерием за содержательный текст, или %=г, если такое событие не произойдет при любом )<г.

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

трудоемкость Е“,р(г) метода - среднее число опробуемых ключей (математиче­ ское ожидание случайной величины %).

Надежность яар(г) метода - вероятность определить истиный содержа­ тельный текст.

237

Расчет этих характеристик тотального метода будем проводить при следующих предположениях: при расшифровании шифртекста^ на всех клю­ чах %* из Кр среди расшифрованных текстов {Р(у,%*):%*еКр} содержится един­ ственный содержательный текст - истинный текст х0; в множестве Кр сущест­ вует единственный ключ у_*0, при котором Р(у,х*0)=х0Эти предположения по­

зволяют трактовать использование гипотетического статистического критерия насодержательный текст, как критерий проверки опробуемого ключа %* на его совпадение с неизвестным истинным ключом %*0. С вероятностью а истинный ключ будет признан ложным (при выполнении гипотезы Н(0) критерием будет принята Н(1)), а с вероятностью Р ложный ключ будет признан истинным (при выполнении гипотезы Н(1) будет принята Н(0)). Процесс опробования ключей закончится при опробовании %ключей; %=] - номер первого ключа (1<)<г), ко­

торый будет признан статистическим критерием за истинный ключ, или %=г, если такое событие не,произойдет при любом _)<г.

Проведем сначала расчет трудоемкости Е ^ г ) тотального метода. Да­ лее для краткости положим КР=К

Пусть В, —событие, состоящее в том, что в схеме последовательного опробования ключей без возвращения 1-ый ключ является истинным,

И 1 ,-,|К |};

-Еа’р(г,1) - среднее значение %при условии В,;

-Еар({<г) - среднее значение 2, при условии, что истинный ключ находится сре­ ди первых г опробуемых ключей;

Еар(с>г+1) - среднее значение Е, при условии, что истинный ключ не содержится среди первых г опробуемых ключей.

По формуле условного математического ожидания получаем

Е“'Р(Г)= —	Еа'р(1<г) + I^ I~ Г Еа р({>г+1).
|^ |	|К |

Для подсчета величины Еа,р(1:<г) предварительно подсчитаем Е“’р(г,1) при 1<г.

Г - 1	г
Еа’Р(г,1)-^Г/и(1 - Д Г 4 р + 1(1-Р)!-'(1-а) +	^ т а ( 1 - Д )м_2 Д + га(1-Р)г1.
т= 1	га = 7 + 1

Первое слагаемое отвечает окончанию опробований на каком то к-ом ключе, где к<1-1 (напомним, что истиный ключ опробуется при 1-ом опробова­ нии). Второе слагаемое отвечает определению истинного ключа при 1-ом опро­ бовании. Третье слагаемое отвечает ситуации аналогичной первой для к>1+ 1 .

Четвертое слагаемое отвечает ситуации, когда при каждом из первых г опробо­ ваний критерий принимал гипотезу Н(1).

238

Если истинный ключ находится среди первых г опробуемых ключей, то

он может с вероятностью —появиться при любом 4-ом опробовании,

г

4е{1,...,г}. Поэтому Еа'р(1< г )= ^ Е а’Р(г,*)р(В1 ) ,

1=1

г 1-1

Е“*(Кг)=-]Г(|;т(1-0Г,р+1(1-0)'-'а-а)+'%'№$-РГ*0 +га(1 -рГ')-

Г 1=1 т=1

т='+1

Г МЫ	+—	+- ^ЁЁ‘0-/в)м+га(1-я"'.
	г	г(1‘ Я м ы 1

Нам предстоит теперь изменить порядок суммирования в двойных суммах. С этой целью выпишем отдельно слагаемые первой и второй двойных сумм:

Слагаемые первой суммы:

4=1
4=2		1
4=3	1	+2(1-р)
4=4 1+2(1-р)+3(1-р)2
4=г-1	......................................................
4=г	1 +2(1-р)+3(1-р)2		+...+(г-1)(1-р)г'2
Слагаемые второй суммы:
2(1 -р)+3(1 -р)2+...+г(1-р у 1
3(1-Р)2+...		+г(1-Р)г''

г(1 -Р Г '

Меняя порядок суммирования в двойных суммах, получим, что Е“'р(1<г)=

- Б ( 1- # ' ( г - У ) + - ^ - Б - ( 1 - Д ' Н('-1 )+ — Ъ Ч - Р Г +ю (1-

Дополняя первую сумму слагаемым при у=т9а вторую слагаемым при 1=1 (равными нулю) и меняя везде индекс суммирования на «к», объединяя

первые три слагаемые в одно слагаемое, получим

Е“’р( 4 < г ) = - 2 > ( 1 - / ? ) к'1 Д г - к ) + ^ ( к - 1) + (1 - а ) + га(1-р)г1.

Г К=\

239

В том случае, когда истинный ключ не находится среди первых г опро­ буемых ключей, среднее число опробуемых ключей равно

Еа’р(.*>г+1)=

- Р)К_1Р + г(1-р)г.

к=1

Последнее слагаемое отвечает ситуации, когда при всех опробуемых ключах критерий принял гипотезу Н(1). Для получения окончательной формулы трудо­ емкости Еа,р(г) тотального метода подставим полученные выражения Еа,р((<г), Е^С&гН) в начальную формулу:

Е“’р(г)=	Еа’р(1>г+1).
1*1	К |
Д г - к ) + ^ ( * - 1 ) + (1 -а )		г а (1 -р )г'' +
I л. | к=[		1*1

, 1^1-г

+ г(1-Ю -

|К |

Приведем формулы для расчета среднего числа Е“’р(г) опробуемых ключей в некоторых частных случаях.

Если положить г=|К|, то мы получим формулу для среднего числа опро­ бований в тотальном методе при условии, что опробуются все ключи.

Д | К | - к ) + ^ ( к - 1 ) + (1 - а )

I -К I

Положим, г=|К| и а=р=0, то есть рассмотрим случай, когда в тотальном методе опробуются все ключи и критерий отбраковки текстов работает без ошибок/

е»0(|к |) - т2 - §	к = Щ ^ .
| А | *.=1	I

В случае г=|К|, а^О, Р=0, то есть при использовании процедуры, не допускаю­ щей принятия ложного ключа за иотинный, но допускающей невыявление ис­ тинного ключа, имеем

	1	1*1
Е“-0(|к|)=—		2>[1-«] +№ =
_ о - ж ^	! М 1 +1К1а=^ К 1 (1 _ а ) + , , , а
2 \	К \	2

Если положить г=|К|, а=0, Р*0, то есть рассматривать процедуры принятия решения, при которых невозможна потеря истинного ключа, то

			240
	1	1«1
Е°'(|К|)=—		2 * с(1 - /?)-' (/?(| /Г|-к> + 1)-
	I А	I *=1
1	№	4
- 7 ^ тЁ * ( 1 - Л '''0 » ( |К |- « с) + 1)-
|* |Й .
_ д щ + 1 а		_	_ _ д _ а к!
1*1	+		| / Г | Й

Для вычисления входящих в последнее выражение сумм рассмотрим функцию

		1*1	1 _	гк+|
		ф (х)= 2 У	' = —	- •
I ; « у - 1= Ф \х ) - ~ ('к			1+1)х'*' (* -		* ) + 1 -	х1*|+|
«=о			. (1 - х		)2
|К|		|К|	|К|
^ к 2х*-'	= ^ к ( к - 1 ) х к-1 + Х кхК*1 = х Ф " ( х ) + Ф '(х ) .
к=0		к=0	к=0
Втожезремя
Г ' М		1 - х		|	- х
Отсюда				1
		-(1/^1 +1) | К | х1*1
^	2				1 + х	.
У *		Xк 1= —±'----!	Г2 !------+ --------Ф (х ).
^		1 - х			1 - х

Испрльзуя полученные соотношения при х=1-р для Е0,Р(|К|) будем иметь

ф -0 - Д + (I Л-|+1)(1 - Р)Щ- т Ь г ^ ' О - Д .

	| А	|	| А	|
где
	СГ(1	Д	- ( 1 ^ 1 + ! ) ( ! - Д ' У + ' - а - Д ' ^	'
Подставляя последней выражение в формулу для Е°’Р(|К|) и проводя
элементарные преобразования получаем
Е“ т	~0 ~		~(| * 1+1)(| ~ '8>И /?!•[Д1 * I +1>- ‘1
			| К I д 2

Несложный анализ показывает, что при |К|—> оо