пз4(т7)-. Мамлеев Радик Римлянович Москва 2022 Практическое занятие
![]()
|
![]() ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ КАЗЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ УНИВЕРСИТЕТ МВД РОССИИ ИМЕНИ В.Я. КИКОТЯ» кафедра специальных информационных технологий учебно-научного комплекса информационных технологий УТВЕРЖДАЮ Начальник кафедры подполковник полиции Е.С. Поликарпов «___» сентября 2022 г. Дисциплина: Криптографическая защита информации 10.05.05 Безопасность информационных технологий в правоохранительной сфере, специализация «Технологии защиты информации в правоохранительной сфере» Методическая разработка практического занятия Тема 7. «Системы шифрования с открытыми ключами»
Москва 2022 Практическое занятие Объем времени, отводимого для изучения данной темы: 4 часа. Место проведения: учебная аудитория. Методы проведения: персональное выполнение заданий. Материально-техническое обеспечение занятия: учебная аудитория, с ПЭВМ подключенным к сети Интернет и установленным программным обеспечением: Операционная система MicrosoftWindows; Набор офисных программ MicrosoftWord, Excel; Основные термины и понятия: криптология, криптография, криптоанализ. Цели занятия: Закрепить знания по проведенной лекции и прошедшего лекционного занятия. Кратко проконтролировать уровень усвоения полученных знаний слушателями в ходе самостоятельной работы. Рассмотреть особенности систем шкриптографической защиты информации. Сформировать у слушателей такие профессиональные качества, как бдительность, самодисциплина, самообразование, сообразительность (не доводится!). План занятия: Основная теорема арифметики Взаимно простые числа Функция Эйлера Теорема Эйлера Алгоритм Евклида Алгоритм открытого ключа Шифрование с открытым ключом Алгоритм RSA Проверка результатов Заключение Распределение учебного времени
Цель: развитие интереса слушателей к изучению основ криптографии с целью ее применения для защиты информации. Обучающие задачи: - ознакомить слушателей с понятиями защита информации, криптография, шифрование, дешифрование и др.; - научиться кодировать и декодировать информацию; - объяснить практическую значимость темы. Развивающие задачи: - развить алгоритмическое мышление слушателей; - уметь применять знания в жизни; - развить навыки работы с инструкционной картой. Тема 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. Далее пользователь А вычисляет открытый ключ Ya= (cXa)mod n, а пользователь В – открытый ключ Yb = (cXb) mod n. 4. Затем стороны обмениваются вычисленными значениями открытых ключей Ya и Yb по любому, даже совсем незащищенному каналу, т.к. открытые ключи не являются секретом. (считаем, что все данные, передаваемые по незащищенному каналу связи, могут быть перехвачены злоумышленником). 5. Далее пользователи А и В вычисляют общий секретный ключ, используя следующие соотношения: пользователь А: Kab= (YbXa)mod n = (cXbXa)mod n, пользователь В: Kba= (YaXb)mod n = (cXaXb)mod n. Очевидно, что Kab= Kba. Ключ К может использоваться в качестве общего секретного ключа (ключа шифрования), например, в таких симметричных криптосистемах, как DES, ГОСТ 28147-89, AES и др. Возможные действия злоумышленника.Перехватив значения n, c, Ya и Yb, криптоаналитик тоже хотел бы определить значения ключа К. Очевидный путь для решения этой задачи состоит в вычислении такого значения Хa по n, c и Ya, что (cXa)mod n = Ya (поскольку в этом случае, вычислив Xa, можно найти K = (YbXa)mod n). Однако нахождение Xa по n, c и Ya – это задача нахождения дискретного логарифма в конечном поле, которая считается неразрешимой. Выбор значений n и c может иметь существенное влияние на безопасность этой системы. Модуль n должен быть большим и простым числом. Число (n-1)/2 также должно быть простым числом. Число с желательно выбирать таким, чтобы оно было примитивным элементом множества ненулевых элементов Zn, т.е. {c,c2,….cn-1} = Zn – {0}. В принципе достаточно, чтобы с генерировало большую подгруппу мультипликативной группы по mod n. Алгоритм открытого распределения ключей Диффи-Хеллмана позволяет обойтись без защищенного канала для передачи ключей. Однако, работая с этим алгоритмом, необходимо иметь гарантию того, что пользователь А получил открытый ключ именно от пользователя В, и наоборот. Эта проблема решается с помощью электронной подписи, которой подписываются сообщения об открытом ключе. Метод Диффи-Хеллмана дает возможность шифровать данные при каждом сеансе связи на новых ключах. Это позволяет не хранить секреты на дискетах или других носителях. Не следует забывать, что любое хранение секретов повышает вероятность попадания их в руки конкурентов или противника. Преимущество метода Диффи-Хеллмана по сравнению с методом RSA заключается в том, что формирование общего секретного ключа происходит в сотни раз быстрее. В системе RSA генерация новых секретных и открытых ключей основана на генерации новых простых чисел, что занимает много времени. Кроме того, сам процесс зашифровывания и расшифровывания информации в симметричных (одноключевых) системах протекает значительно быстрее, чем в асимметричных (двухключевых), а система Диффи-Хеллмана как раз и ориентирована на то, что сам процесс информационного обмена будет производиться в симметричных системах. Однонаправленные функции это функции, для которых обратное преобразование существует и однозначно, но вычислительно нереализуемо. Они называются вычислительно необратимыми функциями. В качестве примера однонаправленной функции y= (x) рассмотрим функцию дискретного возведения в степень: yx, где x – целое число от 1 до p–1 включительно, а вычисление производится по модулю p, где p – очень большое простое число; a – целое число (11(mod7)=3, a2(mod7)=32(mod7)=2, a3(mod7)=33(mod7)=6, a4(mod7)=4, a5(mod7)=5, a6(mod7)= Функция вычисляется сравнительно просто, а обратная к ней функция является вычислительно сложной практически для всех (1 Задача дискретного логарифмирования состоит в том, что для известных целых x, p, y необходимо найти целое число x. Однако алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. Поэтому модульная экспонента считается однонаправленной функцией. К настоящему времени предложено большое количество однонаправленных функций с потайным ходом, построенных на основе известных вычислительно сложных математических задач. Наиболее часто для построения однонаправленных функций с потайным ходом используется сложность решения следующих теоретико-числовых задач: – разложение больших чисел на простые множители (криптосистема шифрования и криптосистема цифровой подписи сообщений RSA, криптосистема цифровой подписи сообщений Рабина и другие криптосистемы); – отыскание дискретного логарифма элемента в большом конечном поле или группе (криптосистема открытого распространения ключей Диффи-Хэллмана, криптосистема шифрования и криптосистема цифровой подписи сообщений Эль-Гамаля, криптосистема цифровой подписи сообщений Шнорра и другие криптосистемы); – задача об укладке целочисленного ранца; – декодирование неизвестных получателю кодов Гоппы. 2. Модулярная арифметикаМногие криптографические алгоритмы базируются на результатах классической теории чисел. Мы рассмотрим необходимый минимум из этой теории. Классические теоремы Ферма, Эйлера и ряд других результатов из теории чисел будут даны без доказательств, которые могут быть найдены практически в любом учебнике по теории чисел. Определение 1. Целое положительное число p называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицы. Основная теорема арифметики. Любое целое положительное число может быть представлено в виде произведения простых чисел, причем единственным образом. Таблица простых чисел
Пример 27 = 3 • 3 • 3, 33 = 3 • 11. Задание 1 Основная теорема арифметики.Найти произведения простых чисел для чисел
Определение 2 Два числа называются взаимно простыми, если они не имеют ни одного общего делителя кроме единицы. Пример Числа 27 и 28 взаимно просты (у них нет общих делителей кроме единицы), числа 27 и 33 – нет (у них есть общий делитель 3). Задание 2 Взаимно простые числа.Найти пару взаимно простых чисел
Функция Эйлера. Пусть дано целое число N 1. Значение функции Эйлера (N) равно количеству чисел в ряду 1, 2, 3, . . . , N - 1, взаимно простых с N . Пример (10)=? 1, (10) =3 (12)=? 1, (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 и
Теорема Эйлера. Пусть a и b – взаимно простые числа. Тогда a(b) mod b =1. Задание 4 Теорема ЭйлераДоказать теорему Эйлера для
Алгоритм Евклида Дано: Положительные целые числа a, b, a > b. Найти: Наибольший общий делитель НОД(a, b) . Если b 0 то r ← a mod b, a← b, b ← r. Возврат: a. Покажем, как с помощью алгоритма Евклида вычисляется НОД(28, 8):
Здесь каждый столбец представляет собой очередную итерацию алгоритма. Процесс продолжается до тех пор, пока b не станет равным нулю. Тогда в значении переменной a содержится ответ (4). Задание 5 Алгоритм ЕвклидаС помощью алгоритма Евклида вычислить НОД(a, b)
3.Алгоритмы открытого ключаШаг первый. Подготовка сообщения
1. Выбор сообщения
+10
Группировка
Шифрование. S=M*1000 mod 4999. Открытый ключ (1000; 4999)
2. Расшифровка. М=S*5 mod 4999. Закрытый ключ (5; 4999)
Разгруппировка
-10
Задание 6 Алгоритм открытого ключаЗашифруйте фразу
Шифрование. S=M*1000 mod 4999. Открытый ключ (1000; 4999)
Дешифрование. М=S*5 mod 4999. Закрытый ключ (5; 4999)
Задание 7 ШифрованиеЗашифруйте любое слово из восьми букв
Открытый ключ (1000; 4999) S=M*1000 mod 4999
Расшифруйте слово от партнера. Закрытый ключ (5; 4999) М=S*5 mod 4999
Алгоритм RSAШаг первый. Подготовка ключей1. Проделать предварительные действия: сгенерировать публичный и приватный ключ.
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: 1017=1700000000000000000 Вычисляем остаток от деления на n (=21) P = Edmod n =1700000000000000000 mod 21=19 Никто, кроме автора не может расшифровать сообщение (E=10), так как ни у кого кроме него нет закрытого ключа. Задание 8 Алгоритм RSAВыбирать два простых Вычислить модуль n=p×q. Вычислить открытый ключ {e, n}. Вычислить закрытый ключ { d, n }. Зашифруйте слова( p=3 и q=11).
Отчет о практической работе № 4Курсанта ______ взвода. Фамилия ___________________ Имя _________________ Отчество _________________
Проверил: _______________________________________ дата _____________ |