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

• ⇐ Назад
11
12
13
14
15
16
17
18
19
202122
23
24
25
26
Далее ⇒

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

В настоящее время разработано большое количество БСК, многие из которых являются национальными стандартами. Наибольшую известность приобрели системы 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

---

• ⇐ Назад
11
12
13
14
15
16
17
18
19
202122
23
24
25
26
Далее ⇒