2 Цели и задачи Цель проекта : изучение системы шифрования с открытым ключом RSA. Задачи проекта: Ознакомиться с основными понятиями криптографии. Изучение основных принципов симметрических криптосистем. Изучение основных принципов асимметрических криптосистем. Ознакомиться с методами теории чисел, используемых в RSA. Изучение алгоритма RSA. Продемонстрировать на примерах шифрование и дешифрование различных сообщений по алгоритму RSA 2

3 Основные понятия Криптология (kryptos - тайный, logos - наука) - наука, изучающая математические методы защиты информации путем ее преобразования. Криптография - занимается поиском и исследованием математических методов преобразования информации. Криптоанализ - занимается исследованием возможности расшифровывания информации без знания ключей. Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом (называемый также криптограммой). Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный. 3

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

5 Алгоритм создания открытого и секретного ключей RSA 1.Выберем два простых числа p и q. 2.Вычисляется их произведение m= pq, которое называется модулем. 3.Вычисляется значение функции Эйлера от числа m: (m)=(p-1)(q-1) 4.Выбирается целое число e (1

6 5.Найдем линейное представление НОД(e, (m)) при помощи расширенного алгоритма Евклида. 1=5-4*1=5-(64-5*12)= =5*13-64*1 1=5-4*1=5-(64-5*12)= =5*13-64*1 dc13(-1) НОД (5, 64) =1=d*5+c*64 = 13*5+(-1)*64 d = 13 (d,m)=(13,85) Пара (d,m)=(13,85) – секретный ключ RSA. Алгоритм RSA: пример. 6 p=17q=5 1.Выбираются два простых числа p=17 и q=5. m= pq=17*5=85 2.Вычислим их произведение m= pq=17*5=85. 3.Вычислим значение функции Эйлера: (85)=(p-1)(q-1)=16*4=64 (85)=(p-1)(q-1)=16*4=64 e=5 (m)=64 4.Выбирается целое число e=5, взаимно простое с (m)=64. (e,m)=(5,85) Пара (e,m)=(5,85) - открытый ключ RSA. Алгоритм RSA: пример. Алгоритм шифрования 1.Возьмем открытый ключ (e,m)=(5,85). 2.Возьмем открытый текст a=7. 3.Получить криптограмму b: b=a e mod m=7 5 mod 85=16807 mod 85=62 4.Передать шифрованное сообщение b=62. Алгоритм шифрования 1.Возьмем открытый ключ (e,m)=(5,85). 2.Возьмем открытый текст a=7. 3.Получить криптограмму b: b=a e mod m=7 5 mod 85=16807 mod 85=62 4.Передать шифрованное сообщение b=62. Алгоритм дешифрования 1.Принять зашифрованное сообщение b=62. 2.Применить свой секретный ключ (d,m)=(13,85) для расшифровки сообщения: a=b d mod m=62 13 mod 85= mod 85=7

7 Криптоанализ RSA Ловушка в системе RSA заключается в том, что умножение чисел p и q для получения числа m простая операция, тогда как обратная задача разложение числа m на множители для получения p и q практически неразрешима. Почему же систему RSA трудно взломать? 7

8 Изучены основные виды симметрических криптосистем: шифры замены и шифры перестановки. Изучены основные принципы асимметрических криптосистем. Изучены понятия и методы теории чисел, используемых в RSA: алгоритм Евклида нахождения НОД, расширенный алгоритм Евклида, функция Эйлера и ее свойства. Изучен алгоритма RSA. Разобрано 5 примеров шифрования и дешифрования различных высказываний великих математиков по алгоритму RSA Основные результаты работы 8