пз4(т7)-. Мамлеев Радик Римлянович Москва 2022 Практическое занятие

• Название: Мамлеев Радик Римлянович Москва 2022 Практическое занятие
• Дата: 09.11.2022
• Размер: 1.06 Mb.
• Имя файла: пз4(т7)-.doc
• Тип: Занятие; #778185

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ КАЗЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«МОСКОВСКИЙ УНИВЕРСИТЕТ МВД РОССИИ ИМЕНИ В.Я. КИКОТЯ»
кафедра специальных информационных технологий

учебно-научного комплекса
информационных технологий
УТВЕРЖДАЮ

Начальник кафедры

подполковник полиции

Е.С. Поликарпов

«___» сентября 2022 г.

Дисциплина:

Криптографическая защита информации

10.05.05 Безопасность информационных технологий в правоохранительной сфере, специализация «Технологии защиты информации в правоохранительной сфере»

Методическая разработка практического занятия

Тема 7. «Системы шифрования с открытыми ключами»

Обсуждена и одобрена на заседании кафедры протокол № 1 от « 2 » сентября 2022г

Подготовил: старший преподаватель кафедры СИТ УНК ИТ Мамлеев Радик Римлянович

Москва 2022

Практическое занятие

Объем времени, отводимого для изучения данной темы: 4 часа.

Место проведения: учебная аудитория.

Методы проведения: персональное выполнение заданий.

Материально-техническое обеспечение занятия: учебная аудитория, с ПЭВМ подключенным к сети Интернет и установленным программным обеспечением:

1. 
   Операционная система MicrosoftWindows;
   
2. 
   Набор офисных программ MicrosoftWord, Excel;
   

Основные термины и понятия: криптология, криптография, криптоанализ.
Цели занятия:

1. 
   Закрепить знания по проведенной лекции и прошедшего лекционного занятия. Кратко проконтролировать уровень усвоения полученных знаний слушателями в ходе самостоятельной работы.
   
2. 
   Рассмотреть особенности систем шкриптографической защиты информации.
   
3. 
   Сформировать у слушателей такие профессиональные качества, как бдительность, самодисциплина, самообразование, сообразительность (не доводится!).
   

План занятия:

1. 
   Основная теорема арифметики
   
2. 
   Взаимно простые числа
   
3. 
   Функция Эйлера
   
4. 
   Теорема Эйлера
   
5. 
   Алгоритм Евклида
   
6. 
   Алгоритм открытого ключа
   
7. 
   Шифрование с открытым ключом
   
8. 
   Алгоритм RSA
   
9. 
   Проверка результатов
   
10. 
    Заключение
    

Распределение учебного времени

1.	Введение	5 мин.
2.	Основная часть	160 мин.
3	Проверка результатов	10 мин.
4.	Заключение	5 мин.

Цель: развитие интереса слушателей к изучению основ криптографии с целью ее применения для защиты информации.

Обучающие задачи:

- ознакомить слушателей с понятиями защита информации, криптография, шифрование, дешифрование и др.;

- научиться кодировать и декодировать информацию;

- объяснить практическую значимость темы.

Развивающие задачи:

- развить алгоритмическое мышление слушателей;

- уметь применять знания в жизни;

- развить навыки работы с инструкционной картой.

Тема 7. Системы шифрования с открытыми ключами

План занятия

УТВЕРЖДАЮ 1

Тема 7. Системы шифрования с открытыми ключами 4

1. Краткие теоретические сведения и задания 4

2. Модулярная арифметика 7

Задание 1 Основная теорема арифметики. 7

Задание 2 Взаимно простые числа. 7

Задание 3 Функция Эйлера 8

Задание 4 Теорема Эйлера 8

Задание 5 Алгоритм Евклида 8

3.Алгоритмы открытого ключа 8

Задание 6 Алгоритм открытого ключа 9

Задание 7 Шифрование 9

Алгоритм RSA 9

Задание 8 Алгоритм RSA 11

Отчет о практической работе № 4 12

1. Краткие теоретические сведения и задания

Однонаправленные функции

Для реализации любой одноключевой криптосистемы необходим обмен секретными ключами шифрования. Передача таких ключей по открытым каналам не имеет смысла, так как может стать легкой добычей злоумышленника. Передавать ключи по закрытым каналам тоже опасно, так как в этом случае однократная компрометация канала рассекречивает весь дальнейший обмен. Поэтому единственным надежным средством доставки ключевой информации для особо важного обмена до недавнего времени считалась фельдъегерская почта. В современных условиях, например, для миллионов пользователей Internet такая система неприемлема.

Особую роль в криптографии играют однонаправленные функции, которые в общем случае не являются биективными.

В основе криптографии с открытым ключем лежит свойство односторонней функции y=f(x), в которой, зная х сравнительно легко вычислить y, но вычисление х при известном у выливается в задачу, сопоставимую с полным перебором.

В 1976 году Диффи и Хеллман опубликовали алгоритм открытого распределения ключей, который позволяет двум абонентам путем обмена открытыми сообщениями сформировать одинаковые секретные ключи для своей одноключевой (симметричной) системы шифрования.

В основе метода лежит свойство односторонней функции y=f(x), в которой, зная х сравнительно легко вычислить y, но вычисление х при известном у выливается в задачу, сопоставимую с полным перебором.

Суть алгоритма Диффи-Хеллмана состоит в следующем.

Предположим, что два пользователя А и В хотят организовать защищенный коммуникационный канал.

1. Обе стороны заранее уславливаются о модуле n (n должно быть простым числом) и примитивном элементе с (1<c < n). Эти два целых числа n и с могут не храниться в секрете. Как правило, эти значения являются общими для всех пользователей системы.

2. Затем пользователи А и В независимо друг от друга выбирают собственные секретные ключи Х_a и Х_b (Х_a и Х_b – случайные большие целые числа, которые хранятся пользователями А и В в секрете).

3. Далее пользователь А вычисляет открытый ключ Y_a= (c^Xa)mod n, а пользователь В – открытый ключ Y_b = (c^Xb) mod n.

4. Затем стороны обмениваются вычисленными значениями открытых ключей Y_a и Y_b по любому, даже совсем незащищенному каналу, т.к. открытые ключи не являются секретом. (считаем, что все данные, передаваемые по незащищенному каналу связи, могут быть перехвачены злоумышленником).

5. Далее пользователи А и В вычисляют общий секретный ключ, используя следующие соотношения:

пользователь А: K_ab= (Y_b^Xa)mod n = (c^XbXa)mod n,

пользователь В: K_ba= (Y_a^Xb)mod n = (c^XaXb)mod n.

Очевидно, что K_ab= K_ba.

Ключ К может использоваться в качестве общего секретного ключа (ключа шифрования), например, в таких симметричных криптосистемах, как DES, ГОСТ 28147-89, AES и др.

Возможные действия злоумышленника.

Перехватив значения n, c, Y_a и Y_b, криптоаналитик тоже хотел бы определить значения ключа К. Очевидный путь для решения этой задачи состоит в вычислении такого значения Х_a по n, c и Y_a, что (c^Xa)mod n = Y_a (поскольку в этом случае, вычислив X_a, можно найти K = (Y_b^Xa)mod n). Однако нахождение X_a по n, c и Y_a – это задача нахождения дискретного логарифма в конечном поле, которая считается неразрешимой.

Выбор значений n и c может иметь существенное влияние на безопасность этой системы. Модуль n должен быть большим и простым числом. Число (n-1)/2 также должно быть простым числом. Число с желательно выбирать таким, чтобы оно было примитивным элементом множества ненулевых элементов Zn, т.е. {c,c²,….c^n-1} = Zn – {0}.

В принципе достаточно, чтобы с генерировало большую подгруппу мультипликативной группы по mod n.

Алгоритм открытого распределения ключей Диффи-Хеллмана позволяет обойтись без защищенного канала для передачи ключей. Однако, работая с этим алгоритмом, необходимо иметь гарантию того, что пользователь А получил открытый ключ именно от пользователя В, и наоборот. Эта проблема решается с помощью электронной подписи, которой подписываются сообщения об открытом ключе.

Метод Диффи-Хеллмана дает возможность шифровать данные при каждом сеансе связи на новых ключах. Это позволяет не хранить секреты на дискетах или других носителях. Не следует забывать, что любое хранение секретов повышает вероятность попадания их в руки конкурентов или противника.

Преимущество метода Диффи-Хеллмана по сравнению с методом RSA заключается в том, что формирование общего секретного ключа происходит в сотни раз быстрее. В системе RSA генерация новых секретных и открытых ключей основана на генерации новых простых чисел, что занимает много времени. Кроме того, сам процесс зашифровывания и расшифровывания информации в симметричных (одноключевых) системах протекает значительно быстрее, чем в асимметричных (двухключевых), а система Диффи-Хеллмана как раз и ориентирована на то, что сам процесс информационного обмена будет производиться в симметричных системах.

Однонаправленные функции это функции, для которых обратное преобразование существует и однозначно, но вычислительно нереализуемо. Они называются вычислительно необратимыми функциями.

В качестве примера однонаправленной функции y= (x) рассмотрим функцию дискретного возведения в степень: y^x, где x – целое число от 1 до p–1 включительно, а вычисление производится по модулю p, где p – очень большое простое число; a – целое число (11(mod7)=3, a²(mod7)=3²(mod7)=2, a³(mod7)=33(mod7)=6, a⁴(mod7)=4, a⁵(mod7)=5, a⁶(mod7)=

Функция вычисляется сравнительно просто, а обратная к ней функция является вычислительно сложной практически для всех (1
Задача дискретного логарифмирования состоит в том, что для известных целых x, p, y необходимо найти целое число x. Однако алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. Поэтому модульная экспонента считается однонаправленной функцией.

К настоящему времени предложено большое количество однонаправленных функций с потайным ходом, построенных на основе известных вычислительно сложных математических задач. Наиболее часто для построения однонаправленных функций с потайным ходом используется сложность решения следующих теоретико-числовых задач:

– разложение больших чисел на простые множители (криптосистема шифрования и криптосистема цифровой подписи сообщений RSA, криптосистема цифровой подписи сообщений Рабина и другие криптосистемы);

– отыскание дискретного логарифма элемента в большом конечном поле или группе (криптосистема открытого распространения ключей Диффи-Хэллмана, криптосистема шифрования и криптосистема цифровой подписи сообщений Эль-Гамаля, криптосистема цифровой подписи сообщений Шнорра и другие криптосистемы);

– задача об укладке целочисленного ранца;

– декодирование неизвестных получателю кодов Гоппы.

2. Модулярная арифметика

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

Определение 1. Целое положительное число p называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицы.

Основная теорема арифметики. Любое целое положительное число может быть представлено в виде произведения простых чисел, причем единственным образом.

Таблица простых чисел

1	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67
71	73	79	83	89	97	101	103	107	109	113	127	131	137	139	149	151	157	163	167
173	179	181	191	193	197	199	211	223	227	229	233	239	241	251	257	263	269	271	277

Пример

27 = 3 • 3 • 3, 33 = 3 • 11.

Задание 1 Основная теорема арифметики.

Найти произведения простых чисел для чисел

28	35	47	52	63	78

Определение 2 Два числа называются взаимно простыми, если они не имеют ни одного общего делителя кроме единицы.

Пример

Числа 27 и 28 взаимно просты (у них нет общих делителей кроме единицы), числа 27 и 33 – нет (у них есть общий делитель 3).

Задание 2 Взаимно простые числа.

Найти пару взаимно простых чисел

17	29	31	53	59	67

Функция Эйлера. Пусть дано целое число N  1. Значение функции Эйлера  (N) равно количеству чисел в ряду 1, 2, 3, . . . , N - 1, взаимно простых с N .

Пример

(10)=?

1, 2, 3, 4, 5, 6, 7, 8, 9

(10) =3

(12)=?

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

(12) =4

(здесь зачеркнуты числа, не взаимно простые с аргументом).

Если p и q – два различных простых числа (p ≠ q), тогда

 (pq) = (p – 1)*(q – 1).

В ряду 1, 2, . . . , pq – 1 не взаимно простыми с pq будут числа p, 2p, 3p, …, (q - 1) p и q, 2q, 3q, …, (p - 1) q. Всего таких чисел будет (q – 1) + (p – 1) . Следовательно, количество чисел, взаимно простых с pq , будет

pq – 1 – (p – 1) – (q – 1) =pq – q –p + 1 = (p – 1) (q – 1).

Задание 3 Функция Эйлера

Найти функцию Эйлера для следующих пар p и

p	3	5	7	11	13
q	17	19	23	29	31
 (pq)

Теорема Эйлера. Пусть a и b – взаимно простые числа. Тогда

a^(b) mod b =1.

Задание 4 Теорема Эйлера

Доказать теорему Эйлера для

a	3	5	7	11	13
b	17	19	23	29	31
a(b) mod b

Алгоритм Евклида

Дано: Положительные целые числа a, b, a > b.

Найти: Наибольший общий делитель НОД(a, b) .

Если b  0 то

r ← a mod b, a← b, b ← r.

Возврат: a.

Покажем, как с помощью алгоритма Евклида вычисляется НОД(28, 8):

a:	28	8	4
b:	8	4	0
r:	4	0

Здесь каждый столбец представляет собой очередную итерацию алгоритма. Процесс продолжается до тех пор, пока b не станет равным нулю. Тогда в значении переменной a содержится ответ (4).

Задание 5 Алгоритм Евклида

С помощью алгоритма Евклида вычислить НОД(a, b)

a:	28				34				42
b:	12				7				10
r:

3.Алгоритмы открытого ключа

Шаг первый. Подготовка сообщения

А	Б	В	Г	Д	Е	Ё	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33

1. Выбор сообщения

М	О	С	К	В	А
14	16	19	12	3	1

+10

24

26

29

22

13

11

Группировка

M

2426

2922

1311

Шифрование. S=M*1000 mod 4999. Открытый ключ (1000; 4999)

S

1485

2584

1262

2. Расшифровка. М=S*5 mod 4999. Закрытый ключ (5; 4999)

M

2426

2922

1311

Разгруппировка

24

26

29

22

13

11

-10

14	16	19	12	3	1
М	О	С	К	В	А

Задание 6 Алгоритм открытого ключа

Зашифруйте фразу

П

Е

Р

Е

Х

О

Д

И

Н

А

З

А

П

А

С

Н

У

Ю

В

О

Л

Н

У

.

2716

___10

Шифрование. S=M*1000 mod 4999. Открытый ключ (1000; 4999)

Шифр (S)

Дешифрование. М=S*5 mod 4999. Закрытый ключ (5; 4999)

Текст (М)

Задание 7 Шифрование

Зашифруйте любое слово из восьми букв

Открытый ключ (1000; 4999)

S=M*1000 mod 4999

Шифр (S)

Расшифруйте слово от партнера. Закрытый ключ (5; 4999)

М=S*5 mod 4999

Текст (М)

Алгоритм RSA

Шаг первый. Подготовка ключей

1. Проделать предварительные действия: сгенерировать публичный и приватный ключ.

1

2

3

5

7

11

13

17

19

23

29

31

37

41

43

47

53

59

61

67

2. Выбираем два простых числа. Пусть это будет p=3 и q=7.

3. Вычисляем модуль – произведение наших p и q: n=p×q=3×7=21.

(в общем случае n - должно быть больше мощности алфавита т.е. 33)

Вычисляем функцию Эйлера: φ=(p-1)×(q-1)=2×6=12.

Выбираем число e, отвечающее следующим критериям:

(1) оно должно быть простое,

(2) оно должно быть меньше φ – остаются варианты:

3, 5, 7, 11,

(3) оно должно быть взаимно простое с φ; остаются варианты

5, 7, 11.

Выберем e=5. Это, так называемая, открытая экспонента.

Теперь пара чисел {e, n} – это мой открытый ключ. Я отправляю его вам, чтобы вы зашифровали своё сообщение.

4. Получение закрытого ключа.

Нужно вычислить число d, обратное е по модулю φ.

То есть остаток от деления по модулю φ произведения d×e должен быть равен 1.

Запишем это в принятых обозначениях:

(d×е) mod φ=1. Или (d×5) mod 12=1.

d может быть равно 5 ((5×5)mod12 = 25mod12=1), но чтобы оно не путалось с e в дальнейшем повествовании, давайте возьмём его равным 17.

Проверим, что (17×5)mod12 действительно равно 1 (17×5-12×7=1). Итак d=17. Пара {d, n} – это секретный ключ, оставляем у себя. Его нельзя сообщать никому. Только обладатель секретного ключа может расшифровать то, что было зашифровано открытым ключом.

Шаг второй. Шифрование

Теперь пришла ваша очередь шифровать ваше сообщение. Допустим, ваше сообщение это число 19. Обозначим его P=19. Кроме него у вас уже есть мой открытый ключ: {e, n} = {5, 21}. Шифрование выполняется по следующему алгоритму:

Возводите ваше сообщение в степень e по модулю n.

То есть, вычисляете 19 в степени 5 (2476099) и берёте остаток от деления на 21. Получается 10 – это ваши закодированные данные.

Строго говоря, вам вовсе незачем вычислять огромное число «19 в степени 5». При каждом умножении достаточно вычислять не полное произведение, а только остаток от деления на 21. Но это уже детали реализации вычислений. Полученные данные E=10, вы отправляете мне.

Здесь надо заметить, что сообщение P=19 не должно быть больше n=21. иначе ничего не получится.

Шаг третий. Расшифровка

Имеются данные (E=10),

имеется закрытый ключ {d, n} = {17, 21}.

Обратите внимание на то, что открытый ключ не может расшифровать сообщение. Закрытый ключ кроме автора неизвестен. В этом особенность асимметричного шифрования.

Начинаем раскодировать: операция, очень похожа на шифрование, но вместо e используется d. Возведим E в степень d: 10¹⁷=1700000000000000000

Вычисляем остаток от деления на n (=21)

P = E^dmod n =1700000000000000000 mod 21=19

Никто, кроме автора не может расшифровать сообщение (E=10), так как ни у кого кроме него нет закрытого ключа.

Задание 8 Алгоритм RSA

Выбирать два простых

Вычислить модуль n=p×q. Вычислить открытый ключ {e, n}. Вычислить закрытый ключ { d, n }.

Зашифруйте слова( p=3 и q=11).

КОД			КОТ			КИТ

Отчет о практической работе № 4

Курсанта ______ взвода. Фамилия ___________________ Имя _________________ Отчество _________________

Задание 1
Задание 2.
Задание 3.
Задание 4.
Задание 5.
Задание 6.
Задание 7.
Задание 8

Проверил: _______________________________________ дата _____________