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

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ВОЗДУШНОГО ТРАНСПОРТА
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ГРАЖДАНСКОЙ АВИАЦИИ»
Кафедра основ радиотехники и защиты информации
Э. А. Болелов
ПОСОБИЕ
к выполнению лабораторных работ по дисциплине
«КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ»
для студентов 4 курса
специальности 090106
дневной формы обучения
Москва – 2010

2
Данное учебно-методическое пособие издается в соответствии с рабочей программой учебной дисциплины «Криптографические методы защиты информации» по Учебному плану специальности 090106 для студентов дневного обучения.
Учебно-методическое пособие способствует реализации квалификационных требований к студентам по обеспечению знаний в области криптографических методов защиты информации.
В учебно-методическом пособии приведены организационно- методические указания по выполнению лабораторных работ, задания на выполнение лабораторных работ, требования к отчету, а также основные теоретические сведения по каждой работе.
Рассмотрено и одобрено на заседаниях кафедры 15 апреля 2010 г. и методического совета 15 апреля 2010 г.

3
Содержание
Лабораторная работа 1. Изучение частотного метода криптоанализа симметричных криптосистем
4
Лабораторная работа 2. Изучение методов криптоанализа криптосистем гаммирования с периодической гаммой
6
Лабораторная работа 3. Изучение метода линейного криптоанализа блочных симметричных криптосистем
12
Лабораторная работа 4. Изучение метода дифференциального
(разностного) криптоанализа блочных симметричных криптосистем
19
Лабораторная работа 5. Методы оценки качества криптографических генераторов
21
Лабораторная работа 6. Изучение криптосистем с открытым ключом
27
Лабораторная работа 7. Изучение алгоритмов электронной цифровой подписи
29
Приложение А Таблица частот встречаемости букв русского алфавита
32

4
Лабораторная работа №1
Изучение частотного метода криптоанализа
симметричных криптосистем
Цель работы – закрепление теоретических знаний по методам криптоанализа симметричных криптосистем и практическое изучение частотного метода криптоанализа на примере криптосистемы Цезаря.
Время - 4 часа.
1 Основные теоретические сведения
Криптосистема Цезаря определяется выражением:
m
k
x
y
i
i
mod
)
(
,
n
i
,
1 , где
i
y
- буква криптограммы,
i
x
- буква открытого сообщения,
k - ключ шифра, n - длина криптограммы (открытого текста),
m
- мощность алфавита.
Выражения для расшифрования имеет вид:
m
k
y
x
i
i
mod
)
(
Метод частотного криптоанализа базируется на реализации методов теории статистических решений, а именно, на методе максимального правдоподобия [4]. В соответствии с этим методом оценкой ключа шифра
*
k является такое его значение, которое доставляет максимальное значение логарифму функции правдоподобия
)
(k
l
. Для криптосистемы Цезаря оценка формируется в соответствии с выражением:
)
(
max arg
*
k
l
k
k
,
1 0
1
mod
)
(
)
(
log
)
(
m
j
m
k
j
j
p
k
l
,
(1) где
)
(
1
j
p
- оценка вероятности встречаемости
j
-й буквы алфавита мощности m в открытых текстах,
j
- частость встречаемости
j
-й буквы в криптограмме.
Выражение (1) справедливо, если источник открытых сообщений представляет собой стационарный источник дискретных сообщений без памяти. В случае, когда источник открытых сообщений представляет собой однородную цепь Маркова, оценка ключа будет определяться в соответствии с выражением:
1 0
1 0
,
mod
)
(
,
mod
)
(
1
mod
)
(
,
log
)
(
)
(
log max arg
1
m
j
m
s
j
js
m
k
s
m
k
j
m
k
j
у
k
p
Y
j
p
k
2 Порядок выполнения работы
2.1 При подготовке к лабораторной работе
На этапе подготовки к лабораторной работе студенты должны, используя литературу [1,2,3,4] и материалы лекций углубить свои знания по

5 криптосистеме Цезаря и частотному методу криптоанализа простейших шифров.
Студенты на предстоящее лабораторное занятие готовят русский и английский алфавиты со значениями вероятностей встречаемости букв.
2.2 Во время проведения занятия.
Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к лабораторной работе. Затем преподаватель разбивает группу студентов на несколько подгрупп по два студента в каждой.
Каждая подгруппа получает от преподавателя индивидуальный вариант задания на лабораторную работу, который представляет собой криптограмму, зашифрованную с помощью криптосистемы Цезаря.
Студенты должны:
1. Определить частотные характеристики криптограммы, для чего рассчитать значение частоты встречаемости символов
m
A
j
в криптограмме.
2. Определить вероятностные характеристики алфавита, для чего вычислить значение логарифма вероятности встречаемости символа
)
(
log
1
j
p
для заданного алфавита.
3. Полученные значения свести в таблицу 1.
Таблица 1.
Буква
А
Б
…
Ю
Я
m
A
j
)
(
log
1
j
p
)
(Y
j
4. В соответствии с выражением (1) определить значение логарифма функции правдоподобия
)
(K
l
и построить соответствующую графическую зависимость.
5. Определить в соответствии с выражением (1) оценку ключа
*
k .
6. Дешифровать заданную криптограмму, используя оценку ключа
*
k .
При получении осмысленного текста подготовить отчет и представить его преподавателю.
4 Содержание отчета
Отчет должен включать в себя следующие пункты:
1. Задание на выполнение лабораторной работы (исходную криптограмму).
2. Основные расчетные соотношения.
3. Результаты расчетов, сведенные в табл. 1.

6 4. Графическую зависимость
)
(k
l
и значение оценки ключа
*
k .
5. Полученный дешифрованием открытый текст.
5 Контрольные вопросы
1. Основные понятия криптографии и криптоанализа.
2. Понятие симметричной криптосистемы.
3. Шифры перестановки.
4. Шифры замены.
5. Основные характеристики открытых сообщений.
6. Модели источников открытых сообщений.
7. Частотный метод криптоанализа.
Литература
1. Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации. Учебное пособие для вузов. М.: Горячая линия – Телеком, 2005.
2. Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – 2-е изд. – М.: Горячая линия – Телеком, 2002.
3. Осипян В.О, Осипян К.В. Криптография в задачах и упражнениях. –
М.: Гелиос АРВ, 2004.
4. Харин Ю.С., Беник В.И, Матвеев Г.В., Агиевич С.В. Математические и компьютерные основы криптологии: Учеб. пособие. – Минск: Новое знание,
2003.
Лабораторная работа №2
Изучение методов криптоанализа криптосистем гаммирования с
периодической гаммой
Цель работы – закрепление теоретических знаний по методам криптоанализа симметричных криптосистем и практическое освоение методов криптоанализа криптосистем гаммирования с периодической гаммой на примере криптосистемы Виженера.
Время - 4 часа.
1 Основные расчетные соотношения
Криптосистема Виженера представляет собой шифр гаммирования с использованием периодической гаммы малого периода. В криптосистеме
Виженера ключ
d
k
задается набором из
d
символов. Такие наборы подписываются под открытым текстом
n
x
x
x
,...,
,
2 1
,
m
i
A
x
, до получения периодической ключевой последовательности
n
k
k
k
k
,...,
,

2 1
,
r
sd
n
, где
s
- число полных периодов
d
k
,
d
n
r
mod
Уравнение шифрования для криптосистемы Виженера:

7
m
k
x
у
i
i
i
mod

При дешифровании криптосистемы
Виженера решаются две взаимосвязанные задачи:
- задача определение периода
d
ключевой последовательности
k

;
- задача дешифрования криптограммы Y при известном периоде
d
длине ключевой последовательности
k

Основным инструментом решения задачи определения периода ключевой последовательности криптосистемы Виженера являются методы Фридмана, основанные на понятии индекса совпадения. Индексом совпадения последовательности
п
х
х
х
Х
,...,
,
2 1
называется величина
m
i
i
i
n
n
F
F
Х
1
)
1
(
)
1
(
)
(
,
(1) где
m
A
Х
- некоторая последовательность;
i
F
- частота встречаемости
(число мест в тексте)
i
- буквы в последовательности
Х .
Для криптосистемы Виженера, получаемого шифрованием открытого текста
n
a
a
a
X
,...,
,
2 1
с помощью равновероятного выбора ключа
k

из множества всех локально-периодических последовательностей
d
n
K
периода d и
r
sd
n
справедливо
1
)
1
(
)
)(
1
(
)
1
(
1
)
1
(
)
)(
1
(
)
1
(
)
(
2
m
n
n
r
d
s
s
sr
s
p
n
n
r
d
s
s
sr
s
Y
M
i
i
(2)
Первый метод Фридмана состоит в том, что вычисляется индекс совпадения
)
(Y
для имеющейся криптограммы в соответствии с выражением
(1) и затем его значение сравнивается с (2) при
,...
3
,
2
,
1
d
. При достаточной близости индекса совпадения к одному из значений (2), при некотором
d
, предполагают, что период равен этому значению
d
. Первый метод Фридмана эффективен для
5
d
, т.к. значение
)
(Y
M
для фиксированного периода d совпадает со значениями целого ряда различных периодов ключевой последовательности.
Суть второго метода Фридмана состоит в опробовании возможных периодов
d
по следующей схеме. Из исходной криптограммы
n
y
y
y
Y
,...,
,
2 1
для предполагаемого периода
d
ключевой последовательности выписывается
d
подпоследовательностей:
,...
,
,
)
,...
,
,
)
2
,...
,
,
)
1 2
2 2
2 2
2 1
1 1
d
d
d
d
d
d
d
d
d
y
y
y
d
y
y
y
y
y
y

8
Для каждой подпоследовательности подсчитывается ее индекс совпадения
)
(
d
Y
. Если все индексы совпадения в среднем близки к значению
i
i
p
d
2 1
(среднее значение индекса совпадения случайных криптограмм, полученных с помощью гамм периода 1), то принимают величину
d
за истинный период, в противном случае опробуется следующая величина периода. Второй метод Фридмана позволяет эффективно определять периоды
30
d
Метод «протяжки» вероятного слова. При известном периоде ключевой последовательности
d
выписываются две подпоследовательности исходной криптограммы:
,
,...,
,...,
,
;
,...
,...,
,
2 1
)
1
(
2 1
r
kd
n
y
y
y
y
y
y
y
y
r
kd
d
i
d
d
r
d
k
i
Формируется называемое «множество вероятных слов», которые, по мнению криптоаналитика, могут быть началом искомого открытого текста.
Для слова
r
a
a
a
,...,
,
2 1
из этого множества, находятся первые символы ключевой последовательности
r
k
k
k
,...,
,
2 1
. Правильность угадывания вероятного слова, а, следовательно, и первых символов ключевой последовательности, проверяется на «читаемость» следующего фрагмента расшифрованного текста
)
(
),...,
(
),
(
1 2
1 1
1 2
1
d
r
k
d
k
d
k
y
f
y
f
y
f
r
Если полученная последовательность символов «читаемая», то полагают, что
r
r
k
k
k
k
k
k
,...,
,
,...,
,
2 1
2 1
, т.е. найдены первые r символов ключевой последовательности.
Далее анализируя фрагменты расшифрованной криптограммы, ищут возможные продолжения открытого текста, таким образом, чтобы получить недостающую часть ключевой последовательности
d
r
r
d
r
r
k
k
k
k
k
k
,...,
,
,...,
,
2 1
2 1
После того, как определен весь ключ, оставшаяся часть криптограммы расшифровывается на найденном ключе. Если же последовательность символов принимается как случайная (т.е. «нечитаемая»), то опробуется следующее вероятное слово. Вероятные слова могут выбираться также из предположения, что они является окончанием открытого текста или, в общем случае, располагаются на других позициях открытого текста.
Метод чтения в колонках. Рассмотрим два случая:
- априорные вероятности символов ключевой последовательности не известны;
- априорные вероятности символов ключевой последовательности известны.

9
Априорные вероятности символов ключевой последовательности не
известны. Пусть дана криптограмма
n
y
y
y
Y
,...,
,
2 1
. Известен период ключевой последовательности
d
. Сформируем две подпоследовательности исходной криптограммы
,
,...,
,...,
,
;
,...
,...,
,
2 1
)
1
(
2 1
r
kd
n
y
y
y
y
y
y
y
y
r
kd
d
i
d
d
r
d
k
i
Будем полагать, что открытыми текстами, подлежащими шифрованию, являются содержательные тексты с известными вероятностями букв алфавита
j
j
p
a
P
)
(
,
m
j
,
1
, где
j
- порядкоый номер буквы алфавита. Также будем считать, что на множестве K задано равномерное распределение, т.е. ключом является реализация выборки объемом d из равномерного распределения
K
Тогда вероятность того, что
i
-я и (
d
i
)-я буквы открытого текста были равны соответственно,
s
x
i
и
l
x
d
i
, при условии, что
i
-я и (
d
i
)-я буквы криптограммы равны соответственно,
i
y
и
d
i
y
определяется выражением
)
,
(
)
,
;
,
(
)
,
|
,
(
d
i
i
d
i
i
d
i
i
d
i
i
d
i
i
y
y
P
y
y
l
x
s
x
P
y
y
l
x
s
x
P
Если числитель не равен нулю, то справедливо равенство
sl
K
f
y
f
y
f
l
s
d
i
i
d
i
i
p
p
p
p
p
y
y
l
x
s
x
P
d
i
i

)
,
|
,
(
)
(
)
(
1 1
Для каждой пары
i
y
и
d
i
y
букв исходной криптограммы упорядочим в соответствии с убыванием полученных значения условных вероятностей (5) пары букв открытого текста
s
и
l
. Построив такие колонки для каждого
i
, в результате получаем таблицу (табл. 1), в которой верхние пары имеют большую условную вероятность, чем нижние.
Таблица 1.
1
i
…
j
i
…
n
i
d
y
y
1 1
…
d
j
j
y
y
…
r
k d
r
d
k
y
y
)
1
(
….
…
sl
d
j
j
p
l
x
s
x

,
…
…
Буквы искомого содержательного текста будут находится вероятнее всего в первых строках и задача сводится к подбору таких пар букв, чтобы в результате получался осмысленный текст.
Априорные вероятности символов ключевой последовательности
известны. Если априорно известны вероятности символов ключевой

10 последовательности, то задача дешифрования криптограммы аналогична задаче восстановления текста, зашифрованного неравновероятной гаммой. Пусть
i
р
,
m
i
,
1
, есть вероятность использования символа в ключевой последовательности. Рассмотрим простую задачу, когда некоторые символы вовсе не встречаются в ключевой последовательности. Положим, что
l
р
р
р
2 1
,
0 2
1
m
l
l
p
p
p
,
m
l
Составим таблицу (см. таблицу 2), в которой по строкам расположены символы, полученные путем расшифровки криптограммы одним символом ключевой последовательности
i
k
,
l
i
,
1
. Задача заключается в подборе по столбцам символов таким образом, чтобы в результате получился осмысленный текст. Если нельзя исключить использования ни одного символа в ключевой последовательности, то тогда поступают следующим образом. Для составления таблицы исключают из рассмотрения
l
m
наименее вероятных букв алфавита, дальнейшие действия аналогичны рассмотренным выше. Надежность такого метода меньше, так как не исключена возможность частичной, а может и полной, потери истинного открытого текста.
Таблица 2.
i
i
y
k
1
y
….
….
n
y
1
k
)
(
ˆ
1 1
k
y
….
…..
)
(
ˆ
1
k
y
n
2
k
)
(
ˆ
2 1
k
y
….
….
)
(
ˆ
2
k
y
n
….
….
….
….
….
l
k
)
(
ˆ
1
l
k
y
….
….
)
(
ˆ
l
n
k
y