Меню

Главная
Случайная статья
Настройки
RSA
Материал из https://ru.wikipedia.org

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

Криптосистема RSA стала первой системой, пригодной и для шифрования и цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPsec/IKE и других[3].

Содержание

История

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

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

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

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

9686
1477
8829
7431
0816
3569
8962
1829
9613
1409
0575
9874
2982
3147
8013
9451
7546
2225
9991
6951
2514
6622
3919
5781
2206
4355
1245
2093
5708
8839
9055
5154


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

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

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

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

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

В декабре 1997 года была обнародована информация о приоритете Клиффорда Кокса[14].

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

Введение

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


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

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

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


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

RSA-ключи генерируются следующим образом[15]:
1) выбираются два различных случайных простых числа и заданного размера (например, 1024 бита каждое);
2) вычисляется их произведение , которое называется модулем;
3) вычисляется значение функции Эйлера от числа :
;
4) выбирается целое число (), взаимно простое со значением функции ;
число называется открытой экспонентой (англ. public exponent);
обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например,
простые из чисел Ферма: 17, 257 или 65537, так как в этом случае время, необходимое для шифрования с использованием
быстрого возведения в степень, будет меньше;
слишком малые значения , например 3, потенциально могут ослабить безопасность схемы RSA.[16];
5) вычисляется число , мультипликативно обратное к числу по модулю , то есть число, удовлетворяющее сравнению:
(число называется секретной экспонентой; обычно оно вычисляется при помощи расширенного алгоритма Евклида);
6) пара публикуется в качестве открытого ключа RSA (англ. RSA public key);
7) пара играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.


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

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

Сообщениями являются целые числа в интервале от до . [15]

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

Алгоритм шифрования сеансового ключа

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

Алгоритм шифрования сеансового ключа выглядит следующим образом[17]:
Downgrade Counter