µ §, (3.31)
где µ § - длина подблока.
В соответствии с полученной парой µ §, и учитывая в схеме алгоритма шифрования перестановки и сложение по mod2, формируется эффективный линейный статистический аналог
µ §, при µ §. (3.32)
Как правило, формируются несколько линейных аналогов (один из них эффективный) для которых значения вероятностей близки.
2. Генерируется множество независимых исходных текстов µ § и регистрируются соответствующие им криптограммы µ §.
3. Для каждой пары µ §, µ § вычисляется значение левой части эффективного линейного статистического аналога:
µ §. (3.33)
4. Определяется частота получения «1» при вычислении M значений (3.33):
µ §, (3.34)
и строится оценка максимального правдоподобия в соответствии с правилом:
µ § (3.35)
Вычисления на этапах 3 и 4 выполняются для всех сформированных эффективных линейных статистических аналогов.
5. Строится система линейных уравнений, причем каждое уравнение системы представляет собой равенство правой части (3.32) и соответствующего значения (3.35)
µ §. (3.36)
Единственное решение полученной системы (3.36) используется в качестве оценки ключа µ §. Таким образом, на шаге 1 решается первая задача линейного криптоанализа, а шаги 2-5 обеспечивают решение второй задачи.
Рассмотрим пример реализации алгоритма линейного криптоанализа на базе криптосистемы S-DES, подробно рассмотренной в [4]. Криптосистема S-DES разработана для изучения свойств криптосистем, основанных на схеме Фейстеля. Алгоритм шифрования по своей структуре аналогичен алгоритму DES. Отличие состоит в следующем:
- алгоритм имеет два раунда шифрования;
- алгоритм оперирует 8 битными входными блоками;
- функция усложнения включает два блока замены;
- основной ключ шифра 10 битный, а раундовые ключи 8 битные.
Таблицы замен и перестановок приведены в [4]. Для простоты, но, не нарушая общности, будем считать, что шифрование производилось одним раундом.
В соответствии с алгоритмом линейного криптоанализа вначале проводиться анализ блоков замены (см. табл. 3.1, табл. 3.2) функции усложнения.
Таблица 3.1. Блок замены µ § Таблица 3.2. Блок замены µ §
Результаты анализа блока µ § и блока µ § приведены в табл. 3.3 и 3.4.
Таблица 3.3. Анализ блока µ § Таблица 3.4. Анализ блока µ §
iЗначение jiЗначение jµ §011011 µ §0110110001888000188800108660010681000118660011612601006108010088801011410801018121201106860110108601116860111108610008881000888100188810018881010810101010101210101181021011108611006108110084121101610811018881110641011106810111161210111114810
Итак, в соответствии с табл. 3.3, можно выделить четыре эффективных линейных статистических аналога и составить первые четыре наиболее эффективных линейных уравнения, соответствующие парам: (i, j) ЁC µ §, µ §, µ §, µ §. В соответствии с табл. 3.4 можно выделить семь эффективных линейных статистических аналогов и составить семь наиболее эффективных линейных уравнений, соответствующие парам: (i, j) ЁC µ §, µ §, µ §, µ §, µ §, µ §, µ §. Следует отметить, что одно из уравнений будет более эффективным, однако его не достаточно для нахождения битов ключа.
Рассмотрим первую пару µ § блока µ §. Очевидно, что µ § выполняется с вероятностью µ §, а соответственно µ §. Тогда, в соответствии с (3.32) можно записать первое линейное уравнение для блока замены µ §:
µ §. (3.37)
Повторяя подобные рассуждения аналогично можно записать и другие линейные уравнения для блока µ §:
µ §,
µ §, (3.38)
µ §.
и блока µ §:
µ §,
µ §,
µ §,
µ §, (3.39)
µ §,
µ §,
µ §.
Представим исходный текст, как µ §. Затем выполняется начальная перестановка IP [4]. После перестановки получаем µ §, далее текст разбивается на левую часть µ § и правую часть µ §. Правая часть подвергается перестановке с расширением Е [4]. В результате получается следующий результат - µ §, который складывается с битами раундового ключа µ §. На блок µ § подаем µ §, на блок µ § подаем µ §. Представим входные биты блоков замены в следующем виде. Для блока µ § справедливы зависимости:
µ § µ § µ § µ §. (3.40)
Для блока µ § справедливы зависимости:
µ § µ § µ § µ §. (3.41)
Пусть криптограмма имеет вид µ §. Вид информационного блока до конечной перестановки (обратной начальной) имеет вид µ § Разбиваем данный блок на левую часть µ § и правую часть µ § Правая часть µ § получается в результате сложения по модулю 2 левой части исходного текста после перестановки IP µ § с текстом µ § прошедшим функцию усложнения. На выходе блоков замены функции усложнения имеем - µ §. После перестановки Р получаем µ §. В результате можно записать:
µ §, µ §, µ §, µ § (3.42)
Теперь подставим линейные уравнения (3.40) ЁC (3.42) в уравнения (3.38) и (3.39) и получим уравнения линейных статистических аналогов. Полученные результаты сведем в табл. 3.5.
На этом первый этап алгоритма линейного криптоанализа закончен. Выбрав в качестве ключа шифрования µ §0010001111 реализуем второй, третий и четвертый этапы. Сформировав набор пар «открытый текст ЁC криптограмма», используя µ §0010001111, на основании выражения (3.33) вычислим левые части линейных эффективных аналогов.
Таблица 3.5. Линейные статистические аналоги
№
блокаЛинейные уравнениярµ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §µ §
В результате получаем систему уравнений (пятый этап):
µ §, µ §, µ §, µ §,
µ §,µ §, µ §, µ §, µ §, (3.43)
µ §.
Решение системы уравнений (3.43) имеет вид:
µ §, µ §, µ §, µ §,
µ §, µ §, µ §, µ §,
µ §, µ §, µ §, µ §,
µ §, µ §, µ §, µ §.
Анализ решения системы уравнений (3.43) позволяет определить раундовый ключ µ §, а затем используя алгоритм формирования ключей алгоритма S-DES и метод полного перебора ЁC ключ криптосистемы.
3.6 Дифференциальный (разностный) криптоанализ
Метод дифференциального (разностного) криптоанализа предложен А. Бихамом и А. Шамиром, и, по мнению ряда специалистов компании IBM, является общим методом криптоанализа блочно-итерационных криптосистем. Идея заключается в анализе процесса изменения несходства для пары открытых текстов µ §, имеющих определенные исходные различия, в процессе прохождения через циклы шифрования с одним и тем же ключом.
Метод дифференциального криптоанализа будем рассматривать на примере криптосистемы S-DES. Пусть задана пара входов µ § и µ §, с несходством µ §. Известны перестановка µ § и перестановка с расширением Е, а следовательно, известны и несходства µ § на входе блоков замены µ § и µ §. Выходы µ § и µ § известны, следовательно, известно и несходство µ §, а значит, при известных перестановках µ § и µ § известны несходства ДС на выходе блоков замены µ § и µ §. Доказано, что для любого заданного ДA не все значения ДС равновероятны. Комбинация ДА и ДС позволяет предположить значения битов для µ § и µ §. То, что µ § и µ § известны, дает информацию о µ §. Несходство различных пар открытых текстов приводит к несходству получаемых криптограмм с определенной вероятностью. Эти вероятности можно определить, построив таблицы для каждого из блоков замены. Таблицы сроятся по следующему принципу: по вертикали располагаются все возможные комбинации µ §, по горизонтали ЁC все возможные комбинации ДС, а на пересечении ЁC число соответствий данного ДС данному µ §.
Число наибольших совпадений указывает нам пару ДA и ДС, с помощью которой можно определить секретный ключ. Пара открытых текстов, соответствующих данным ДА и ДС называется правильной парой, а пара открытых текстов, не соответствующих данным ДA и ДС ЁC неправильной парой. Правильная пара подскажет правильный ключ, а неправильная пара ЁC случайный. Чтобы найти правильный ключ, необходимо просто собрать достаточное число предположений. Один из подключей будет встречаться чаще, чем все остальные. Фактически, правильный подключ появляется из всех возможных случайных подключей.
Рассмотрим пример применения дифференциального криптоанализа на практике. Вначале анализируются блоки замены и формируются таблицы зависимостей ДА от ДС. Анализ осуществляется следующим образом. Так как на вход каждого блока замены подается по четыре бита, то и размерность их суммы по mod2 не будет превышать четырех бит. Таким образом, диапазон изменения ДА лежит в пределах 0000 ЁC 1111. Однако, пара анализируемых текстов должна различаться хотя бы одним битом, тогда значение µ § не может использоваться для анализа. Поэтому диапазон изменения ДА составляет 15 значений от 0001 до 1111. Каждое из значений ДА может быть получено шестнадцатью возможными комбинациями входных данных блоков замены. Так, например, µ § может быть получено следующими возможными комбинациями:
0000„v0001, 0001„v0000, 0010„v0011, 0011„v0010, 0100„v0101, 0101„v0100,
0110„v0111, 0111„v0110, 1000„v1001, 1001„v1000, 1010„v1011, 1011„v1010,
1100„v1101, 1101„v1100, 1110„v1111, 1111„v1110.
При этом сумма выходов по mod2, полученных после прохождения любой пары данных входов через конкретный блок замены, не всегда совпадет с суммой выходов того же блока замены по mod 2 другой пары. Рассмотрим пару входов 0011„v0010, значение 0011 при прохождении через блок µ § даст 01, а значение 0010 ЁC 00. Сумма этих выходов по mod2 будет равна ДСµ §. Рассмотрим другую пару входов 0101„v1011. При прохождении через блок µ § значение 0101 даст нам 00, а 1011 ЁC 11. Таким образом, ДСµ §. Из данного примера наглядно видно, что одному и тому же значению ДА могут соответствовать различные ДС. Результаты анализа блоков замены µ § и µ § приведен в табл. 3.6 и 3.7.
Таблица 3.6. ДС(ДА) в блоке µ § Таблица 3.7. ДС(ДА) в блоке µ §
ДАДСДАДС0001101100011011000166220001262600100484001008080011226600116262010001204010008440101662201016262011000880110001240111226601112626100066221000262610014840100100124101022661010626210110401210110844110066221100626211018404110144081110226611102626111140120111112400
После того, как проведен анализ и построены таблицы, можно приступить к выявлению наилучшего ДА и соответствующего ему ДС, то есть пары (ДА, ДС). Из табл. 3.6 и 3.7 можно выделить несколько равновероятных пар. Для блока µ § такими парами будут: (0100, 01), (1011, 11), (1111,10), а для блока µ § - (0110, 10), µ §, (1111, 00). Однако, следует учитывать, что ДА равно сумме по mod2 переставленных и расширенных входных бит. Тогда можно выделить единственное значение ДА=11111111, которому соответствует ДС=1000. Именно эта пара и будет рассматриваться далее.
Зная наилучшее значение пары (ДА,ДС), можно приступить к нахождению ключа. Для этого понадобятся несколько пар открытых текстов (Х1,Х2), таких, что ДАµ §, а ДСµ §. Для того, чтобы из зашифрованного сообщения Х1 выделить µ §, необходимо к последним четырем битам шифрованного сообщения добавить первые четыре бита, а затем учесть последнюю перестановку. Для удобства работы данные тексты и относящиеся к ним данные занесем в табл. 3.8.
Таблица 3.8. Пары (Х1, Х2), соответствующие наилучшим (ДА, ДС)
№Х1µ §µ §Y11000110011100001110110100011021111100111000011101100001000№Х2µ §µ §Y21010001100011110000111101011120100011000111100001111010111
Рассмотрим приведенные пары открытых текстов, учитывая, что результат ѓй складывается по mod2 с левой частью исходного сообщения. Так как на вход блоков замены µ § и µ § поступают значения µ § и µ §, то для всех Х1 и Х2 имеем следующее.
Для блока µ §:
1. Пара (00011001, 01000110): µ § даст на выходе 10; µ § даст на выходе 00. На выходе блока µ § значение 10 получается в том случае, когда на его вход подается одно из значений 0100, 0101, 1000, 1101, а значение 00 ЁC при входных 0010, 0111, 1010, 1011. Исходя из этого, имеем следующие возможные варианты:
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §.
2. Пара (11111001, 01000110). Для блока µ § данную пару рассматривать нет необходимости, так как первые четыре бита µ § и µ § будут аналогичны тем же битам предыдущей пары, а, следовательно, дадут такой же результат.
Для блока µ §:
1. Пара (00011001, 01000110): µ § даст на выходе 11; µ § даст на выходе 11. На выходе блока µ § значение 11 получается в том случае, когда на его вход подается одно из значений 0001, 0010, 1100, 1101, а значение 11 ЁC при входных 0001, 0010, 1101. Исходя из этого, имеем следующие возможные варианты:
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §;
µ §, µ §.
2. Пара (11111001, 01000110). Для блока µ § данную пару рассматривать нет необходимости, так как вторые четыре бита µ § и µ § будут аналогичны тем же битам предыдущей пары, а следовательно дадут такой же результат.
Объединив результаты анализа, получим следующие наиболее вероятные раундовые ключи:
µ §, µ §, µ §,
µ §, µ §, µ §,
µ §,µ §.
Как показала проверка, из всех возможных комбинаций, µ § является искомым раундовым ключом. Используя алгоритм формирования раундовых ключей алгоритма S-DES, остальные 2 бита ключа криптосистемы можно найти методом полного перебора.
4. Теория стойкости криптосистем
Систематические вопросы теоретической стойкости криптосистем впервые исследовал К.Шеннон в своей фундаментальной работе [5,10,11,13], опубликованной в 1949 г. В этой работе К. Шеннон рассматривал вероятностную модель шифра и криптоатаку на основе криптограммы. Примерно в те же годы концепция совершенных криптосистем разрабатывалась в закрытых работах, выполняемых под руководством В.А. Котельникова.
4.1. Совершенно стойкие криптосистемы
Предположим, что имеется конечное число возможных открытых сообщений µ §, множество возможных ключей µ § и множество криптограмм µ §. Задано криптопреобразование:
µ §. (4.1)
Считаем, что на множестве открытых сообщений µ § задано априорное распределение вероятностей, т.е. определены априорные вероятности µ §, µ §. Это априорное распределение известно противнику. После того как шифровальщик противника перехватил некоторую криптограмму µ §, µ §, он может вычислить, по крайней мере в принципе, апостериорные вероятности различных сообщений µ §.
Криптосистема называется совершенно стойкой (совершенно секретной), если выполняется условие:
µ §, при всех µ §, µ § и µ §. (4.2)
В этом случае перехват криптограммы не дает криптоаналитику противника никакой информации. Он не может корректировать никакие свои действия в зависимости от информации, содержащейся в криптограмме, так как все вероятности, относящиеся к содержанию криптограммы, не изменяются. Смысл выражения (4.2) заключается в том, что открытый текст и криптограмма статистически независимы.
Теорема Шеннона. Если система является совершенно стойкой (т.е. выполняется условие (4.2)), то справедливо равенство:
µ §, при всех µ § и µ §. (4.3)
Верно и обратное утверждение: если (4.3) выполняется, то система совершенно стойкая.
„T Используя определение условной вероятности, при µ §, можно записать:
µ §. (4.4)
Принимая во внимание (4.2), получаем:
µ §, то есть µ §.„S
Другими словами, полная вероятность всех ключей, переводящих сообщение µ § в данную криптограмму µ §, равна полной вероятности всех ключей, переводящих сообщение µ § в ту же самую криптограмму µ § для всех µ §, µ §, и µ §. К. Шеннон доказал, что совершенно стойкие криптосистемы существуют.
Теорема о совершенной стойкости шифра Вернама. Шифр Вернама является совершенно стойкой криптосистемой.
„T Согласно теореме Шеннона достаточно доказать справедливость (4.3). Имеем:
µ § (4.5)
|
