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

261

Во множестве ключей К выбирают «часть» К| ключей, то есть предста­ вляют К в виде К=К1хК2,а для основного отображения Ф: К|хК2—»У подбирают

некоторое вспомогательное отображение Ф*: К)—>У*. На множестве У*хУ за­ дают некоторый функционал (р:У*хУ-»К.1 и строится статистика ф (Хь(х(1),Х(2)))- Эта статистика и меры РТ(о)=Рт{т/т€Т(0)}, Рт(1)=Рт{т/т€Т(1)}

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

Рт(о>( ф(Хи (Х0),Х(2)))6В) и Рт(|)( ср(хь (х(1),Х(2)))еВ).

Цель построения общей схемы состоит в подборе четверки Кь У*, Ф* и ф так, чтобы приведенные выше распределения «хорошо различались», то есть чтобы эти распределения были в основном сосредоточены на некоторых непересекающихся множествах В(0), В(1). Если такую четверку подобрать уда­ ется, то в качестве решающей функции X берется индикаторная функция

ЧХи У(0))=1, если ф(хи (х(1),х(2)))еВ(0),

ЧХи У (0 ))= 0 , е с л и ф ( х ь (х (1 ),х (2 )))ё В(0).

Ошибки а, Р получаются из соотношений 1-а=РТ(0)( ф (хь (х(1)>Х(2)))еВ(0)),

Р=Рт(1>( ф(Хь (х ( 1)>Х(2))) е В (0 )).

Принцип «удобного» разбиения множества ключей.

Пусть I, П, О — конечные множества, ф: 1x0—>0. Задача состоит в на­ хождении решения со(0) системы уравнений

ф(12,СО)=У2

ф(1М,©)=Уы относительно неизвестного параметра <0€О.

Пусть ф*:1хО-Ю* - некоторое вспомогательное отображение, где О* - некоторый новый алфавит. Рассмотрим последовательность У*1,У*2, ...,У*м, где

ф*(1ь©*)=У*1

ф*(12,©*)=У*2

ф*(1к,М*)=У*Ы

для©*еО.

Предположим, что на I задано вероятностное распределение. Обозна­ чим через Р0,а)»(ф,ф*) - совместное распределение пары (ф(1,<о),ф*(1,<о*)), ин-

дуцированное распределением на I. Для заданной функции ф* проведем разби­ ение множества параметров О. на классы: Ш,П2,...,ОЬ так, что при любых

262

_),ке 1, Ь было верно утверждение: если со,со' принадлежат О], а со*,со** принад­

лежат Г2к, то Ро),<о*(м/>Ч/*)== Рю>**('|/,4/*), - то есть распределение пары постоян­ но на введенных классах:

Рп;,пк= Ромо*(Ч',Ч'*)= Ро),со»»('|/,'|/*).

Если это условие выполняется, то будем говорить, что функция у* согласована относительно разбиения множества О: на классы: П1,02,...,С2Ь.

Отметим, что можно действовать, исходя из разбиения множества О. Именно, искать согласованную функцию для заданного разбиения. Задача определения решения со(0) приведенной выше системы уравнений может быть решена путем предварительного определения класса Ц), которому принадле­ жит искомое решение. Задача же определения класса О] может быть решена следующим образом. Опробуя представителей со1,(о2,...,соЬ классов

121,02,.. ,,ОЬ и вычисляя для всех ]е 1,Ы значения \|/*(13,(сок), ке 1, Ь , опреде­

ляем значения выборок из распределений Рпк,о>(0)(члу*), ке 1,Ь (при этом по­

следовательность 11,12,—Дм рассматриваем как выборку из заданного распреде­

ления на I).

Если при любых пдеп, т,п е 1, Ь последовательности распределений

Р«*о)т(у,Ч/*),Р«<о)т(Ч/,у*),. ••,Рш(0)П1_(Ч',Ч'*)>	со(0)еПп,
Ри<0)П1(\|/,У*),Рш(0)П2('1/,\|/*),...,Рсо(0)пь('1/,'1/*),	ш ( 0 )е П т

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

Рю(0)П|('У>'1^*)>Рй>(0)П2('У>'К*)>'• чРсо(0)П1_(Ч^Ч^*) можно статистическими критериями определить с некоторой надежностью класс О), которому принадлежит иско­ мое решение со(0).

Частный случай «удобного» разбиедшя.

Для вышеизложенной идеи «удобного» разбиения возможен частный случай, когда Рпк,пк(у,У*)=Р(\|/,у*) при любом ке 1, Ь , и Р^,пк(Ч',Ч/*)*Р(Ч'>')/*)

при любых ^к. Тогда, опробуя представителей классов Оь 1,Ь, пользуясь

статистическими критериями, можно с некоторой надежностью определить искомый класс.

2). Другой подход к решению поставленной задачи поиска решения <о(0) сис­ темы уравнений

у О ь ^ у ,

\|/(12,СО)=у2

1|/(1м,Ю)=Ум

\263

состоит в поиске функции 1:1-»0*, для которой существует разбиение множес­ тва О на классы Ш ,02,...,0Ь , такое, что элементы ю, со' принадлежат одному классу тогда и только тогда, когда совпадают распределения Ро/фД) пары (4/(1,со),1( 1)) и Рю(\|/,1) - пары (\|/(1,оо'),1( 1)), индуцированные заданным распреде­

лением на I. В этом случае наблюдаемость пар (ур(^,со(0)),1(^)), ^ е 1,И позволя­ ет по выборке из распределения РИ(0)(\)/,1) статистически определить класс, в

котором содержится искомое решение оо(0).

Примеры статистических методов анализа

Пример 1. Метод статистических аналогов.

Пусть, как и ранее, \р: 1x0—>0. Рассмотрим поставленную выше задачу нахождения решенйя со(0) системы уравнений

У(11,С0)=У1

1|/(12,С0 )= У 2

\1/(1м,со)=Ум относительно неизвестного параметра соеО. Эту систему уравнений можно за­ писать в виде

А,(1,)=У1

Ч^)=У2

М}п)~У^

и решать ее относительно неизвестного отображения А.:1—>0, А.е{фш, соеО},

УЙ(1)=1|/(1,Ю).

Пусть существует функция ф:1—>0, характеризуемая тем, что для всех функций X из некоторого подмножества М всех возможных функций {\|/и:соеП} и только для них вероятность совпадения их значений со значе­ ниями функции ф (при случайном и равновероятном выборе 1е 1) имеет нену­

левое преобладание Д,р

Р(ф(0=>.(1))>|^-+А<р, для^еМ

и

Р(ф(0= М0)=

,' для Xё М.

264 *

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

Зная последовательности 3=11,12,...,1ы и Уьу2,...,уы и вычисляя значения функции ф на элементах известной последовательности 3

ф00=у' 1, ф(12)=у'2,. • .,фОм)=у'ы,

сравнивают на совпадение последовательно первые, вторые и т. д. элементы последовательностей уьу2,...,уы и у'|,у'2,...,у'ы- Наличие ненулевого преобла­ дания Дф в предположении, что 11,12,...,1м является выборкой из равновероятно­

го распределения на I, дает возможность строить статистический критерий, по­ зволяющий для достаточно длинных последовательностей с заданными ошиб­ ками первого и второго рода принять или опровергнуть гипотезу: искомое ото­ бражение X принадлежит множеству М. В общем случае множество возможных функций X, как правило, разбивают на непересекающиеся подмножества, объе­ динение которых дает все множество функций. Для каждого подмножества строят свой статистический аналог, вычисляют значения у'ьу'2,...,у'н и ис­ пользуют свой статистический критерий (со своим преобладанием) для провер­ ки принадлежности искомой функции X своему подмножеству. Затем оцени­ вают трудоемкость и надежность метода. Для более углубленного изучения способов построения статаналогов функций рекомендуем статью Сидельникова В.М. «Быстрые алгоритмы построения набора маркировок дискретных масси­ вов информации». Труды по дискретной математике, Т.1, ТВП, М., 1977, стр.251-264.

Пример 2. Статистический метод определения пары: входного сло­ ва и начального состояния конечного автомата.

Пусть А=(1,8,0,5,(3) - автомат и А(8,3)=у1,у2,... ,уЬ - его выходная по­ следовательность, отвечающая начальному состоянию зеЗ и входной последо­ вательности 3=П,12,...,1Ь. Задача состоит в нахождении входной последова­ тельности 3 и начального состояния 8€3 при известных А(з,3) и множестве Мс11, содержащем 3.

Пусть Ь - некоторое натуральное число и Ь=кЬ. Обозначим через р(У/3) - вероятность получения выходной последовательности У€Оь с автомата А при входном слове Зе1ь и случайно и равновероятно выбранном начальном состо­ янии е е 8, а через р(У) - безусловную вероятность получения У, при случайно и равновероятно выбранном начальном состоянии з€3 и случайном и равнове­ роятном выборе входного слова Зе1ь. Для автомата А определим два случай­ ных процесса и соответствующие им две гипотезы Н(0) и Н(1) получения пары: входное слово 3'=31,32,...,3к (в алфавите I) длины Ь=кЬ, 3 )е1ь и выходное слово У автомата А.

I

265

Н(0) - последовательность слов длины Ь: 31,32,...,3к есть реализация выбор­ ки из равновероятного распределения на З ь; последовательность (у1,у2,...уЬ)=(У1,У2,...,Ук), У)=у(]'-1)Ь+1 ,...,у)Ь,зе{1,...,к} получена последо­

вательной переработкой (А(з^З])=У)) автоматом А входных слов 31,32,.,.,3к при случайном и равновероятном выборе (для каждого слова ЗД начального СОСТОЯНИЯ (8]) из 8.

Н(1) - последовательность слов длины Ь: 31,32,.. .,3к есть реализация выбор­ ки из равновероятного распределения на З ь; последовательность (у1,у2,...уЬ)=(У1,У2,...,Ук), есть реализация выборки из распределения (р(У),УеОь).

Решение поставленной задачи проводится путем перебора возможных последовательностей (11,12, ,]Ь)=(31,32,... ,3к) из множества М и использо­

ванием статистической процедуры принятия одной из гипотез Н(0) или Н(1) для каждой пары слов (31,32,...,3к; У1,У2,...,Ук). Все не отбракованные вхо­ дные последовательности 3', то есть 3', для которых принимается гипотеза Н(0), совместно с каждым состоянием е е 8 опробуются на предмет выполнения

равенства А(з,3')=у1,у2,... уЬ.

Пример 3. Метод разностного анализа определения входного слова конечного автомата.

Пусть А=(1,8,0,(З^еьСРОы) - автомат, 3=ч1,12,...дЬ - его входное слово, «=8| - его начальное состояние, а з(3 )=31_-ц=8]1.8|1,-ц..•8128118 - его заключитель­

ноесостояние, полученное после воздействия входного слова 3 на автомат А с начальным состоянием з е 8. Задача состоит в определении входного слова 3

автомата А по некоторому множеству МП пар (начальное состояние з; заклю­ чительной состояние з(3)), полученном при входном слове 3.

Обозначим через Ам(з1,3 )=8|,82,...,8ь+1 - последовательность состояний автомата А, отвечающую его входному слову 3 и начальному состоянию 8=81.

Обозначим аналогично Ам(8'1,3)=8'ьз'2,...,8'ь+1. На множестве 8x8 определим некоторую функцию Ф со значениями в некотором множестве О. Для началь­ ных состояний 81 и 8\ автомата А определим последовательность Ф(81,8',),Ф(82,8'2),..., Ф(8ь+1,8\+1).

Примем следующую вероятностную модель. Задано равномерное веро­ ятностное распределение на I. Оно индуцирует равномерные вероятностные распределения на Р, зе {1,... ,Ь}. Задано также вероятностное рапределение на 8x8. Вероятностные распределения индуцируют вероятностные распределения на значениях Ф(81,8'1),Ф(82,з'2),..., Ф(8ь+1,8'ь+1), в связи с чем корректно опреде­

ляются условные вероятности Р(ЬУ/А) =р(Ф(^,з^)= у/Ф(8,,8',)= Д), ]е{1,...,Ь+1}.

266

Поставленную задачу определения входного слова 3 автомата А реша­ ют в два этапа.

На первом этапе находят возможные значения последнего символа ^ в 3. Выбирают пару (А,у), для которой величина Р(Ь,у/Д) принимает максималь­ ное значение. Выбирают из первых компонент множества МП (из множества известных начальных состояний автомата) состояния, точнее, пары состояний вида: (81,8'О, Ф(8],8'1)= А и из уравнений

1• • •б|2Й1181=5ь+1

6и Д ы ...бабп8 1=з'ь+1

Ф(81Ц ...8125и81, 5 ,ц ...6126,18'|)= у определяют множество Цвьб'О возможных значений первой переменной 1Ь.

Для достижения эффективности метода функцию Ф обычно выбирают (если это возможно) таким образом, чтобы предыдущая система уравнений, запи­ санная в форме

61ьЗ[=Зь+1
81ЬЗ'ь=5'ь+1
Ф(зьз'ь)=У, '
при известных значениях правых частей решалась относительно с достаточ­
но малой трудоемкостью. В литературе это предположение формулируется как
предположение о слабом криптографическом преобразовании 8ц..
Для сокращения мощности найденных возможных вариантов перемен­
ной ЁЬ, эту процедуру проводят для нескольких пар начальных состояний со
значением А функции Ф и выбирают общие решения относительно ЁЬ.
Второй этап решения задачи зависит, к&к правило от конкретных осо­
бенностей исследуемого автомата. Входные знаки ё1,ё2,...,ёЬ-1, теперь находят
либо с предварительным определением состояний вида (зьз'ц) и использова­
нием алгоритма первого этапа, либо перебором всех вариантов укороченной
последовательности 11,ё2, ,1Ь—1 , либо другими способами.	‘
ЗАМЕЧАНИЕ. При решении задачи неизвестная последовательность 3
фиксирована, а вероятности Р(),р/Д) рассчитываются при случайном выборе
входных последовательностей автомата. Для корректности вычислений пара­
метров метода обычно используют предположение о том, что эти вероятности	5
близки к вероятностям, полученным при фиксации последовательности 3 и	|
случайном выборе начальных состояний 86 8. Для более детального ознаком-	I
ления с примерами применения разностного метода криптоанализа рекоменду-
ем книги: Грушо А.А., Тимониной Е.Е., Применко Э.А. «Анализ и синтез крип-

267

тоалгоритмов», 2000, 108 стр; А.Л. Чмора «Современная прикладная крипто­ графия», М., Гелиус АРВ, 2001, 244 стр.

Пример 4. Метод линейного криптоанализа определения входного слова автомата. Рассмотрим идейную сторону метода линейного криптоана­

лиза на примере конечного автомата А=(1,8,О,(80|е1,(Р|)|е1) вида Г=Рг, 8=?" ,

моделирующего функционирование блочного шифра (например, шифра Фейстеля), 3 =ч1 ,12,... Д . - его входное слово, з=3| - его начальное состояние, а $(3)=8ы.1=8|[8л.+|...8|28п5 его заключительное состояние, полученное после воз­ действия входного слова 3 на автомат А с начальным состоянием 8€8. Задача состоит в определении входного слова 3 автомата А по некоторому множеству МП пар (начальное состояние з; заключительное состояние 8(3)), полученном при входном слове 3. Рассмотрим выражение вида:

ф(8)0\|/(8Ь+1) ®х(3)=е, где (р?1|/,х ~~ фиксированные произвольные двоичные линейные функции на

п I-#

соответствующих пространствах ?2 и Р2 , еер 2, © - сложение по той 2. Пусть

Рь - вероятность выполнения этого равенства при случайном и равновероятном выборе 8 и 3. Преобладание Рь—1/2 характеризует эффективность выбранного

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

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

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

ф(8)Фф(3]+1) 0 х(П,12,...,у)=е,	(*)
выполняющееся с вероятностью Рг

Затем стараются выразить ф^-ц) через вь+ь и вектор (у+1,у+2,...,1Ь) в виде \1/(8]+1)=ф'(8ь+|) ©х'(Р(8ь+1,(у+1 ,у+2,...,1Ь)), где ф', х' - линейные функ­

ции, а Р - некоторая функция, принимающая значения на векторном простран­ стве над полем Рг. Подстановка выражения для \|/(.^+0 в уравнение (*) дает ли­ нейное соотношение

ф(з)Ф ф'(8[.+1) ©X (Р(8ь+ь(Ч+ 15У+2,• • •дЬ))) ©х(П,12,...,у)=б, (**) выполняющееся с той же вероятностью Р; при случайном и равновероятном выборе з и 3. Предполагают, что это равенство будет выполняться приблизи­ тельно с вероятностью Р) и при фиксированной последовательности 3. В связи

268

с чем, при имеющихся парах (з^ь+О, полученных при одной и той же последо­ вательности 3, статистическими методами отсеивают ложные кандидаты в часть ключа (у+1,у+2,... Д.). При переборе варианов части ключа учитывают несущественную зависимость некоторых переменных, входящих в функции использованные в равенстве (**).

Пример 5. Вариация статистического метода с методом координат­ ного спуска (/Про/).

В качестве примера применения статистического метода рассмотрим задачу дешифрования алгоритма криптографической защиты Оатша-3. Про­ грамма шифрования запускается командной строкой 0 0 8 . При запуске про-

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

При удачной проверке программа запрашивает ключ для обработки файлов. Этот ключ дважды вводится с клавиатуры пользователем и представ­ ляет собой последовательность из Ь (от 1 до 32) символов из латинских букв, русских заглавных букв и 22 служебных символов (пробел, равенство, звездоч­ ка, знаки препинания и др.). Далее программа автоматически дополняет введе­

ние Ь символов пароля до длины пароля в 32 байта и на основе этого дополне­

ния пароля строит бинарный (рабочий) ключ х = (хь ...., х„) Длиной	п=31
бит и формирует начальное заполнение регистра ху= хуь \у2, .... , хуь	Ь = 39.
Открытый текст О, и шифрованный текст Ш, представляются в виде после­
довательности бит. Уравнения шифрования имеют вид
2ы = 0,+1 ф Н(Х1 + XV,+1, Х2 + XV,+1, , Х31+ XV*])
^ 1 + 4 0 = ш,+1,

где суммирование осуществляется по модулю 2, а пороговая функция, опре­ деляющая гамму наложения, Н(уь ..., у3|)=Ь(у1+ ...+у3|) равна 0, если У|+ ...

+у31<16, и равна 1, если у,+ ... +у31>15. Общее число паролей, допустимых для использования в системе защиты, равно К = т 32 +. т 31 + ....+ т , где т = 1 16 - число допустимых для ввода с клавиатуры символов. Таким образом, общее число паролей к>1064 достаточно велико. Блок-схема алгоритма шифрования имеет вид:

269

►

Открытый текст

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

Прежде всего отметим, что в процессе зашифрования используется то­ лько рабочий ключ длиной 31 бит и начальное заполнение регистра длины 39 бит (общее число вариантов ключевых установок равно 270«2-Ю21), а в процессе расшифрования при известном шифрованном тексте для расшифрования всех знаков, кроме первых 4 байт используется только рабочий ключ в 31 бит (об­ щее число вариантов равно 231«2-109).

Для системы защиты данных Оатта-3 , если ориентироваться на рас­ шифрование текста, начиная с 5-го байта, число неэквивалентных рабочих ключей, т. е. число ключей, дающих разные алгоритмы дешифрования, таким образом, равно 2-109. Это число, по меркам криптографии, невелико. На совре­ менной суйер-ЭВМ ключ может быть найден методом тотального опробования всех вариантов ключей, путем проведения пробного расшифрования и отсева ложных вариантов открытого текста по его статистическим свойствам.

Используемая в процедуре шифрования пороговая функция Н обладает существенными криптографическими слабостями. Главная слабость заключае­ тся в том, что для многих пар близких (в смысле расстояния Хэмминга) аргу­ ментов значения функции совпадают. Это приводит к повышенной вероятности совпадения гамм наложения шифра, полученных с помощью системы Оатта-3 на близких рабочих ключах.

270

Действительно, рассмотрим два рабочих ключа х=(х1,Х2,...,Хз!) и У=(УьУ2,--.,Уз1)5отличающихся одним битом, т. е. находящихся на расстоянии

Хемминга друг от друга, равном 1. Для определенности будем считать, что Х1=Уь • • • .,хзо=Узо, х31=Уз1+1 (то<12). Сумма знаков гамм наложения, получен­

ных на этих ключах в один и т о т же такт работы криптосхемы, имеет вид

Н( > 10 Х1,...,\У30Ф Х30,\У31 0 Х31)® Н О , 0 У1,...,^30Ф Узо,Ш31Ф у3,)=

=Н (\У1 0 Х1,...,\У30© Хзо,Ш31 © Х з ,)ф Н(\У] © Х1,...,\Уз0Ф Х30,\У31 © Х3] © 1)=

=Ь(У+(\У31Ф Х31)) © Ь(у+(Уз1 © Х31 Ф 1)).

Здесь через Ф обозначено суммирование по модулю 2 и

У = (\У ) ф Х 1)+ ...+ (\У з о Ф Хзо).

Обращаем внимание, что, если у<15 или у>15, то знаки гамм при обоих ключах совпадают.

При естественном предположении, что последовательность \У), \У2,.... по

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

Отсюда получаем, что вероятность совпадения знаков гамм для рабочих ключей, отличающихся одним битом, равна 1- ( 30 ) 2 зо.

Расчеты показывают, что для рабочих ключей, находящихся на рассто­ янии Хэмминга, равным единице, совпадают в среднем 85 % знаков гаммы, для ключей на расстоянии 5-75%, на расстоянии 10-62%, на расстоянии 15-50%.

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

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

Метод координатного спуска.

В применении к решению системы булевых уравнений Г(х)=а

от п неизвестных метод заключается в следующем.