Криптографические методы. Методические указания по выполнению лабораторных работ, задания на выполнение лабораторных работ, требования к отчету, а также основные теоретические сведения по каждой работе

• Название: Методические указания по выполнению лабораторных работ, задания на выполнение лабораторных работ, требования к отчету, а также основные теоретические сведения по каждой работе
• Анкор: Криптографические методы
• Дата: 01.03.2023
• Размер: 0.75 Mb.
• Имя файла: Криптографические методы.pdf
• Тип: Методические указания; #961472
• страница: 2 из 4

2 Порядок выполнения работы
2.1. При подготовке к лабораторной работе
На этапе подготовки к лабораторной работе студенты должны, используя литературу [1,2,3,4], материалы лекций углубить свои знания по следующим вопросам: криптосистема Виженера; методы определения периода ключевой последовательности; методы бесключевого чтения (метод «протяжки» вероятного слова, метод чтения в колонках).
Студенты на предстоящее лабораторное занятие готовят алфавиты русского и английского языка со значениями вероятностей встречаемости символов.
2.2. Во время проведения занятия
Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к лабораторной работе. Затем преподаватель разбивает группу студентов на подгруппы по два человека.
Каждая подгруппа получает от преподавателя индивидуальный вариант задания на лабораторную работу, который представляет собой криптограммы, зашифрованные с помощью криптосистемы Виженера.

11
Лабораторная работа состоит из двух частей. В первой части работы студенты дешифрируют первую заданную криптограмму с использованием первого метода Фридмана и метода чтения в колонках. При этом студенты должны: определить период ключевой последовательности с помощью первого метода Фридмана; используя метод чтения в колонках для заданного случая дешифрировать первую криптограмму. Вторая часть работы заключается в дешифровании второй криптограммы с применением второго метода Фридмана и метода «протяжки» вероятного слова. На этом этапе студенты должны: используя второй метод
Фридмана определить период ключевой последовательности; на основании вычисленного значения периода ключевой последовательности используя метод «протяжки» вероятного слова дешифрировать вторую криптограмму.
Если в результате дешифрирования заданных криптограмм получены осмысленные тексты, студенты оформляют отчет и представляют его преподавателю.
3 Содержание отчета
Отчет должен включать в себя следующие пункты:
1. Задание на выполнение лабораторной работы (исходные криптограммы).
2. Основные расчетные соотношения.
3. Результаты расчетов, представленные в виде табл. 1 и 2.
4. Результаты анализа, т.е. дешифрованные криптограммы.
4 Контрольные вопросы
1. Основные понятия криптографии и криптоанализа.
2. Методы Фридмана.
3. Метод «протяжки» вероятного слова, метод чтения в колонках.
4. Понятие индекса совпадения.
5. Криптосистема Виженера.
6.
Связь криптосистемы Виженера с другими простейшими криптосистемами.
Литература
1. Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации. Учебное пособие для вузов. М.: Горячая линия – Телеком, 2005.
2. Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – 2-е изд. – М.: Горячая линия – Телеком, 2002.
3. Осипян В.О, Осипян К.В. Криптография в задачах и упражнениях. –
М.: Гелиос АРВ, 2004.
4. Харин Ю.С., Беник В.И, Матвеев Г.В., Агиевич С.В. Математические и компьютерные основы криптологии: Учеб. пособие. – Минск: Новое знание,
2003.

12
Лабораторная работа №3
Изучение метода линейного криптоанализа блочных симметричных
криптосистем
Цель работы – закрепление теоретических знаний и практическое освоение метода линейного криптоанализа блочных симметричных криптосистем на примере криптосистемы S-DES.
Время - 4 часа.
1 Основные теоретические сведения
Блочные симметричные криптосистемы (БСК) представляют собой семейство обратимых криптографических преобразований блоков (частей фиксированной дины) исходного текста.
В настоящее время разработано большое количество БСК, многие из которых являются национальными стандартами. Наибольшую известность приобрели системы DES, IDEA, AES (Rijndael), ГОСТ 28147-89. Эти системы находятся под пристальным вниманием криптоаналитиков, основной задачей которых является поиск «слабых мест» в этих системах.
В настоящей работе метод линейного криптоанализа
БСК рассматривается применительно к криптосистеме S-DES, являющейся упрощенной версией криптосистемы DES.
1. Алгоритм шифрования (расшифрования) криптосистемы S-DES. На рис. 1 иллюстрируется алгоритм шифрования (расшифрования).
Рисунок 1 – Схема алгоритма шифрования S-DES с сетью Фейстеля
Входной 8-битовый блок вначале подвергается начальной перестановке
(IP), в соответствии с табл.1. Биты подблока пронумерованы от 0 до 7, причем
0
L
0
R
1
L
0 0
1
)
,
(
L
k
R
R
k
Конечная перестановка
IP
-1
Схема Фейстеля
(2 раунда)
Начальная перестановка IP

13 бит с наибольшим порядковым номером 7 является младшим битом, и наоборот.
Таблица 1 – Начальная перестановка IP
7 6
4 0
2 5
1 3
Таблица разделена на две части, верхняя часть определяет подблок левых бит
0
L
, а нижняя часть определяет подблок правых бит
0
R
. Таким образом, после начальной перестановки IP, подблоки
0
L
и
0
R
подвергаются первому раунду шифрования. На выходе первого раунда получаются два выходных подблока
1
L
и
1
R
, полученные в соответствии с выражением:
)
,
(
;
1
)
8
(
0 0
1 0
1
k
R
L
R
R
L
Функция
, называемая функцией усложнения и аналогичная функции усложнения алгоритма DES, зависит от ключа, а ее вид будет описан ниже.
Подблоки
1
L
и
1
R
являются входными для второго раунда шифрования, на выходе которого получаются подблоки
2
L
и
2
R
. Далее производиться объединение подблоков
2
L
||
2
R
в блок, который подвергается перестановке, являющейся инверсией начальной перестановки. В результате получаем выходной блок криптограммы.
2. Алгоритм формирования раундовых ключей. Основной 10-битный ключ шифра
)
10
(
k
используется для генерирования двух раундовых 8-битных ключей
1
)
8
(
k
и
2
)
8
(
k
. Основной ключ шифра
)
10
(
k
, биты которого пронумерованы от 0 до 9, подвергается перестановке РС-1, определяемой табл. 2.
Таблица 2 – Перестановка РС-1 9
7 3
8 0
2 6
5 1
4
Верхняя строка таблицы определяют биты (9,7,3,8,0) подблока
0
С
, а нижняя - биты (2,6,5,1,4) подблока
0
D
. Подблоки
0
С
и
0
D
подвергаются единичному сдвигу влево, результатом которого является подблоки
1
С
и
1
D
Результат объединения подблоков
1
С
||
1
D
подвергается перестановке, в соответствии с табл. 3.
Таблица 3 – Перестановка РС-2 5
3 9
7 2
8 6
4

14
Результатом перестановки РС-2 является первый раундовый ключ
1
)
8
(
k
Процедура формирования второго раундового ключа
2
)
8
(
k
аналогична, отличие заключается в том, что подблоки
1
С
и
1
D
подвергаются двум сдвигам влево.
3. Функция усложнения. На рис. 2 представлена схема функции усложнения .
Рисунок 2 – Схема функции усложнения
Вначале 4-х битный подблок подвергается перестановке с расширением
(РE), в соответствии с табл. 4, на выходе которой получается 8-ми битный блок.
Полученный результат складывается по mod2 с битами 8-ми битного раундового ключа
i
k
)
8
(
,
2
,
1
i
и подвергается перестановке в блоках замены
0
S
и
1
S
(см. табл. 5 и табл. 6).
Таблица 4 – Перестановка с расширением РЕ
3 0 1
2 1
2 3
0
Таблица 5 – Блок замены
0
S
0
S
№ столбца
№ строки
0 1
2
3
0
1 0 2 3
1
3 1 0 2
2
2 0 3 1
3
1 3 2 0
Таблица 6 – Блок замены
1
S
1
S
№ столбца
№ строки
0
1
2
3
0
0 3
1 2
1
3 2
0 1
2
1 0
3 2
3
2 1
3 0
)
(
i
R
PE
0
S
1
S
P
4 4
8 4
8 2
2
i
R
k
)
,
(
k
R
i
4 4

15
Причем, результат операции сложения по mod2 затем разбивается на два подблока, первые четыре бита (0,1,2,3) образуют подблок
0
В , оставшиеся биты
(4,5,6,7) образуют подблок
1
В
. Подблоки
0
В и
1
В
подвергаются преобразованию в блоках замены
0
S
и
1
S
, соответственно. Крайние биты входного 4-битного подблока определяют строку таблицы, а средние биты – столбец. После преобразования в блоках замены выходные 2-битные подблоки объединяются
)
(
||
)
(
1 1
0 0
B
S
B
S
. Полученный 4-битный подблок подвергается перестановке (Р), в соответствии с табл. 7.
Таблица 7 – Перестановка (Р)
1 0
3 2
Результатом перестановки будет выходное значение функции усложнения
i
i
k
R
)
8
(
,
,
2
,
1
i
Метод линейного криптоанализа. Метод линейного криптоанализа разработан в 1993 году японским криптологом Митсуру Матсуи. В первоначальном виде этот метод сформулирован применительно к криптосистеме DES, в настоящее время создаются новые модификации этого метода [4].
Идея метода линейного криптоанализа основана на том, что существует возможность заменить нелинейную функцию криптографического преобразования ее линейным аналогом. Линейный криптоанализ базируется на знании криптоаналитиком пар «открытый текст-криптограмма», а также алгоритма шифрования.
Будем считать, что при генерации исходного текста Х случайные биты независимы и равновероятны
p
x
P
i
)
1
(
,
p
x
P
i
1
)
0
(
,
5
,
0
p
. Линейным
статистически аналогом (или приближенным линейным аналогом) называется выражение:
L
k
k
k
n
i
j
i
n
i
i
i
k
c
y
b
x
a
Y
X
1 1
1
)
,
(
,
(1) если вероятность
5
,
0
))
,
(
,
(
1
L
k
k
k
k
c
K
X
f
X
P
Величина
p
2 1
называется эффективностью линейного аналога, а коэффициенты
1
,
0
i
a
,
1
,
0
i
b
,
1
,
0
k
c
- параметрами линейного аналога.
По существу характеризует степень линейности функции криптографического преобразования и имеет максимальное значение
5
,
0
max
. При применении метода линейного криптоанализа решаются две взаимосвязанные задачи:

16 1) нахождение эффективного линейного статистического аналога и вычисление его вероятности;
2) определение ключа (или нескольких бит ключа) с использованием эффективного линейного статистического аналога.
Практическая реализация метода линейного криптоанализа связана с реализацией следующих последовательных шагов.
1. Тщательно анализируется криптографическая функция и определяется множество линейных статистических аналогов. На этом шаге в первую очередь анализируются S-блоки функции усложнения
. Для этого формируются таблицы значений
)
,
(
j
i
Q
t
, где:
1
,
0
t
- номер S-блока,
4
,
1
i
,
2
,
1
j
. Значение
)
,
( j
i
Q
t
представляет собой количество совпадений суммы по mod2 некоторых битов входных данных с суммой по mod2 некоторых битов выходных данных.
В ходе анализа прослеживаются все возможные комбинации двоичных векторов
j
i,
. Каждая пара векторов используется в качестве маски, которая накладывается на возможные пары «вход-выход» S-блока. Эти маски указывают на биты входа и выхода, которые необходимо сложить по mod2, а затем сравнить полученные результаты. Далее проводится анализ полученных таблиц
)
,
( j
i
Q
t
и отыскиваются такие значения
j
i ,
, для которых выполняется условие:
8
)
,
(
max
:
)
,
(
j
i
Q
j
i
Q
t
t
(2)
В соответствии с полученной парой
j
i ,
, и учитывая в схеме алгоритма шифрования перестановки и сложение по mod2, формируется эффективный линейный статистический аналог:
L
k
k
k
n
i
j
i
n
i
i
i
k
c
y
b
x
a
Y
X
1 1
1
)
,
(
,
16
)
,
(
j
i
Q
P
эа
(3)
2.
Генерируется множество независимых исходных текстов
)
(
)
2
(
)
1
(
,...,
,
M
X
X
X
и регистрируются соответствующие им криптограммы
)
(
)
2
(
)
1
(
,...,
,
M
Y
Y
Y
3. Для каждой пары
)
(
)
(
,
m
m
Y
X
,
M
m
,
1
вычисляется значение левой части эффективного линейного статистического аналога:
n
i
m
i
i
n
i
m
i
i
M
m
y
b
x
a
Y
X
1 1
)
(
)
(
)
,
(
(4)
4. Определяется частота получения «1» при вычислении M значений (4):
M
m
m
m
Y
X
M
1
)
(
)
(
)
,
(
1
,
(5) и строится оценка максимального правдоподобия в соответствии с правилом:

17 5
,
0
,
0
,
5
,
0
,
1
d
(6)
5. Строится система линейных уравнений, причем каждое уравнение системы представляет собой равенство правой части (4) и соответствующего значения (6)
L
k
k
k
d
k
c
1
(7)
Единственное решение полученной системы (7) используется в качестве оценки ключа
L
k
k
k
k
,...,
,
2 1
2 Порядок выполнения работы
Лабораторная работа выполняется с использование программы
«Cryptoanaliz».
2.1. При подготовке к лабораторной работе
На этапе подготовки к лабораторной работе студенты должны, используя литературу [1-4], материалы лекций углубить свои знания по следующим вопросам: блочные симметричные криптосистемы (определение, основные характеристики, достоинства и недостатки), блочная криптосистема S-DES, метод линейного криптоанализа блочных криптосистем, а также изучить инструкцию по использованию программы «Cryptoanaliz».
2.2. Во время проведения занятия
Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к лабораторной работе.
Преподаватель разбивает группу студентов на 5 подгрупп, для каждой подгруппы определяется номер индивидуального задания на предстоящую лабораторную работу. Варианты индивидуальных заданий заложены в программе «Cryptoanaliz».
В процессе выполнения работы студенты должны:
1. Запустить на исполнение программу «Cryptoanaliz» и пройти предлагаемый контрольный тест.
2. В соответствии с заданием определенным преподавателем студенты выбирают номер варианта, количество известных текстов и осуществляют зашифрование случайным образом сгенерированных открытых текстов.
3. Используя таблицы
0
Q
и
1
Q
, и учитывая таблицы перестановки и сложение по mod2, студенты определяют эффективные линейные аналоги и вычисляют их вероятности. Полученный результат студенты заносят в табл 8.
Таблица 8 – Эффективные линейные статистические аналоги
№ блока
Эффективный линейный аналог
р
р
2 1
0
S

18 1
S
4. Для каждого из полученных линейных аналогов студенты определяют в соответствии с выражениями (5), (6) значение правой части уравнений используя модуль «Анализ».
5. Используя полученные результаты, студенты формируют систему уравнений (7). Решение системы уравнений позволяет определить все или часть битов 8-битных раундовых ключей. Используя алгоритм формирования раундовых ключей криптосистемы S-DES, студенты определяют основный 10- битный ключ шифра. Возможные варианты 10-битного ключа шифра и соответствующие ему 8-битные раундовые ключи студенты заносят в отчет по лабораторной работе.
6. Используя модуль «Проверка» студенты проверяют правильность каждого из полученных вариантов ключей шифра.
7. При совпадении результатов анализа с истинным ключом шифра студенты оформляют, в соответствии с требованиями настоящего пособия отчет и представляют его преподавателю для защиты.
3 Содержание отчета
Отчет должен включать в себя следующие пункты:
1. Схему блочной криптосистемы S-DES и исходные данные индивидуального задания.
2. Таблицы статистического анализа
0
Q
и
1
Q
, и таблицу с эффективными линейными статистическими аналогами (табл. 8).
3. Систему линейных уравнений для определения битов ключа.
4. Варианты полученных ключей.
5. Результат проверки подтверждающий правильность определенного в работе ключа.