Основные теоретические сведения. Блочные симметричные криптосистемы (БСК) представляют собой семейство обратимых криптографических преобразований блоков (частей фиксированной дины) исходного

Блочные симметричные криптосистемы (БСК) представляют собой семейство обратимых криптографических преобразований блоков (частей фиксированной дины) исходного текста.

В настоящее время разработано большое количество БСК, многие из которых являются национальными стандартами. Наибольшую известность приобрели системы DES, IDEA, AES (Rijndael), ГОСТ 28147-89. Эти системы находятся под пристальным вниманием криптоаналитиков, основной задачей которых является поиск «слабых мест» в этих системах.

В настоящей работе метод линейного криптоанализа БСК

рассматривается применительно к криптосистеме S-DES, являющейся упрощенной версией криптосистемы DES.

1. Алгоритм шифрования (расшифрования) криптосистемы S-DES. На рис. 1 иллюстрируется алгоритм шифрования (расшифрования).

L	к	R
i	г

к

R_l=il/(R₀^k)®L₀

Рисунок 1 – Схема алгоритма шифрования S-DES с сетью Фейстеля

Входной 8-битовый блок вначале подвергается начальной перестановке (IP), в соответствии с табл.1. Биты подблока пронумерованы от 0 до 7, причем

бит с наибольшим порядковым номером наоборот.

Таблица 1 – Начальная перестановка IP

7 6 4 0 2 5 1 3

7 является младшим битом, и

Таблица разделена на две части, верхняя часть определяет подблок левых бит L₀, а нижняя часть определяет подблок правых бит R₀. Таким образом,

после начальной перестановки IP, подблоки L₀ и R₀ подвергаются первому раунду шифрования. На выходе первого раунда получаются два выходных подблока L_xи R_x, полученные в соответствии с выражением:

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

Подблоки L_xи R_xявляются входными для второго раунда шифрования,

на выходе которого получаются подблоки L₂ и R₂. Далее производиться

объединение подблоков L₂\\R₂ в блок, который подвергается перестановке,

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

2. Алгоритм формирования раундовых ключей. Основной 10-битный ключ шифра к₍₀₎ используется для генерирования двух раундовых 8-битных

ключей £_(8)i и £₍₈₎₂. Основной ключ шифра к₍₀₎, биты которого пронумерованы

от 0 до 9, подвергается перестановке РС-1, определяемой табл. 2.

Таблица 2 - Перестановка РС-1

Верхняя строка таблицы определяют биты (9,7,3,8,0) подблока С₀ , а нижняя - биты (2,6,5,1,4) подблока D₀ . Подблоки С₀ и D₀ подвергаются единичному сдвигу влево, результатом которого является подблоки С₁ и D₁ . Результат объединения подблоков С₁ || D₁ подвергается перестановке, в соответствии с табл. 3.

Таблица 3 – Перестановка РС-2

5 3 9 7 2 8 6 4

Результатом перестановки РС-2 является первый раундовый ключ £₍₈₎ . Процедура формирования второго раундового ключа &₍₈₎ аналогична, отличие

заключается в том, что подблоки С ₁ и Дподвергаются двум сдвигам влево.

3. Функция усложнения. На рис. 2 представлена схема функции усложнения

Вначале 4-х битный подблок подвергается перестановке с расширением (РЕ), в соответствии с табл. 4, на выходе которой получается 8-ми битный блок. Полученный результат складывается по mod2 с битами 8-ми битного раундового ключа £₍₈₎., / =1,2 и подвергается перестановке в блоках замены ^₀

и S1 (см. табл. 5 и табл. 6).

Таблица 4 – Перестановка с расширением РЕ

3 0 1 2 1 2 3 0

Таблица 5 – Блок замены S₀

Таблица 6 – Блок замены S₁

s0	№ столбца
№ строки

s1	№ столбца
№ строки

Причем, результат операции сложения по mod2 затем разбивается на два подблока, первые четыре бита (0,1,2,3) образуют подблок В₀, оставшиеся биты

(4,5,6,7) образуют подблок В₁ . Подблоки В₀ и В₁ подвергаются

преобразованию в блоках замены S₀ и S₁ , соответственно. Крайние биты

входного 4-битного подблока определяют строку таблицы, а средние биты – столбец. После преобразования в блоках замены выходные 2-битные подблоки объединяются S₀(B₀) || S₁(B₁). Полученный 4-битный подблок подвергается перестановке (Р), в соответствии с табл. 7.

Таблица 7 – Перестановка (Р)

1 0 3 2

Результатом перестановки будет выходное значение функции усложнения y/$Li,k($)is г = 1,2.

Метод линейного криптоанализа. Метод линейного криптоанализа разработан в 1993 году японским криптологом Митсуру Матсуи. В первоначальном виде этот метод сформулирован применительно к криптосистеме DES, в настоящее время создаются новые модификации этого метода [4].

Идея метода линейного криптоанализа основана на том, что существует возможность заменить нелинейную функцию криптографического преобразования ее линейным аналогом. Линейный криптоанализ базируется на знании криптоаналитиком пар «открытый текст-криптограмма», а также алгоритма шифрования.

Будем считать, что при генерации исходного текста Х случайные биты независимы и равновероятны P(x_t =l) = p, P(x_t = 0) = 1 - р, р = 0,5. Линейным статистически аналогом (или приближенным линейным аналогом) называется выражение:

п

п

Величина A = |l-2/?|называется эффективностью линейного аналога, а коэффициенты щ = 6{Д , b_t = Gfcl', c_k = $1 - параметрами линейного аналога.

По существу Ахарактеризует степень линейности функции криптографического преобразования и имеет максимальное значение Amax ⁼0,5. При применении метода линейного криптоанализа решаются две взаимосвязанные задачи:

1) нахождение эффективного линейного статистического аналога и вычисление его вероятности;

2) определение ключа (или нескольких бит ключа) с использованием эффективного линейного статистического аналога.

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

1. Тщательно анализируется криптографическая функция и определяется множество линейных статистических аналогов. На этом шаге в первую очередь анализируются S-блоки функции усложнения ц/. Для этого формируются

таблицы значений Q_t (/, j), где: t = 0,1 - номер S-блока, г= 14, j= 1,2 . Значение Q_t{i,j) представляет собой количество совпадений суммы по mod2 некоторых битов входных данных с суммой по mod2 некоторых битов выходных данных. В ходе анализа прослеживаются все возможные комбинации двоичных векторов i,y . Каждая пара векторов используется в качестве маски, которая

накладывается на возможные пары «вход-выход» S-блока. Эти маски указывают на биты входа и выхода, которые необходимо сложить по mod2, а затем сравнить полученные результаты. Далее проводится анализ полученных

таблиц Q_t(i,j) и отыскиваются такие значения i*,j*, для которых выполняется условие:

Q_t(i*,j*):mxx\Q_t(i,j)-$. (2)

В соответствии с полученной парой \,j* , и учитывая в схеме алгоритма шифрования перестановки и сложение по mod2, формируется эффективный линейный статистический аналог:

Q{i J ) Тб

п п L

Я (X, 7) = X ajxj 0 X bjyj = Y.ckkk> ^рэа = ■ (3)

/=1 /=1 к=\

2. Генерируется множество независимых исходных текстов

и регистрируются соответствующие им криптограммы

у(1) у (2) у(М)

3. Для каждой пары х^(да),7^(да), т = \М вычисляется значение левой
части эффективного линейного статистического аналога:

f_{X{rn)_jm) ₌ ^_а*_хт _@ ^_ъ*_ут (4)

4. Определяется частота получения «1» при вычислении Мзначений (4):

1 ^м

v^I^^jW), (5)

и строится оценка максимального правдоподобия в соответствии с правилом:

1, v>0,5,
d = \ (6)

[0, v<0,5.

5. Строится система линейных уравнений, причем каждое уравнение системы представляет собой равенство правой части (4) и соответствующего значения (6)

L

Y.cl^kk=d- (7)

к1 Единственное решение полученной системы (7) используется в качестве

оценки ключа к* =к₁X₂,..Xl-

Порядок выполнения работы

Практическаяработа выполняется с использование программы «Cryptoanaliz».

2.1. При подготовке к практической работе

На этапе подготовки к практической работе студенты должны, используя литературу [1-4], материалы лекций углубить свои знания по следующим вопросам: блочные симметричные криптосистемы (определение, основные характеристики, достоинства и недостатки), блочная криптосистема S-DES, метод линейного криптоанализа блочных криптосистем, а также изучить инструкцию по использованию программы «Cryptoanaliz».

2.2. Во время проведения занятия

Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к практической работе. Преподаватель разбивает группу студентов на 5 подгрупп, для каждой подгруппы определяется номер индивидуального задания на предстоящую лабораторную работу. Варианты индивидуальных заданий заложены в программе «Cryptoanaliz».

В процессе выполнения работы студенты должны:

1. Запустить на исполнение программу «Cryptoanaliz» и пройти
предлагаемый контрольный тест.

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

3. Используя таблицы Q₀ и Q₁, и учитывая таблицы перестановки и

сложение по mod2, студенты определяют эффективные линейные аналоги и вычисляют их вероятности. Полученный результат студенты заносят в табл 8.

Таблица 8 – Эффективные линейные статистические аналоги

№ блока	Эффективный линейный аналог	р	^ = 1-2р\
^0

S\

4. Для каждого из полученных линейных аналогов студенты определяют
в соответствии с выражениями (5), (6) значение правой части уравнений
используя модуль «Анализ».

5. Используя полученные результаты, студенты формируют систему уравнений (7). Решение системы уравнений позволяет определить все или часть битов 8-битных раундовых ключей. Используя алгоритм формирования раундовых ключей криптосистемы S-DES, студенты определяют основный 10-битный ключ шифра. Возможные варианты 10-битного ключа шифра и соответствующие ему 8-битные раундовые ключи студенты заносят в отчет по практической работе.

6. Используя модуль «Проверка» студенты проверяют правильность каждого из полученных вариантов ключей шифра.

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

Содержание отчета

Отчет должен включать в себя следующие пункты:

1. Схему блочной криптосистемы S-DES и исходные данные
индивидуального задания.

2. Таблицы статистического анализа Q₀ и Q₁, и таблицу с эффективными линейными статистическими аналогами (табл. 8).

3. Систему линейных уравнений для определения битов ключа.

4. Варианты полученных ключей.

5. Результат проверки подтверждающий правильность определенного в
работе ключа.

Контрольные вопросы

1. Блочные криптосистемы. Принципы построения. Достоинства и
недостатки.

2. Режимы применения блочных криптосистем.

3. Схема Фейстеля.

4. Методы усложнения блочных шифров.

5. Криптосистема DES.

6. Криптосистема ГОСТ 28147 - 89.

7. Основная идея метода линейного криптоанализа.

8. Понятие эффективного линейного статистического аналога.

9. Методика применения линейного криптоанализа.

Литература

1. Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – 2-е изд. – М.: Горячая линия – Телеком, 2002.

2. Харин Ю.С., Беник В.И, Матвеев Г.В., Агиевич С.В. Математические и компьютерные основы криптологии: Учеб. пособие. – Минск: Новое знание, 2003.

3. Бабенко Л.К., Мишустина Е.А. Лабораторный практикум по изучению современных методов криптоанализа по курсу «Криптографические методы и средства обеспечения защиты информации». – Таганрог: Изд-во ТРТУ, 2003.

4. Бабенко Л.К., Мишустина Е.А. Изучение современных методов криптоанализа. Методическое пособие. – Таганрог: Изд-во ТРТУ, 2003