RSA
Материал из Википедии — свободной энциклопедии
RSA — криптографический алгоритм с открытым ключом.
RSA стал первым алгоритмом такого типа, пригодным и для шифрования и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений.
Содержание |
[править] История
Описание RSA было опубликовано в 1977 году Рональдом Райвестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT). Система была названа по первым буквам их фамилий.
Британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году во внутренних документах центра, но эта работа не была раскрыта до 1977 года и Райвест, Шамир и Адлеман разработали RSA независимо от работы Кокса.
В 1983 году MIT был выдан патент 4405829 США, срок действия которого истёк 21 сентября 2000 года.
В 1977 году создателями RSA была зашифрована фраза «The Magic Words are Squeamish Ossifrage» («Волшебные слова — это брезгливый ягнятник»). За расшифровку была обещана награда в 100 долларов США. Фраза была расшифрована в 1993—1994 годах. Более 600 добровольцев жертвовали процессорное время с около 1600 машин (две из которых были факс-машинами) больше шести месяцев. Координирование проходило через Интернет, и это был один из первых подобных проектов распределённых вычислений. Полученную награду победители пожертвовали в фонд свободного программного обеспечения.
[править] Описание алгоритма
Безопасность алгоритма RSA основана на трудности задачи разложения на множители. Алгоритм использует два ключа — открытый (public) и секретный (private), вместе открытый и соответствующий ему секретный ключи образуют пару ключей (keypair). Открытый ключ не требуется сохранять в тайне, он используется для шифрования данных. Если сообщение было зашифровано открытым ключом, то расшифровать его можно только соответствующим секретным ключом.
[править] Генерация ключей
Для того, чтобы сгенерировать пару ключей выполняются следующие действия:
- Выбираются два больших случайных простых числа
и 
- Вычисляется их произведение

- Вычисляется Функция Эйлера

- Выбирается целое
такое, что
и
взаимно простое с 
- С помощью расширенного алгоритма Евклида находится число
такое, что
это значит, что
при некотором целом
.
Число
называется модулем, а числа
и
— открытой и секретной экспонентами, соответственно. Пара чисел
является открытой частью ключа, а
— секретной. Числа
и
после генерации пары ключей могут быть уничтожены, но ни в коем случае не должны быть раскрыты.
[править] Шифровывание и расшифровывание
Для того, чтобы зашифровать сообщение
вычисляется
.
Число
и используется в качестве шифртекста. Для расшифровывания нужно вычислить
.
Нетрудно убедиться, что при расшифровывании мы восстановим исходное сообщение:
Из условия
следует, что
для некоторого целого
, следовательно
Согласно теореме Эйлера:
,
поэтому
[править] Пример
Сгенерируем пару ключей. Выберем два простых числа
Вычислим модуль
Вычислим функцию Эйлера
Положим открытый показатель равным 3
С помощью расширенного алгоритма Евклида вычислим секретный показатель
Заметьте, что
Пара чисел (3, 9173503) образует открытую часть ключа, а число 6111579 является секретным ключом.
Зашифруем с помощью открытого ключа число
:
Шифртекстом является число 4051753.
Для расшифрования вычисляем
в результате получаем исходное сообщение.
[править] Цифровая подпись
RSA может использоваться не только для шифрования, но и для цифровой подписи. Подпись
сообщения
вычисляется с использованием секретного ключа по формуле:
Для проверки правильности подписи нужно убедиться, что выполняется равенство
[править] Некоторые особенности алгоритма
[править] Генерация простых чисел
На случайные простые числа
и
накладываются следующие дополнительные ограничения:
и
не должны быть слишком близки друг к другу, иначе можно будет их найти используя метод факторизации Ферма. Однако, если оба простых числа
и
были сгенерированы независимо, то это ограничение с огромной вероятностью автоматически выполняется.- Необходимо выбирать «сильные» простые числа, чтобы нельзя было воспользоваться p-1 алгоритмом Полларда.
[править] Дополнение сообщений
При практическом использовании необходимо некоторым образом дополнять сообщения. Отсутствие дополнений может привести к некоторым проблемам:
- значения
и
дадут при зашифровании шифртексты 0 и 1 при любых значениях
и
. - при малом значении открытого показателя (
, например) возможна ситуация, когда окажется, что
. Тогда
, и нарушитель легко сможет восстановить исходное сообщение вычислив корень степени
из
. - поскольку RSA является детерминированным алгоритмом, то есть не использует случайных значений в процессе работы, то нарушитель может использовать атаку с выбранным открытым текстом.
Для решения перечисленных проблем сообщения дополняются перед каждым зашифрованием некоторым случайным значением — солью. Дополнение выполняется таким образом, чтобы гарантировать, что
,
и
. Кроме того, поскольку сообщение дополняется случайными данными, то зашифровывая один и тот же открытый текст мы каждый раз будем получать другое значение шифртекста, что делает атаку с выбранным открытым текстом невозможной.
[править] Выбор значения открытого показателя
RSA работает значительно медленнее симметричных алгоритмов. Для повышения скорости шифрования открытый показатель
выбирается небольшим, обычно 3, 17 или 65537. Эти числа в двоичном виде содержат только по две единицы, что уменьшает число необходимых операций умножения при возведении в степень. Например, для возведения числа
в степень 17 нужно выполнить только 5 операций умножения:
Выбор малого значения открытого показателя может приводить к раскрытию сообщения, если оно отправляется сразу нескольким получателям, но эта проблема решается за счёт дополнения сообщений.
[править] Выбор значения секретного показателя
Значение секретного показателя
должно быть достаточно большим. В 1990 году Михаэль Винер (Michael J. Wiener) показал, что если
и
, то имеется эффективный способ вычислить
по
и
. Однако, если значение
выбирается небольшим, то
оказывается достаточно большим и проблемы не возникает.
[править] Длина ключа
Число n должно иметь размер не меньше 512 бит. На 2008 год система шифрования на основе RSA считается надёжной, начиная с размера N в 1024 бита.
[править] Применение RSA
Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.
Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать надежный генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам симметричный криптоалгоритм (в данное время широкое применение находят Rijndael, IDEA, Serpent, Twofish).
[править] См. также
[править] Ссылки
- Справочное описание
- Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (бесплатно, в формате PDF)
- Свободный плагин Total Commander для шифрования алгоритмом RSA
[править] Литература
- Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. Handbook of Applied Cryptography. — CRC Press, October 1996. ISBN 0-8493-8523-7
- Венбо Мао Современная криптография: теория и практика = Modern Cryptography: Theory and Practice. — М.: «Вильямс», 2005. — С. 768. — ISBN 0-13-066943-1
- Нильс Фергюсон, Брюс Шнайер Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: «Диалектика», 2004. — С. 432. — ISBN 0-471-22357-3
- Шнайер, Брюс. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си — М.: Издательство ТРИУМФ, 2002—816 с.:ил. ISBN 5-89392-055-4



















