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

241

Е°’Р( |К |) - Д .

Следовательно, при больших значениях |К| можно пользоваться приближенным

равенством Е0,Р(|К|)5— .

$

Перейдем теперь к расчету надежности метода тотального опробования ключей, то есть вероятности Р(г,а,Р) определить истинный ключ этим методом.

Пусть С - событие, состоящее в определении истинного ключа при оп­ робовании г ключей. Используем введенные ранее события В„ 1е {1,.. .,|К|}. Со­

бытия В, несовместны, в связи с чем событие С представимо в виде

Г

С-1НС п В ,) . Отсюда

(=1

Р (г ,а ,())-Р (С )-2 Р (С п В Э -2 Р(В ,)Р (С /В . ) =		Г ? 7 2 Р(С/В') ’
/=1	/-1	1^1 /=1
так как Р{В ,) = —— . В то же время Р (С / 2?,) = (1 —/?)‘ 1		(1 —а ) . Следова-
.1 * 1
тельно,

Последнее равенство выписано в предположении: {3*0.

Методы использования эквивалентных ключей

Пусть А=(Х,К,У,1) - алгебра зашифрования шифра. Напомним следую­

щее

Определение. Ключи %,%' называются эквивалентными, если Г(х,х)=Г(х,х') при любом Х€Х.

Ключи %,х еК называются эквивалентными относительно подмноже­ ства Х'сХ, если

Г(х,х)=Г(х,х')

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

242

Ц Х ' )

Обозначим это разбиение через К.(а(Х'))= 1^)^/ • Очевидно, что из эквива-

У = 1

лентности ключей х,Х €К относительно X' следует их эквивалентность и отно­ сительно любого подмножества X" множества X'. Откуда вытекает, что любой

класс К ? содержится целиком в некотором классе К * эквивалентности от-

/

носительно подмножества X" множества X'. Каждый класс К * состоит из объединения некоторых классов К * . В частности, Ц Х ")<Ц Х '), а классы

К * «мельче» классов К * .

Рассмотрим задачу определения ключа %по заданным открытому х и шифрованному ^ текстам, т. е. задачу решения уравнения Г(х,х)=у относи­

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

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

Будем решать поставленную задачу при различных возможных допол­ нительных данных.

1.Известны представители ХьХг>-• -»Хь классов КЬК2,...,КЬ эквивалентных

ключей. В этом случае проводится опробование без возвращения предста­ вителей до первого успеха (до получения представителя класса эквивалент­ ности, в котором лежит искомый ключ). То есть для каждого опробуемого ключа х вычисляется Г(х,х)=ух и сравнивается ух с заданным у. Процесс оп­ робования заканчивается при получении равенства ух=у. Трудоемкость Т в опробованиях такого метода совпадает с трудоемкостью тотального метода при г=|К|=Ь и нулевых ошибках статистичечкого критерия:

2

Надежность метода я=1.

2.Известны мощности классов эквивалентных ключей и представители этих классов.

Упорядочим Хк1)»9Ск2)»-• мХкцизвестные нам представители в соответст­

вии с мощностями классов эквивалентных ключей:

243
|К((1)|>|КК2)|>...>|К№)|
и опробуем их в соответствии с этим порядком	-,Х»(Ь), г- ^ • Алго­

ритм прекращает свою работу, если найден искомый ключ (с точностью до эк­ вивалентности), либо проведено г опробований.

Если ключ шифра выбирался случайно и равновероятно из К, то веро-

		I * , I
ятность выбора ключа из класса К) равна -у-^у. Поэтому среднее число Тг оп­
робуемых при реализации алгоритма ключей равно
г-'	I К • I	1 I К . I
т г = У ) —		,
6	1*1	1 ^ \ к \
а надежность метода

>1 \ гг \ ■

\К .

При г=Ь имеем

3. Известны Только мощности |К1|, |К2|,...,|Кь| классов эквивалентных ключей.

Проведем опробование без возвращения ключей %еК до получения ис­ тинного ключа с точностью до эквивалентности.

Если ключ шифра выбирался случайно и равновероятно из К, то веро-

I * / I

ятность выбора ключа %из класса К) равна --------. Обозначим через Т())

1 * 1

среднее число опробований алгоритма, при условиии что искомый ключ ХбК). Тогда

Т0 ) = ^ ^

и общее среднее число опробований алгоритма

т^	т о ) Щ - 1 ^ ± 1 ^ |К )| .
м	\ К \	|К| Я \ К , \ + 1

Надежность метода п= 1.

Отметим, что если в данном методе опробование проводить с возвра­ щением, то среднее число опробований алгоритма будет равно

244

у 1I К | I -^7 = 1 .

■*

\

Следовательно, в условиях третьей задачи всегда Т<Ь. Очевидно,

2

при этом нижняя оценка достигается при Ь=1 , |К)|=|К|, а верхняя при Ь=|К|,

|К^=1. Если известны оценки мощностей классов эквивалентных ключей

с3<|К||<Сь

ТО

| К | + 1 Г с > ' Т г | к | + 1 У С > | К | р с , + Г . | К | 4 ; с ; + Г

4.Известно число Ь классов эквивалентных ключей. Проводя метод пункта 3, для трудоемкости метода получаем оценку Т<Ь.

Обратим Ваше внимание на то обстоятельство, что изложенные методы

базировались на эквивалентности ключей относительно заданного хеХ («сла­ бой эквивалентности ключей»). Обычно точный расчет мощностей классов та­ ких эквивалентностей затруднителен, в связи с чем пользуются эквивалентно­ стью ключей относительно всего множества X. В этом случае несложно полу­ чаются нижние оценки мощностей классов использованных нами слабых экви­ валентностей. Прямое использование мощностей классов эквивалентных клю­ чей относительно всего множества X в методах 1-4 дает верхние оценки тру­ доемкостей изложенных выше методов «слабых эквивалентностей».

Метод опробования с использованием памяти

Пусть известны: А=(1, 8, О, (81)151, (ОДеО - конечный автомат и его N

вход-выходных последовательностей 3^=^(1),У(2),..., ^(Ь); 9^=У(1),У(2),..., У(Ц

где У(к)€1, У(к)еО,) е 1,N .Требуется найти произвольное состояние з е 8, при

котором А(з,30=91^ при некотором )е 1,Ы. Напомним, что А(з,3^) — выходная

последовательность автомата А с начальным состоянием 3€8 при входном сло­

ве ,3^.

Метод состоит из двух этапов.

245

На первом этапе проводится заполнение памяти (таблицы), содержащей |0|‘ ячеек (строк), где I - параметр метода, С<Ь. Фиксируется некоторое слово

из I*. Для заполнения памяти опробуются все последовательности (3*,№),) € 1,N . Для )-той пары проверяется условие

(^(1)Л 2),...,1^))=(1.Д2,

Если равенство выполнено, то пара (3\№ ) записывается в ячейку (строку) с адресом у’(1 ),у’(2),..., у*(1).

На втором этапе проводится опробование состояний зеЗ (опробование поурновой схеме без возвращения). Пусть А(з,1 1 ,1 2 ,...,1[)= у5(1 ),у5(2),..., у5(0 - выходное слово автомата А, определяемое начальным состоянием з е 8 и вход­ ным словом !],12,...,1(. Тогда проводится обращение к ячейке (строке таблицы) с адресом у5(1),у5(2),..., у5(1). Если ячейка оказалась пустой, опробуется следую­

щее состояние автомата. В противном случае, проверяется, удовлетворяет ли состояние 8 улобиям задачи относительно одной из пар (3;,№), записанных в этой ячейке, то есть перерабатывает ли автомат А с начальным состоянием 8 входное слово З 1 в выходное слово пара №. Если состояние 8 таково, что А(к,

3’)= №, реализация алгоритма заканчивается. В противном случае (после опро­ бования всех пар из ячейки на состоянии к) опробуется следующее состояние из 8.

Очевидно, надежность метода равна единице. Рассчитаем его трудоем­ кость. Пусть N1- число пар из всех (3\№ ), )е 1, N , для которых

0>(1),142),...,т = (ц ,1 2,...,1,).

, Трудоемкость первого этапа метода имеет вид: Т|=Н+МЬ где N - число опробований на предмет поиска пар с началом (1^,12,-. .д«), а N 1 - число обраще­ ний к памяти для записи в память пар с этим началом. Здесь и далее мы «сум­ мируем различные операции», молчаливо предполагая, их приблизитель­ ную равноценность по скорости выполнения.

В качестве трудоемкости второго этапа метода берут величину

т _ |8 |+ 1 , |81+1 N4

2 ^ +1 1 ^ + 1 | 0 | 1 ’

246

|5|+1		,
г д е-------------среднее число опробуемых состоянии на втором этапе метода,
^	+1
13 1+1	К!	_
--------------------N ^1	|0|*	среднее число опробовании второго этапа метода, совершаемых

	N
после обращения к памяти ( — -— среднее число пар в ячейке памяти).
	I о Г
При получении этой формулы использовано следующее предположе­
ние: для каждой пары	существует единственное состояние, при котором
А(з,3])=

Первое слагаемое в формуле для Тг - это среднее число операций вы­ числения выходного слова А(з,11Д2,- -.,1*)= У*0)>У*(2)>—>у50 с последующим об­ ращением в память по адресу у5(1),у5(2),..., у5(4). Второе слагаемое - это среднее

число операций вычисления выходного слова А(з,30 с последующим сравне­ нием его с да.

При необходимости проводят усреднение общей трудоемкости Т1+Т2по возможным значениям N1 и оптимизацию метода по параметру I, а также его

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

Остановимся на одной модификации приведенного метода упорядо­ ченного опробования.

На первом этапе наряду с фиксацией начала 11,12, Д* входных слов ав­

томата фиксируют и некоторое начало УьУг,- • ,У( его выходных слов и отбира­ ют пары вход-выходных последовательностей 3 )=^(1),^(2),..., ^(Ь); да=у)(1),у)(2),..., у*(Ь) автомата удовлетворяющие условию

1Ч1)Д 2),..„ ?(1)= 11,12,	, у’(1),у’(2),..., у*(1)= УьУ2,...,У1
Обозначим через М - множество отобранных пар.
На втором этапе метода проводится опробование состояний §€8 и от­

бор таких 8, при которых А(з, 11,12,...,1е)= УьУг,---,У|- На третьем этапе проверяют, удовлетворяет ли 8, отобранное на втором

этапе, хотя бы одной паре (3*,да) из множества М, то есть выполняется ли ра­ венство А(8,30=да. В процессе реализации метода второй и третий этапы че­ редуются: как только на втором этапе найдено состояние 8 автомата, при кото­ ром А(з, 1|Д2,.. -,1с)= УьУ2,-”»Уь _ так °но опробуется на третьем этапе. Перебор

проводится до появления искомого состояния.

Число операций первого этапа равно N (операции нахождения пар, при­ надлежащих множеству М). Для подсчета трудоемкостей второго и третьего этапов метода примем предположения, указанные выше.

247

Пусть ^ - число опробуемых состояний на втором этапе метода, 2, - чи­ сло опробуемых состояний на третьем этапе метода. За операцию примем по­ лучение выходного слова автомата при заданных начальном состоянии и вход­ ном слове. Тогда общее число операцш, выполненых на втором и третьем етапах, составит ^+2, |М|, при этом ^ и 4 - случайные величины. Среднее значение Т2.3 величины %-Н; |М| имеет вид

Т2,3 = Е (^ '|М |)= Е ф + Е (й |М |.

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

|М|-исходов. Поэтому Е(^)= ^^ I	. Далее,
| М | +1
	|5|ЧМ|+1
Е й > ^ Щ ' $ = уШ = у).
	У=\
Предположим дополнительно, что вероятность события А(з, 1],

12,...,!()= уьУ2,...,У( при случайном и равновероятном выборе з е 8 равна |0 |'*. То­

гда Е(2, 4=у)=у|ОГ‘ и

|8|-|М|+1
В Д - 2	VI о Г* р(Е,= V) =1 о Г* Е(е.).
у*=1
Таким образом,
т	|5 |+ 1	, IМ |( |5 1+ 1)
2,3	| М | +1	(| М | +1) | О |1 ’

В ряде случаев, при необходимости, проводят усреднение трудоемкости метода по |М| и ее оптимизацию.

Метод расшифровки черного ящика

Пусть для начального состояния §€8 и каждого входного слова Зе1ь

известно выходное слово А(з,3)= 9?=у(1),у(2),..., у(Ь). автомата А. Требуется найти частичные функции переходов и выходов автомата А.

Обозначим через А(з) - подавтомат автомата А=(1, 8, О, (бО^ь (РО^О,

порожденный состоянием з. Состояниями этого подавтомата являются: само з и все состояния, достижимые в автомате А из з. Уточненная задача, решаемая ниже, состоит в построении графа переходов автомата А(з), что равносильно нахождению его функций переходов и выходов. При этом мы будем предпола­ гать, что автомат А(з) является приведенным и Ь>К+0 + 1 , где К - степень раз­

248

личимости автомата, Б - его диаметр (здесь использована терминология теории автоматов.

Метод состоит в последовательном проведении двух этапов (использу­ ется терминология теории графов).

На первом этапе по набору входных и выходных слов строится дерево высоты Ь, из каждой вершины которого' исходит |1| ребер. Каждое ребро, исхо­ дящее из каждой вершины дерева, помечается одним из символов входного ал­ фавита I, точнее говоря, устанавливается взаимно-однозначное соответствие между элементами из I и ребрами, исходящими из каждой вершины. Для 1={0,1 }, Ь=2 полученное таким образом дерево изображается на приводимом ниже рисунке (левая стрелка - 0, правая - 1)

Далее проводится «разметка» дерева выходными символами у € 0 авто­ мата А(§) по следующему правилу. Пусть ребро V является концом пути, кото­ рый начинается в корне и ребрам которого соответствует входное слово 11,12,...,1ь если А(з) преобразует его в выходное слово У1,уг,---»У«» то ребро V

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

На втором этапе осуществляется операция «свертывания» дерева V, то есть получение из дерева V графа переходов автомата А(з). Занумеруем все ве­ ршины дерева V следующим образом: припишем номер 1 корневой вершине, затем нумеруем слева направо все вершины первого яруса, второго и так далее до И+1 яруса включительно. Назовем вершину с номером) базисной, если по­ ддерево УО) дерева V высотой К с корнем в вершине с номером) отлично от любого поддерева УО) дерева V той же высоты с корнем в вершине с номером )' - такой, что )'<).

Свертывание дерева V проводится следующим образом. На первом ша­ ге поддерево У(2) сравнивается с поддеревом У(1). Если У(2) отлично от У(1), то вторая вершина базисная и на следующем шаге сравнивается У(3) с подде­ ревьями У(1) и У(2). Если же У(2) совпало с У(1), то из дерева У удаляется все его поддерево (высоты Ь -1) с корнем во второй вершине; ребро, входившее во

вторую вершину, присоединяется к первой вершине, то есть проводится пере­ ориентация ребра (с его пометками), и на следующем шаге сравнивается У(3) с У(1). Вообще на к-ом шаге последовательно сравнивается некоторое поддерево

249

%) с поддеревьями У(]), где |<)'к и - номер базисной вершины. Если У(]к) совпало с некоторым У(Р),-то все поддерево дерева V с корнем в вершине с номером^ удаляется из V (удаленные таким образом вершины в дальнейшем нерассматриваются), ребро, входившее в вершину )к, присоединяется к верши­ не)', то есть переориентируют ребро. На (к+1)-ом шаге проводят сранение по­ ддерева У0к+0>где ^+1 минимальный номер вершины такой, что_)к+1> )к и вер­

шина с этим номером осталась в дереве после проведения к-го шага. Алгоритм заканчивает свою работу после того, как проведено сравнение последней не удаленной вершины (0 + 1)-го яруса дерева V.

' Расчет параметров метода расшифровки «черного ящика». Надежность метода очевидно равна единице, а общая трудоемкость Т метода есть сумма трудоемкостей Т1 и Т2 первого и второго этапов. Подсчитаем величину Т|. Чис-

11 |ь	1 1 1 , поэтому для реализации первого этапа требу-
ло дугдерева V равно — —-
1 1 |ь	11 |ь
ется память объема ууу—у 111	ячеек и для ее «разметки» у-у—у 111 обращений

кпамяти, то есть трудоемкость первого этапа можно положить равной

| 1 |ь Т|=уу|—у 111 обращений к памяти.

Точный расчет трудоемкости второго этапа метода достаточно сложен, в связи с чем мы его не приводим.

Метод упорядоченного опробования в задаче оп­ ределения входного слова автомата

Пусть А=(1,8,0,6,Р) - автомат, для которого 1=АхХ, 0=А, функция пе­ реходов 8(а,х,з), (а,х)е АхХ при каждом зе8 зависит лишь от хеХ, то есть 8(а,х,з)= 8(х,з), а функция р при каждом зеЗ зависит лишь от аеА, то есть

Р(а,х,8)=Р(а,з), и при каждом зе8 эта функция.осуществляет биективное отобзажение А в 0= А.

Рассматриваемая задача состоит в определении входной последователь­ ности Хо,Х1,...,хк при известных данных: автомат А, выходная последователь­

ность уо,У|,...,Ук> отвечающая выходной последовательности ао,хо),(а1,Х1),...,(ак,х,с) и начальному состоянию з0автомата А.

Обозначим через \Ук+1 множество входных последовательностей хо,Х1,...,хкеХ к+1, являющихся решениями задачи, а через 8К+] множество заклю­

чительных состояний автомата А, отвечающих его входным последовательнос­ тям вида (ао,х0),(а1,Х1),...,(а1,х|С), х0,Х1,...,хкеХ к+1. Множество \Ук+| искомых по­

250

следовательностей может быть разбито на непересекающиеся подмножества \Ук+1>5, 8е 8 к+1, где \Ук+1,з - множество последовательностей хо,Х|,...,хк, являю­

щихся решениями задачи, и при которых автомат А с начальным состоянием $о переходит в заключительное состояние 8. Таким образом, задача сводится к нахождению множества 3*+! и соответствующих его элементам з е 8 к-н мно­ жеств \Ук+1>5. Для нахождения этих параметров предлагается следующий алго­ ритм, состоящий в последовательном построении множеств Зу\У^8, 8е 8^по на­ чалам ао,а1,...,а,*.ь Уо,Уь.--,Ум известных последовательностей хо,Х1,...,хк,

Уо,Уь---,Ук- Положим, 30={8о,}, ^о,з0= х • В качестве множества 8| выберем все со­

стояния 8 вида 8 = 5 (х ,80), хеХ, для которых Р(а1,8)=уь а в качестве множества \У|>5, з е 8| выберем все элементы хоеХ, для которых 8(х0,8о)=8еЗ|. Пусть для]- го шага построены: множество состояний 8] и множества з е 8; входных слов длины ^ в алфавите X. Тогда множество 8^, строится исходя из следующе­ го правила: 8^1 е 8^1 тогда и только тогда, если для некоторых з^е 8^и х^€Х 8(х^,8|)==8|+1 и Р(а^|,з^1)=у,+|. Если з^ е З ^ , то множество \У|+|>8 состоит из

всех слов вида х0,х1,...,х;.1,х,, где хо,Х|,...,хце ^	>8 и 8(х^)= 3)+1. Алгоритм за­
канчивает свою работу при ]=к, и множество	^ К,$Кпредставляет собой

множество решений рассматриваемой задачи, так как к+1-е элементы хКв ре­

шениях произвольны (это следует из законов функционирования автомата А). Трудоемкость алгоритма совпадает с трудоемкостью предложенного

метода построения множеств 8<>, 81,:.., 8К. Она определяется величиной

к

Т=|Х| = | | . ^=0

Здесь за операцию принято вычисление 6(х,8) при заданных (х,з)еХх8и

проверка равенства Р(а,з)=у для заданных (а,з,у)е АхЗхО.

Предположим, что автомат А выбирается случайно и равновероятно из класса всех автоматов рассматриваемого типа с заданными алфавитами 8, X, к Это означает, что 8 является случайным равновероятным отображением мно­ жества Хх8 во множество 8, а Р выбирается случайным равновероятным обра­ зом из класса всех отображений множества Ах8 во множество 0=А, индуци­ рующих при любом фиксированном з е 8 подстановку множества А. В приве­

денных предположениях |^| являются случайными величинами, в связи с чем представляет интерес