Исследовательский проект на тему: «RSA-алгоритм»

Краевое государственное бюджетное профессиональное образовательное учреждение «Хабаровский промышленно-экономический техникум»

Исследовательский проект 

на тему: «RSA-алгоритм»

Руководитель проекта: Волкова И.Б.

Авторы проекта: Рыжков Григорий, группа ИСП-12

Хабаровск

2024

Содержание

Введение…………………………………………………………………………..3стр.

1. История появления……………………………………………………………4стр.

1.2 Основные понятия криптосистемы RSA…………………………………..5стр.

2. Преимущества и недостатки…………………………………………………5стр.
3. Алгоритм создания открытого и секретного ключей………………..……5-6стр.
4. Шифрование и расшифрование……………………………………………6-7стр.
5. Доказательство корректность схемы RSA…………………………………..7стр.
6. Заключение…………………………………………………………………….8стр.
7. Литература………………………………………………………………….…9стр.

Введение 

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших простых чисел. Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других

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

Проблема: Проблема RSA обобщает задачу выполнения операции с закрытым ключом RSA с учетом только открытого ключа. Алгоритм RSA передает сообщение в показатель степени, по модулю a составное число N, коэффициенты которого неизвестны.

Цель: исследование языка шифрования RSA, используемого для кодирования и декодирования информации, а также при создании электронной подписи.

1. История появления

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

Рон Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института в течение года предприняли несколько попыток создать одностороннюю функцию, которую было бы трудно инвертировать. Ривест и Шамир, будучи компьютерными учеными, предложили множество потенциальных функций, а Адлеман, будучи математиком, отвечал за поиск их слабых мест. Они опробовали множество подходов, включая «ранцевый» и «перестановочные полиномы». Какое-то время они думали, что то, чего они хотели достичь, невозможно из-за противоречивых требований. В апреле 1977 года они провели Песах в доме одного из студентов и выпили много манишевицкого вина, а затем вернулись к себе домой около полуночи. Ривест, не в силах заснуть, лег на диван с учебником математики и начал думать о своей односторонней функции. Остаток ночи он провел, формализуя свою идею, и к рассвету большая часть статьи была готова. Алгоритм теперь известен как RSA — инициалы их фамилий в том же порядке, что и в их статье.

Клиффорд Кокс, английский математик, работавший в британской разведывательной службе Government Communications Headquarters (GCHQ), описал эквивалентную систему во внутреннем документе в 1973 г. Однако, учитывая относительно дорогие компьютеры, необходимые для ее реализации в то время, она считалась в основном курьезом и, насколько известно, так и не была применена. Однако его открытие было раскрыто только в 1997 году из-за его сверхсекретного засекречивания.

В 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 году. 

1.2 Основные понятия криптосистемы RSA

Первым шагом создания алгоритма RSA является: выбор двух простых больших натуральных чисел p и q. Затем найдем произведение этих чисел m = p*q и обозначим его как модуль шифрования. Следующим шагом найдем функцию Эйлера: hramov01.wmf.

Следующий этап алгоритма: выбор показателя степени числа e, которое называют открытым показателем. Число e должно быть таким, чтобы выполнялись следующие условия: hramov02.wmf, НОДhramov03.wmf. Далее найдем d (закрытый показатель), что hramov04.wmf. Таким образом, получаем (m, e) – открытый ключ, (m, d) – закрытый ключ. В чем же заключается безопасность криптосистемы RSA? В том, что она основывается на неразрешимой задаче, а именно разложение модуля шифрования на множители, так как продуктивный способ поиска на данный момент времени неизвестен.

2. Преимущества и недостатки 

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

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

RSA-ключи генерируются следующим образом:

1) выбираются два различных случайных простых числа и заданного размера (например, 1024 бита каждое);

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

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

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

число   называется открытой экспонентой (англ. public exponent);

обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например,

простые из чисел Ферма: 17, 257 или 65537, так как в этом случае время, необходимое для шифрования с использованием

быстрого возведения в степень, будет меньше;

слишком малые значения апример 3, потенциально могут ослабить безопасность схемы RSA.[16];

5) вычисляется число , мультипликативно обратное к числу по модулю   то есть число, удовлетворяющее сравнению:  

6) пара            публикуется в качестве открытого ключа RSA (англ. RSA public key);

7) пара             играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

4. Шифрование и расшифрование

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

Сообщениями являются целые числа в интервале от 

0 до           

Алгоритм шифрования:

• Взять открытый ключ           Алисы
• Взять открытый текст  
• Зашифровать сообщение с использованием открытого ключа Алисы:

Алгоритм расшифрования:

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

Данная схема на практике не используется по причине того, что она не является практически надёжной (semantically secured). Действительно, односторонняя функция E(m) является детерминированной — при одних и тех же значениях входных параметров (ключа и сообщения) выдаёт одинаковый результат. Это значит, что не выполняется необходимое условие практической (семантической) надёжности шифра.

5. Доказательство корректность схемы RSA

Заключение

Таким образом, можно сделать следующие выводы: криптосистема RSA является актуальной и в настоящее время. Этот метод шифрования нельзя назвать самым безопасным, так как он был разработан еще в ХХ веке. Однако для современных технологий алгоритм RSA используется и сегодня, например для передачи зашифрованных ключей. С наступлением времени электронного документооборота возникла необходимость создания электронной цифровой подписи. Она необходима, прежде всего, для признания официальности документов. Электронная цифровая подпись представляет собой перевод данных на язык криптографии. Электронная цифровая подпись и криптосистема RSA – это неделимый союз, поскольку они не могут существовать друг без друга. В Глобальной сети есть два вида ключей – это публичный и приватный. Если публичный ключ доступен любому пользователю, то приватный является защищенным от третьих лиц. Благодаря криптосистеме RSA документ является зашифрованным, но открыть доступ к нему можно в любое время. Дешифрование подписи для проверки происходит при помощи приватного ключа, а предоставление доступа к заверенному документу – через публичный ключ.

Литература

1. https://top-technologies.ru/ru/article/view?id=38220
2. https://ru.wikibrief.org/wiki/RSA_problem
3. https://ru.wikipedia.org/wiki/RSA#:~:text=RSA%20(%D0%B0%D0%B1%D0%B1%D1%80%D0%B5%D0%B2%D0%B8%D0%B0%D1%82%D1%83%D1%80%D0%B0%20%D0%BE%D1%82%20%D1%84%D0%B0%D0%BC%D0%B8%D0%BB%D0%B8%D0%B9%20Rivest,%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8%20%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%20%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D1%85%20%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85%20%D1%87%D0%B8%D1%81%D0%B5%D0%BB.&text=%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0%20RSA%20%D1%81%D1%82%D0%B0%D0%BB%D0%B0%20%D0%BF%D0%B5%D1%80%D0%B2%D0%BE%D0%B9%20%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%BE%D0%B9,%D1%88%D0%B8%D1%84%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F%2C%20%D0%B8%20%D0%B4%D0%BB%D1%8F%20%D1%86%D0%B8%D1%84%D1%80%D0%BE%D0%B2%D0%BE%D0%B9%20%D0%BF%D0%BE%D0%B4%D0%BF%D0%B8%D1%81%D0%B8.
4. Книга: Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.