Блочные симметричные криптосистемы (БСК) представляют собой семейство обратимых криптографических преобразований блоков (частей фиксированной дины) исходного текста.
В настоящее время разработано большое количество БСК, многие из которых являются национальными стандартами. Наибольшую известность приобрели системы DES, IDEA, AES (Rijndael), ГОСТ 28147-89. Эти системы находятся под пристальным вниманием криптоаналитиков, основной задачей которых является поиск «слабых мест» в этих системах.
В настоящей работе метод линейного криптоанализа БСК
рассматривается применительно к криптосистеме S-DES, являющейся упрощенной версией криптосистемы DES.
1. Алгоритм шифрования (расшифрования) криптосистемы S-DES. На рис. 1 иллюстрируется алгоритм шифрования (расшифрования).
|
| L | к | R | ||
| i | г | |||
| к |
Rl=il/(R0^k)®L0
Рисунок 1 – Схема алгоритма шифрования S-DES с сетью Фейстеля
Входной 8-битовый блок вначале подвергается начальной перестановке (IP), в соответствии с табл.1. Биты подблока пронумерованы от 0 до 7, причем
бит с наибольшим порядковым номером наоборот.
Таблица 1 – Начальная перестановка IP
7 6 4 0 2 5 1 3
7 является младшим битом, и
Таблица разделена на две части, верхняя часть определяет подблок левых бит L0, а нижняя часть определяет подблок правых бит R0. Таким образом,
после начальной перестановки IP, подблоки L0 и R0 подвергаются первому раунду шифрования. На выходе первого раунда получаются два выходных подблока L x и Rx, полученные в соответствии с выражением:
Функция у/, называемая функцией усложнения и аналогичная функции усложнения алгоритма DES, зависит от ключа, а ее вид будет описан ниже.
Подблоки L x и R x являются входными для второго раунда шифрования,
на выходе которого получаются подблоки L2 и R2. Далее производиться
объединение подблоков L2\\R2 в блок, который подвергается перестановке,
являющейся инверсией начальной перестановки. В результате получаем выходной блок криптограммы.
2. Алгоритм формирования раундовых ключей. Основной 10-битный ключ шифра к (0) используется для генерирования двух раундовых 8-битных
ключей £(8)i и £(8)2. Основной ключ шифра к (0), биты которого пронумерованы
от 0 до 9, подвергается перестановке РС-1, определяемой табл. 2.
Таблица 2 - Перестановка РС-1
Верхняя строка таблицы определяют биты (9,7,3,8,0) подблока С 0, а нижняя - биты (2,6,5,1,4) подблока D 0. Подблоки С 0 и D 0 подвергаются единичному сдвигу влево, результатом которого является подблоки С 1 и D 1. Результат объединения подблоков С 1 || D 1 подвергается перестановке, в соответствии с табл. 3.
Таблица 3 – Перестановка РС-2
5 3 9 7 2 8 6 4
Результатом перестановки РС-2 является первый раундовый ключ £(8). Процедура формирования второго раундового ключа &(8) аналогична, отличие
заключается в том, что подблоки С 1 и Д подвергаются двум сдвигам влево.
3. Функция усложнения. На рис. 2 представлена схема функции усложнения
Вначале 4-х битный подблок подвергается перестановке с расширением (РЕ), в соответствии с табл. 4, на выходе которой получается 8-ми битный блок. Полученный результат складывается по mod2 с битами 8-ми битного раундового ключа £(8)., / = 1,2 и подвергается перестановке в блоках замены ^ 0
и S1 (см. табл. 5 и табл. 6).
Таблица 4 – Перестановка с расширением РЕ
3 0 1 2 1 2 3 0
Таблица 5 – Блок замены S 0
Таблица 6 – Блок замены S 1
| s0 | № столбца | |||
| № строки | ||||
| s 1 | № столбца | |||
| № строки | ||||
Причем, результат операции сложения по mod2 затем разбивается на два подблока, первые четыре бита (0,1,2,3) образуют подблок В 0, оставшиеся биты
(4,5,6,7) образуют подблок В 1. Подблоки В 0 и В 1 подвергаются
преобразованию в блоках замены S 0 и S 1, соответственно. Крайние биты
входного 4-битного подблока определяют строку таблицы, а средние биты – столбец. После преобразования в блоках замены выходные 2-битные подблоки объединяются S 0(B 0) || S 1(B 1). Полученный 4-битный подблок подвергается перестановке (Р), в соответствии с табл. 7.
Таблица 7 – Перестановка (Р)
1 0 3 2
Результатом перестановки будет выходное значение функции усложнения y/$Li,k($)is г = 1,2.
Метод линейного криптоанализа. Метод линейного криптоанализа разработан в 1993 году японским криптологом Митсуру Матсуи. В первоначальном виде этот метод сформулирован применительно к криптосистеме DES, в настоящее время создаются новые модификации этого метода [4].
Идея метода линейного криптоанализа основана на том, что существует возможность заменить нелинейную функцию криптографического преобразования ее линейным аналогом. Линейный криптоанализ базируется на знании криптоаналитиком пар «открытый текст-криптограмма», а также алгоритма шифрования.
Будем считать, что при генерации исходного текста Х случайные биты независимы и равновероятны P(xt =l) = p, P(xt = 0) = 1 - р, р = 0,5. Линейным статистически аналогом (или приближенным линейным аналогом) называется выражение:
| п |
| п |
Величина A = |l- 2 /?| называется эффективностью линейного аналога, а коэффициенты щ = 6{Д, bt = Gfcl ', ck = $1 - параметрами линейного аналога.
По существу А характеризует степень линейности функции криптографического преобразования и имеет максимальное значение Amax = 0,5. При применении метода линейного криптоанализа решаются две взаимосвязанные задачи:
1) нахождение эффективного линейного статистического аналога и вычисление его вероятности;
2) определение ключа (или нескольких бит ключа) с использованием эффективного линейного статистического аналога.
Практическая реализация метода линейного криптоанализа связана с реализацией следующих последовательных шагов.
1. Тщательно анализируется криптографическая функция и определяется множество линейных статистических аналогов. На этом шаге в первую очередь анализируются S-блоки функции усложнения ц/. Для этого формируются
таблицы значений Qt (/, j), где: t = 0,1 - номер S-блока, г= 14, j= 1,2. Значение Qt{i,j) представляет собой количество совпадений суммы по mod2 некоторых битов входных данных с суммой по mod2 некоторых битов выходных данных. В ходе анализа прослеживаются все возможные комбинации двоичных векторов i,y. Каждая пара векторов используется в качестве маски, которая
накладывается на возможные пары «вход-выход» S-блока. Эти маски указывают на биты входа и выхода, которые необходимо сложить по mod2, а затем сравнить полученные результаты. Далее проводится анализ полученных
таблиц Qt(i,j) и отыскиваются такие значения i*,j*, для которых выполняется условие:
Qt(i*,j*):mxx\Qt(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.clkk=d- (7)
к 1 Единственное решение полученной системы (7) используется в качестве
оценки ключа к* =к 1 X 2,.. Xl-
Порядок выполнения работы
Практическаяработа выполняется с использование программы «Cryptoanaliz».
2.1. При подготовке к практической работе
На этапе подготовки к практической работе студенты должны, используя литературу [1-4], материалы лекций углубить свои знания по следующим вопросам: блочные симметричные криптосистемы (определение, основные характеристики, достоинства и недостатки), блочная криптосистема S-DES, метод линейного криптоанализа блочных криптосистем, а также изучить инструкцию по использованию программы «Cryptoanaliz».
2.2. Во время проведения занятия
Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к практической работе. Преподаватель разбивает группу студентов на 5 подгрупп, для каждой подгруппы определяется номер индивидуального задания на предстоящую лабораторную работу. Варианты индивидуальных заданий заложены в программе «Cryptoanaliz».
В процессе выполнения работы студенты должны:
1. Запустить на исполнение программу «Cryptoanaliz» и пройти
предлагаемый контрольный тест.
2. В соответствии с заданием определенным преподавателем студенты выбирают номер варианта, количество известных текстов и осуществляют зашифрование случайным образом сгенерированных открытых текстов.
3. Используя таблицы Q0 и Q1, и учитывая таблицы перестановки и
сложение по 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 0 и Q 1, и таблицу с эффективными линейными статистическими аналогами (табл. 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
