RSA

From CryptoWiki
Jump to: navigation, search

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

Криптосистема RSA [MODSPKC78] разработана в 1977 году и названа в честь ее разработчиков: Rivest, Shamir и Adleman.

Вначале получатель шифртекстов создает пары ключей: открытого и секретного. Данный этап состоит из следующих операций:

  1. выбираются два достаточно больших простых числа p и q вычисляется их произведение n = p*q, называемое модулем;
  2. выбирается целое число e, такое что e < φ (n) и НОД (e, φ (n)) = 1, где φ (n) = (p – 1) * (q – 1) – функция Эйлера;
  3. вычисляется число d, удовлетворяющее условию ed = 1 (mod φ (n)).

Пара (e, n) является открытым (public) ключом, который публикуется в общедоступном сертифицированном справочнике и предоставляется всем абонентам криптосистемы RSA.

Пара (d, n) называется секретным (private) ключом, который держится в секрете.

Зашифрование открытого сообщения М выполняется по формуле:

Memod(n) = C,

где С – получившийся шифртекст.

Расшифрование шифртекста С выполняется по формуле:

Cdmod(n) = M
.

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

На рисунке 2 представлена схема передачи информации лицом В лицу А.
Рисунок 2: Схема RSA

Отправитель В создает зашифрованный текст С, возводя сообщение M в степень e и беря это значение по модулю n: C = Memod(n), где e и n – открытый (public) ключ лица А.Затем лицо В посылает С (зашифрованный текст) лицу А. Чтобы расшифровать полученный текст, А возводит полученный зашифрованный текст C в степень d и берет получившееся значение по модулю n: M = Cd(mod n), где d и n – секретный (private) ключ лица А. Значение d вычисляется при помощи расширенного алгоритма Евклида.

В настоящее время Лаборатория RSA рекомендует для обычных задач ключи размером 1024 бита, а для особо важных задач – 2048 бит.


На главную страницу раздела

Башкеев М.А., Филиппова К.С., 2016