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

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

4 Контрольные вопросы
1. Блочные криптосистемы. Принципы построения. Достоинства и недостатки.
2. Режимы применения блочных криптосистем.
3. Схема Фейстеля.
4. Методы усложнения блочных шифров.
5. Криптосистема DES.
6. Криптосистема ГОСТ 28147 - 89.
7. Основная идея метода линейного криптоанализа.
8. Понятие эффективного линейного статистического аналога.
9. Методика применения линейного криптоанализа.
Литература

19 1. Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – 2-е изд. – М.: Горячая линия – Телеком, 2002.
2. Харин Ю.С., Беник В.И, Матвеев Г.В., Агиевич С.В. Математические и компьютерные основы криптологии: Учеб. пособие. – Минск: Новое знание,
2003.
3. Бабенко Л.К., Мишустина Е.А. Лабораторный практикум по изучению современных методов криптоанализа по курсу «Криптографические методы и средства обеспечения защиты информации». – Таганрог: Изд-во ТРТУ, 2003.
4. Бабенко Л.К., Мишустина Е.А. Изучение современных методов криптоанализа. Методическое пособие. – Таганрог: Изд-во ТРТУ, 2003
Лабораторная работа №4
Изучение метода дифференциального (разностного) криптоанализа
блочных симметричных криптосистем
Цель работы – закрепление теоретических знаний и практическое освоение метода дифференциального (разностного) криптоанализа блочных симметричных криптосистем на примере криптосистемы S-DES.
Время - 4 часа.
1 Основные теоретические сведения
Криптосистема S-DES подробно рассмотрена в лабораторной работе №3.
Метод дифференциального (разностного) криптоанализа предложен
Э. Байхэмом и А. Шамиром, и, по мнению ряда специалистов компании IBM, является общим методом криптоанализа блочно-итерационных криптосистем.
Идея заключается в анализе процесса изменения несходства для пары открытых текстов
X
X
X
, имеющих определенные исходные различия, в процессе прохождения через циклы шифрования с одним и тем же ключом.
Пусть задана пара входов X и Х , с несходством
Х
Х
Х
. Известны перестановка IP и перестановка с расширением Е, а следовательно, известны и несходства А на входе блоков замены
0
S
и
1
S
. Выходы Y и Y известны, следовательно, известно и несходство
Y
Y
Y
, а значит, при известных перестановках
1
IP
и P известны несходства ΔС на выходе блоков замены
0
S
и
1
S
Доказано, что для любого заданного ΔA не все значения ΔС равновероятны. Комбинация ΔА и ΔС позволяет предположить значения битов для
i
k
Х
Е
)
(
и
i
k
Х
Е
)
(
. То, что E(X) и
)
( Х
Е
известны, дает информацию о
i
k
Несходство различных пар открытых текстов приводит к несходству получаемых шифр-текстов с определенной вероятностью. Эти вероятности

20 можно определить, построив таблицы для каждого из блоков замены. Таблицы сроятся по следующему принципу: по вертикали располагаются все возможные комбинации А , по горизонтали – все возможные комбинации ΔС, а на пересечении – число соответствий данного ΔС данному А .
Число наибольших совпадений указывает нам пару ΔA и ΔС, с помощью которой можно определить секретный ключ. Пара открытых текстов, соответствующих данным ΔА и ΔС называется правильной парой, а пара открытых текстов, не соответствующих данным ΔA и ΔС – неправильной парой.
Правильная пара подскажет правильный ключ цикла, а неправильная пара – случайный. Чтобы найти правильный ключ, необходимо просто собрать достаточное число предположений. Один из подключей будет встречаться чаще, чем все остальные. Фактически правильный подключ появляется из всех возможных случайных подключей.
2 Порядок выполнения работы
Лабораторная работа выполняется с использование программы
«Cryptoanaliz».
2.1. При подготовке к лабораторной работе
На этапе подготовки к лабораторной работе студенты должны, используя литературу [1-4], материалы лекций углубить свои знания по следующим вопросам: блочные симметричные криптосистемы (определение, основные характеристики, достоинства и недостатки), блочная криптосистема S-DES, метод дифференциального
(разностного) криптоанализа блочных криптосистем, а также изучить инструкцию по использованию программы
«Cryptoanaliz».
2.2. Во время проведения занятия
Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к лабораторной работе.
Преподаватель разбивает группу студентов на 5 подгрупп, для каждой подгруппы определяется номер индивидуального задания на предстоящую лабораторную работу. Варианты индивидуальных заданий заложены в программе «Cryptoanaliz».
В процессе выполнения работы студенты должны:
1. Запустить на исполнение программу «Cryptoanaliz» и пройти предлагаемый контрольный тест.
2. В соответствии с заданием определенным преподавателем студенты выбирают номер варианта и количество известных текстов.
3. Используя таблицы анализа несходств (
C
A,
) для блоков замены
0
S
и
1
S
студенты определяют оптимальный дифференциал (
C
A ,
) и осуществляют зашифрование случайным образом сгенерированных открытых

21 текстов.
Программа выбирает из множества пар текстов пары удовлетворяющие оптимальному дифференциалу (
C
A ,
) и представляет их в виде в табл. 1.
Таблица 1 – Пары текстов удовлетворяющие оптимальному дифференциалу
№
X
)
( Х
Е
))
(
(
Х
Е
S
Y
1
…
№
X
)
( Х
Е
))
(
(
Х
Е
S
Y
1
…
4. Студенты анализируют пары открытых текстов и определяют множество раундовых ключей шифра и, соответственно, множество основных ключей шифра. Ключ, получаемый чаще остальных и будет наиболее вероятным ключом шифра.
5. Используя модуль «Проверка» студенты проверяют правильность определенного анализом ключей шифра.
6. При совпадении результатов анализа с истинным ключом шифра студенты оформляют, в соответствии с требованиями настоящего пособия отчет и представляют его преподавателю для защиты.
4 Содержание отчета
Отчет должен включать в себя следующие пункты:
1. Структуру алгоритма S-DES и таблицы перестановок и замен, соответствующие заданному варианту.
2. Результаты анализа таблиц замен
0
S
и
1
S
3. Результаты анализа пар открытых текстов.
4. Множество возможных раундовых ключей.
5. Результаты проверки, подтверждающие правильность определенного в работе ключа.
5 Контрольные вопросы
1. Основные понятия криптографии и криптоанализа.
2. Понятие блочной симметричной криптосистемы.
3. Основные характеристики блочных симметричных криптосистем.
4. Метод дифференциального (разностного) криптоанализа.
Литература
1. Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – 2-е изд. – М.: Горячая линия – Телеком, 2002.

22 2. Харин
Ю.С., Беник В.И, Матвеев Г.В., Агиевич С.В.
Математические и компьютерные основы криптологии: Учеб. пособие. –
Минск: Новое знание, 2003.
3. Бабенко Л.К., Мишустина Е.А. Лабораторный практикум по изучению современных методов криптоанализа по курсу «Криптографические методы и средства обеспечения защиты информации». – Таганрог: Изд-во
ТРТУ, 2003.
4. Бабенко Л.К., Мишустина Е.А. Изучение современных методов криптоанализа. Методическое пособие. – Таганрог: Изд-во ТРТУ, 2003
Лабораторная работа №5
Методы оценки качества криптографических генераторов
Цель работы – закрепление теоретических знаний и практическое освоение методов оценки качества криптографических генераторов.
Время - 4 часа.
1 Основные теоретические сведения
Криптографический генератор – это аппаратно или программно реализованный имитатор источника равномерно распределенной случайной последовательности (РРСП) чисел, которая вычисляется по известному детерминированному рекуррентному соотношению. Основное требование к выходной последовательности
i
х
криптографического генератора,
,
0
i
, состоит в минимальных отличиях по статистическим характеристикам последовательности
i
х
от РРСП.
Тесты, применяемые для оценки качества КГ, делятся на графические и оценочные [3].
К графическим тестам относится: гистограмма распределения элементов последовательности; распределение на плоскости; проверка серий; автокорреляционная функция; графический спектральный тест; проверка на монотонность; профиль линейной сложности.
Гистограмма распределения элементов – данный метод позволяет оценить равномерность распределения символов, а также определить частоту появления каждого символа. Для исследуемой последовательности
n
i
i
,
1
,
подсчитывается сколько раз встречается каждый элемент, после чего строиться график зависимости числа появления элементов от их численного представления.
Распределение на плоскости – метод предназначен для определения зависимостей между элементами последовательностей.
Построение распределение на плоскости осуществляется по правилу
)
1
(
,
1
,
,
1
n
i
i
i
Если между элементами последовательности связь отсутствует, то точки на плоскости расположены хаотично, в случае когда на плоскости наблюдаются

23
«узоры» - между элементами последовательности существует взаимосвязь, т.е. последовательность не является случайной.
Проверка серий – данный метод позволяет оценить равномерность распределения символов в исследуемой последовательности на основе анализа частоты появления нулей и единиц и серий состоящих из k бит. Построение осуществляется следующим образом: подсчитывается сколько раз проявляются нули, единицы, серии-двойки (00, 01, 10, 11), серии-тройки (000, 001, 010, 011,
100, 111) и т.д. в битовом представлении исследуемой последовательности
n
i
i
,
1
,
Результат представляется в графическом виде.
У последовательности, чьи свойства близки к свойствами РРСП разбросы между числом появлений нулей и единиц, между числом появлений серий каждого вида должны стремиться к нулю.
Проверка на монотонность – данный метод позволяет оценить равномерность распределения символов. В исследуемой последовательности на основе анализа длин участков невозрастания и неубывания элементов последовательности.
Исследуемая последовательность
n
i
i
,
1
,
представляется в виде непересекающихся участков невозрастания и неубывания следующих друг за другом. У последовательности, чьи свойства близки к свойствам РРСП вероятность появления участка невозрастания
(неубывания) обратно пропорциональна его длине.
Автокорреляционная функция (АКФ) – данный метод предназначен для оценки корреляции между сдвинутыми копиями исследуемой последовательности
n
i
i
,
1
,
. Метод позволяет обнаруживать зависимость между подпоследовательностями исследуемой последовательности. Битовая
АКФ. Исследуемая последовательность
n
i
i
,
1
,
представляется в битовом виде и затем нормируется по правилу
n
i
i
i
,
1
,
)
1
(

1
. После этого вычисляются всплески корреляции:
n
i
i
n
i
n
j
i
i
j
r
1 1
mod



,
n
j
,
1 .
Символьная АКФ. Исследуемая последовательность нормируется по правилу
n
i
R
j
j
a
i
i
,
1
,
2 1

1 0
, R - разрядность числа,
i
a
- двоичная запись
i го элемента исследуемой последовательности. Далее вычисляются всплески корреляции.
Для последовательности, чьи свойства близки к свойствам РРСП, значения всплесков корреляции должно стремиться к нулю, во всех точках, кроме тех,

24 чье значение кратно длине последовательности в символах (в битах) для символьной (битовой) АКФ.
Профиль линейной сложности – данный метод позволяет исследовать последовательность на случайность анализируя зависимость линейной сложности последовательности от ее длины. Для исследуемой двоичной последовательности
n
i
i
,
1
,
рассматриваются подпоследовательности
k
содержащие первые k элементов и строится графическая зависимость линейной сложности
L от длины подпоследовательности
k .
У последовательности, чьи свойства близки к свойствам РРСП линия графика должна стремиться к линии
2
k
L
Графический спектральный метод – данный метод позволяет определить равномерность распределения 0 и 1 в исследуемой последовательности на основе анализа высоты выбросов преобразования Фурье. Исследуемая двоичная последовательность
n
i
i
,
1
,
преобразуется по правилу
1 2

i
i
в последовательность
n
i
i
,
1
,

к которой применяется дискретное преобразование Фурье. У последовательности, чьи свойства близки к свойствам
РРСП число гармоник, чьи длительности значительно превышают среднюю длину гармоники должно стремиться к нулю.
Оценочные тесты, в отличии от графических тестов, позволяют по результатам тестирования сделать практически однозначный вывод о возможности использования криптографического генератора. Существует множество различных оценочных тестов, сгруппированных в наборы: тесты
Д.Кнута, тест DieHard, тест NIST и др. [3]. В настоящей лабораторной работе рассматриваются некоторые тесты, входящие в набор NIST.
Частотный тест (frequency test) служит для проверки равномерности появления 0 и 1 в исследуемой последовательности. В исследуемой последовательности длинной n подсчитывается количество нулей
0
n
и единиц
1
n
, а затем вычисляется их разница
0 1
n
n
S
n
Вычисляется статистика
n
S
s
n
и определяется значение
2
s
erfc
P
, где
x
d
e
x
erf
x
erfc
2 2
1
- дополнительный интеграл вероятностей,
x
d
e
x
erf
0 2
2
- функция ошибок.
Связь стандартного нормального распределения
x
и функции ошибок имеет вид:

25
x
x
erf
d
e
x
2 1
5
,
0 2
1 2
2
Значение P должно быть больше 0,01.
Частотный тест в последовательностях (frequency test within a block) необходим для проверки равномерности появления
0 и
1 в подпоследовательности.
Исследуемая двоичная последовательность разбивается на
M
n
N
M -битных последовательностей. Лишние биты отбрасываются. Определяется доля 1 в каждой подпоследовательности
M
M
j
j
M
i
i
1 1
. Вычисляется статистика
M
i
i
M
s
1 2
5
,
0 4
и значение
2
,
2
s
N
igamc
P
, где:
)
,
(
1
,
x
a
p
x
a
igamc
,
a
a
x
a
p
x
)
,
(
,
0 1
dt
e
t
a
t
a
- гамма-функция,
x
t
a
x
dt
e
t
a
0 1
- неполная гамма-функция.
Значение P должно быть больше 0,01.
Тест «дырок» (runs test) служит для проверки равномерности распределения 0 и 1 в исследуемой последовательности на основе анализа количества появлений «блоков» - подпоследовательностей, состоящих из одних
1 или одних 0 («дырок»). Определяется предтестовая статистика – доля 1 в исследуемой последовательности
n
n
i
i
1
. Если
n
2 5
,
0
- тест считается не пройденным, в противном случае вычисляем статистику
(количество блоков и «дырок»)
1 1
1
)
(
n
k
n
k
r
, где:
1 1
,
1
,
,
0
)
(
i
i
i
i
k
r
. Затем вычисляется
1 2
2 1
2
n
n
erfc
P
n
Значение P должно быть больше 0,01.
Проверка рангов матриц (binary matrix rank test) служит для проверки равномерности распределения 0 и 1 в исследуемой последовательности на основе анализа количества появлений матриц различных рангов. Исследуемая двоичная последовательность длины
n разбивается на
MQ
n
N
непересекающихся подпоследовательностей. Лишние биты отбрасываются.

26
Каждая подпоследовательность представляется как бинарная матрица размером
Q
M
Определяется ранг каждой матрицы. Пусть
M
F
- число матриц ранга M ,
1
M
F
- число матриц ранга
1
M
,
1
M
M
F
F
N
- число оставшихся матриц.
Вычисляется статистика
N
N
F
F
N
N
N
F
N
N
F
s
M
M
M
M
1336
,
0 1336
,
0 5776
,
0 5776
,
0 2888
,
0 2888
,
0 2
1 2
1 2
, а затем значение
2
,
1
s
igamc
P
Значение P должно быть больше 0,01.
Спектральный тест (spectral test) служит для проверки равномерности 0 и 1 в исследуемой последовательности на основе анализа высоты выбросов преобразования Фурье.
Исследуемая двоичная последовательность
i
,
n
i
,
1
преобразовывается в последовательность
i
x
по правилу
1 2
i
i
x
. К полученной последовательности применяется дискретное преобразование
Фурье
x
DFT
S
, из которого формируется подпоследовательность
S
, содержащая первые
2
n
членов S . Члены последовательности S являются комплексными числами. Определяются модули
i
i
S
m
каждого из элементов последовательности
S
. Последовательность
i
m
дает последовательность выбросов высот преобразования Фурье.
Вычисляются
n
T
3 ,
2 95
,
0 0
n
N
и определяется статистика
2 05
,
0 95
,
0 0
1
n
N
N
s
, где
1
N
- число элементов
i
m
, меньших чем T .
Вычисляется значение
2
s
erfc
P
. Значение P должно быть больше
0,01.