RSA

Материал из Википедии — свободной энциклопедии

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

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

Содержание

1 История
2 Описание алгоритма
3 Некоторые особенности алгоритма
4 Длина ключа
5 Применение RSA
6 См. также
7 Ссылки
8 Литература

[править] История

Описание 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). Открытый ключ не требуется сохранять в тайне, он используется для шифрования данных. Если сообщение было зашифровано открытым ключом, то расшифровать его можно только соответствующим секретным ключом.

[править] Генерация ключей

Для того, чтобы сгенерировать пару ключей выполняются следующие действия:

Выбираются два больших случайных простых числа $p\,$ и $q\,$
Вычисляется их произведение $n=pq \,$
Вычисляется Функция Эйлера $\varphi(n)=(p-1)(q-1)$
Выбирается целое $e\,$ такое, что $1<e<\varphi(n)$ и $e\,$ взаимно простое с $\varphi(n)$
С помощью расширенного алгоритма Евклида находится число $d\,$ такое, что $ed\equiv 1\pmod{\varphi(n)}$ это значит, что $de = 1 + k\varphi(n)\,$ при некотором целом $k\,$ .

Число $n\,$ называется модулем, а числа $e\,$ и $d\,$ — открытой и секретной экспонентами, соответственно. Пара чисел $(n,\,e)$ является открытой частью ключа, а $d\,$ — секретной. Числа $p\,$ и $q\,$ после генерации пары ключей могут быть уничтожены, но ни в коем случае не должны быть раскрыты.

[править] Шифровывание и расшифровывание

Для того, чтобы зашифровать сообщение $m<n\,$ вычисляется

$c=m^e\bmod\,n \,$ .

Число $c\,$ и используется в качестве шифртекста. Для расшифровывания нужно вычислить

$m=c^d\bmod\,n \,$ .

Нетрудно убедиться, что при расшифровывании мы восстановим исходное сообщение:

$c^d\equiv (m^e)^d\equiv m^{ed}\pmod n\,$

Из условия

$ed\equiv 1\pmod{\varphi(n)}$

следует, что

$ed=k\varphi(n)+1$ для некоторого целого $k\,$ , следовательно

$m^{ed}\equiv m^{k\varphi(n)+1}\pmod n$

Согласно теореме Эйлера:

$m^{\varphi(n)}\equiv 1\pmod n$ ,

поэтому

$m^{k\varphi(n)+1}\equiv m \pmod n$

$c^d\equiv m\pmod n\,$

[править] Пример

Сгенерируем пару ключей. Выберем два простых числа

$p=3557\,$

$q=2579\,$

Вычислим модуль

$n=p\cdot q=3557\cdot2579=9173503$

Вычислим функцию Эйлера

$\varphi(n)=(p-1)(q-1)=3556\cdot2578=9167368$

Положим открытый показатель равным 3

$e=3\,$

С помощью расширенного алгоритма Евклида вычислим секретный показатель

$d=6111579\,$

Заметьте, что

$e\cdot d\ \bmod\ \varphi(n)=3\cdot6111579\ \bmod\ 9167368=1\,$

Пара чисел (3, 9173503) образует открытую часть ключа, а число 6111579 является секретным ключом.

Зашифруем с помощью открытого ключа число $m=111111\,$ :

$c=m^e\bmod\ n=111111^3\bmod\ 9173503=4051753$

Шифртекстом является число 4051753.

Для расшифрования вычисляем

$c^d\bmod\ n=4051753^{6111579}\bmod\ 9173503=111111$

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

[править] Цифровая подпись

RSA может использоваться не только для шифрования, но и для цифровой подписи. Подпись $s\,$ сообщения $m\,$ вычисляется с использованием секретного ключа по формуле:

$s=m^d\bmod\ n\,$

Для проверки правильности подписи нужно убедиться, что выполняется равенство

$m=s^e\bmod\ n\,$

[править] Некоторые особенности алгоритма

[править] Генерация простых чисел

На случайные простые числа $p\,$ и $q\,$ накладываются следующие дополнительные ограничения:

$p\,$ и $q\,$ не должны быть слишком близки друг к другу, иначе можно будет их найти используя метод факторизации Ферма. Однако, если оба простых числа $p\,$ и $q\,$ были сгенерированы независимо, то это ограничение с огромной вероятностью автоматически выполняется.
Необходимо выбирать «сильные» простые числа, чтобы нельзя было воспользоваться p-1 алгоритмом Полларда.

[править] Дополнение сообщений

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

значения $m=0\,$ и $m=1\,$ дадут при зашифровании шифртексты 0 и 1 при любых значениях $e\,$ и $n\,$ .
при малом значении открытого показателя ( $e=3\,$ , например) возможна ситуация, когда окажется, что $m^e<n\,$ . Тогда $c=m^e\bmod\ n=m^e\,$ , и нарушитель легко сможет восстановить исходное сообщение вычислив корень степени $e\,$ из $c\,$ .
поскольку RSA является детерминированным алгоритмом, то есть не использует случайных значений в процессе работы, то нарушитель может использовать атаку с выбранным открытым текстом.

Для решения перечисленных проблем сообщения дополняются перед каждым зашифрованием некоторым случайным значением — солью. Дополнение выполняется таким образом, чтобы гарантировать, что $m\neq0\,$ , $m\neq1\,$ и $m^e>n\,$ . Кроме того, поскольку сообщение дополняется случайными данными, то зашифровывая один и тот же открытый текст мы каждый раз будем получать другое значение шифртекста, что делает атаку с выбранным открытым текстом невозможной.

[править] Выбор значения открытого показателя

RSA работает значительно медленнее симметричных алгоритмов. Для повышения скорости шифрования открытый показатель $e\,$ выбирается небольшим, обычно 3, 17 или 65537. Эти числа в двоичном виде содержат только по две единицы, что уменьшает число необходимых операций умножения при возведении в степень. Например, для возведения числа $m\,$ в степень 17 нужно выполнить только 5 операций умножения:

$m^2= m\cdot m$

$m^4=m^2\cdot m^2$

$m^8=m^4\cdot m^4$

$m^{16}=m^8\cdot m^8$

$m^{17}=m^{16}\cdot m$

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

[править] Выбор значения секретного показателя

Значение секретного показателя $d\,$ должно быть достаточно большим. В 1990 году Михаэль Винер (Michael J. Wiener) показал, что если $q<p<2q\,$ и $d<n^{\frac14}/3$ , то имеется эффективный способ вычислить $d\,$ по $n\,$ и $e\,$ . Однако, если значение $e\,$ выбирается небольшим, то $d\,$ оказывается достаточно большим и проблемы не возникает.

[править] Длина ключа

Число n должно иметь размер не меньше 512 бит. На 2008 год система шифрования на основе RSA считается надёжной, начиная с размера N в 1024 бита.

[править] Применение RSA

Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.

Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать надежный генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам симметричный криптоалгоритм (в данное время широкое применение находят Rijndael, IDEA, Serpent, Twofish).

[править] См. также

Алгоритм быстрого возведения в степень

[править] Ссылки

[править] Литература

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

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

| RSA | DSA | Схема Эль-Гамаля | ГОСТ Р 34.10-2001 |

RSA