Алгоритм RSA

Размещено на http://www.allbest.ru/

Введение

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

1. История разработки алгоритма RSA

Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом. Разработанный впоследствии алгоритм Диффи -- Хеллмана позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных средств пользователи не могли быть уверены, с кем именно они сгенерировали общий секретный ключ.

Изучив эту статью, трое учёных Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

В августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American, с разрешения Рональда Ривеста появилось первое описание криптосистемы RSA. Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом:

В качестве открытых параметров системы были использованы числа n=1143816...6879541 (129 десятичных знаков, 425 бит, также известно как RSA-129) и e=9007. За расшифровку была обещана награда в 100 долларов США. По заявлению Ривеста, для факторизации числа потребовалось бы более 40 квадриллионов лет^[7][3]. Однако чуть более чем через 15 лет, 3 сентября 1993 года было объявлено о запуске проекта распределённых вычислений с координацией через электронную почту по нахождению сомножителей числа RSA-129 и решению головоломки. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (три из которых были факс-машина). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE (англ.)» («Волшебные слова -- это брезгливый ягнятник»). Полученную награду победители пожертвовали в фонд свободного программного обеспечения.

После публикации Мартина Гарднера полное описание новой криптосистемы любой желающий мог получить, выслав по почте запрос Рональду Ривесту с приложенным конвертом с обратным адресом и марками на 35 центов. Полное описание новой криптосистемы было опубликовано в журнале «Communications of the ACM» в феврале 1978 года.

Заявка на патент была подана 14 декабря 1977 года, в качестве владельца был указан MIT. Патент 4405829 был выдан 20 сентября 1983 года, а 21 сентября 2000 года срок его действия истёк. Однако за пределами США у изобретателей патента на алгоритм не было, так как в большинстве стран его необходимо было получить до первой публикации^[.

В 1982 году Ривест, Шамир и Адлеман организовали компанию RSA Data Security (англ.) (в настоящий момент -- подразделение EMC). В 1989 году RSA, вместе с симметричным шифром DES, упоминается в RFC 1115, тем самым начиная использование алгоритма в зарождающейся сети Internet, а в 1990 году использовать алгоритм начинает министерство обороны США.

В ноябре 1993 года открыто публикуется версия 1.5 стандарта PKCS1 , описывающего применение RSA для шифрования и создания электронной подписи. Последние версии стандарта также доступны в виде RFC (RFC 2313 -- 1.5, 1993 год; RFC 2437 -- 2.0, 1998 год; RFC 3447 -- 2.1, 2002 год).

В декабре 1997 года была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал криптосистему, аналогичную RSA в 1973 году.

2. Описание и работа алгоритма RSA

2.1 Описание алгоритма

Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

· если известно {\displaystyle x}x, то f(x){\displaystyle f(x)}  вычислить относительно просто;

· если известно {\displaystyle y=f(x)}y=f(x), то для вычисления {\displaystyle x}x нет простого (эффективного) пути.

Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть.

Для{\displaystyle \forall } допустимых пар открытого и закрытого ключей (p,s){\displaystyle (p,s)} существуют {\displaystyle \existсоответствующие функции шифрования (x){\displaystyle E_{p}(x)} и расшифрования {\displaystyle D_{s}(x)}(x){\displaystyle E_{p}(x)} такие, что для {\displaystyle \forall } сообщения {\displaystyle m\in M}m принадлежит M, где {\displaystyle M}M -- множество допустимых сообщений,

{\displaystyle m=D_{s}(E_{p}(m))=E_{p}(D_{s}(m)).}

алгоритм криптографический ключ секретный

2.2 Алгоритм создания открытого и секретного ключей

Первым этапом любого асимметричного алгоритма является создание пары ключей - открытого и закрытого и распространение открытого ключа "по всему миру".

1. Создание ключей

Для алгоритма RSA этап создания ключей состоит из следующих операций:

1. Выбираются два очень больших простых числа  and .

2. Вычисляется их произведение , которое называется модулем.

3. Вычисляется значение функции Эйлера от числа :

4. Выбирается произвольное число  ( ), взаимно простое со значением функции .

Число  называется открытой экспонентой

5. С помощью алгоритма Евклида вычисляется число , которое удовлетворяет условию 

6. Пара  публикуется в качестве открытого ключа RSA.

7. Пара  играет роль закрытого ключа RSA и держится в секрете.

2.3 Шифрование и расшифрование

Предположим, отправитель хочет послать получателю сообщение .

Сообщениями являются целые числа в интервале от 0 до , т.е . . На рисунке представлена схема алгоритма RSA.

Рисунок - Схема алгоритма RSA

Алгоритм Отправителя:

1. Взять открытый ключ  получателя

8. Взять открытый текст 

9. Зашифровать сообщение с использованием открытого ключа получателя:

Алгоритм Получателя:

1. Принять зашифрованное сообщение 

10. Взять свой закрытый ключ 

11. Применить закрытый ключ для расшифрования сообщения:

Уравнения (1) и (2), на которых основана схема RSA, определяют взаимно обратные преобразования множества 

2.4 Пример использования алгоритма

В таблице представлен пример использования алгоритма RSA. Отправитель отправил зашифрованное сообщение «111111» и получатель, используя свой закрытый ключ, расшифровал его.

3. Программная реализация алгоритма RSA

Для реализации алгоритма был выбран язык программирование C++. Ниже представлена рабочая программа RSA.

Рисунок интерфейс программы

Рисунок интерфейс программы

Open text - поле для ввода исходного текста. Сюда мы вводим текст для дальнейшей зашифровки.

Рисунок интерфейс программы

Далее в программе вычисляются p и q, затем вычисляется n, затем fi, публичный и приватный ключи.

Рисунок интерфейс программы

Рисунок интерфейс программы

Decrypted text - расшифрованный текст
Decrypted text (ASCI) - расшифрованный текст в (ASCI) кодах.

Вывод

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

Список используемой литературы

1. Семенов Ю.А. Протоколы Internet // М.: Проспект, 2011. - 114 с.

2. Беляев А.В. Методы и средства защиты информации // ЧФ СПбГТУ, 2010. - 142с.

3. Венбо М. Современная криптография. Теория и практика // М.: Вильямс, 2005. -- 768 с.

4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты // М.: Триумф, 2002. -- 816 с.

5. Алгоритм RSA // Интернет ресурс: http://ru.wikipedia.org/wiki/Rsa

Размещено на Allbest.ru