RSA

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

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

История

Описание RSA было опубликовано в 1977 году Рональдом Райвестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT).

Британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году во внутренних документах центра, но эта работа не была раскрыта до 1977 года и Райвест, Шамир и Адлеман разработали RSA независимо от работы Кокса.

В 1983 году MIT был выдан патент 4405829 США, срок действия которого истёк 21 сентября 2000 года.

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

Безопасность алгоритма RSA основана на трудности задачи разложения на множители. Алгоритм использует два ключа — открытый (public) и секретный (private), вместе открытый и соответствующий ему секретный ключи образуют пару ключей (keypair). Открытый ключ не требуется сохранять в тайне, он используется для зашифрования данных. Если сообщение было зашифровано открытым ключом, то расшифровать его можно только соответствующим секретным ключом.

Генерация ключей

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

1. Выбираются два больших простых числа $p\,$ и $q\,$
2. Вычисляется их произведение $n=pq\,$
3. Вычисляется Функция Эйлера $\varphi (n)=(p-1)(q-1)$
4. Выбирается целое $e\,$ такое, что $1<e<\varphi (n)$ и $e\,$ взаимно простое с $\varphi (n)$
5. С помощью расширенного алгоритма Евклида находится число $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\cdot 2579=9173503$

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

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

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

$e=3\,$

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

$d=6111579\,$

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

$e\cdot d\ {\bmod {\ }}\varphi (n)=3\cdot 6111579\ {\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\neq 0\,$, $m\neq 1\,$ и $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^{\frac {1}{4}}/3$, то имеется эффективный способ вычислить $d\,$ по $n\,$ и $e\,$. Однако, если значение $e\,$ выбирается небольшим, то $d\,$ оказывается достаточно большим и проблемы не возникает.

Длина ключа

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

Применение RSA

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

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

Ссылки

• Справочное описание
• Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (бесплатно, в формате PDF)

Литература

• 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