RSA

RSA
Дата возникновения	1977[1]
Названо в честь	Рональд Линн Ривест, Ади Шамир и Леонард Макс Адлеман
Определяющая формула	${\displaystyle \left(m^{e}\right)^{d}\equiv m{\pmod {n}}}$[2]
Обозначение в формуле	${\displaystyle m}$, ${\displaystyle e}$, ${\displaystyle d}$ и ${\displaystyle n}$

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

Криптосистема RSA стала первой системой, пригодной и для

Алгоритм шифрования с открытым и закрытым ключом приписывается Уитфилду Диффи и Мартину Хеллману, которые опубликовали эту концепцию в 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

После публикации Мартина Гарднера полное описание новой криптосистемы любой желающий мог получить, выслав по почте запрос Рональду Ривесту с приложенным конвертом с обратным адресом и марками на 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].

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

• если известно ${\displaystyle x}$, то ${\displaystyle f(x)}$ вычислить относительно просто;
• если известно ${\displaystyle y=f(x)}$, то для вычисления ${\displaystyle x}$ нет простого (эффективного) пути.

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

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

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

${\displaystyle \forall }$ допустимых пар открытого и закрытого ключей ${\displaystyle (p,s)}$

${\displaystyle \exists }$ соответствующие функции шифрования ${\displaystyle E_{p}(x)}$ и расшифрования ${\displaystyle D_{s}(x)}$ такие, что

${\displaystyle \forall }$ сообщения ${\displaystyle m\in M}$, где ${\displaystyle M}$ — множество допустимых сообщений,

${\displaystyle m=D_{s}(E_{p}(m))=E_{p}(D_{s}(m)).}$

RSA-ключи генерируются следующим образом^[15]:

1) выбираются два различных случайных простых числа ${\displaystyle p}$ и ${\displaystyle q}$ заданного размера (например, 1024 бита каждое);

2) вычисляется их произведение ${\displaystyle n=p\cdot q}$, которое называется модулем;

3) вычисляется значение функции Эйлера от числа ${\displaystyle n}$:

${\displaystyle \varphi (n)=(p-1)\cdot (q-1)}$;

4) выбирается целое число ${\displaystyle e}$ (${\displaystyle 1<e<\varphi (n)}$), взаимно простое со значением функции ${\displaystyle \varphi (n)}$;

число ${\displaystyle e}$ называется открытой экспонентой (англ. public exponent);

обычно в качестве ${\displaystyle e}$ берут простые числа, содержащие небольшое количество единичных бит в

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

, будет меньше;

слишком малые значения ${\displaystyle e}$, например 3, потенциально могут ослабить безопасность схемы RSA.^[16];

5) вычисляется число ${\displaystyle d}$, мультипликативно обратное к числу ${\displaystyle e}$ по модулю ${\displaystyle \varphi (n)}$, то есть число, удовлетворяющее сравнению:

${\displaystyle d\cdot e\equiv 1{\pmod {\varphi (n)}}}$

(число ${\displaystyle d}$ называется секретной экспонентой; обычно оно вычисляется при помощи расширенного алгоритма Евклида);

6) пара ${\displaystyle (e,n)}$ публикуется в качестве открытого ключа RSA (англ. RSA public key);

7) пара ${\displaystyle (d,n)}$ играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

Предположим, Боб хочет послать Алисе сообщение ${\displaystyle m}$.

Сообщениями являются целые числа в интервале от ${\displaystyle 0}$ до ${\displaystyle n-1}$. ^[15]

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

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

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

В случае, когда сеансовый ключ больше, чем модуль ${\displaystyle n}$, сеансовый ключ разбивают на блоки нужной длины (в случае необходимости дополняют нулями) и шифруют каждый блок.

Уравнения ${\displaystyle (1)}$ и ${\displaystyle (2)}$, на которых основана схема RSA, определяют взаимно обратные преобразования множества ${\displaystyle \mathbb {Z} _{n}}$

Система RSA может использоваться не только для шифрования, но и для

Предположим, что Алисе (стороне ${\displaystyle A}$) нужно отправить Бобу (стороне ${\displaystyle B}$) сообщение ${\displaystyle m}$, подтверждённое

Поскольку

Заметим, что подписанное сообщение ${\displaystyle m}$ не зашифровано. Оно пересылается в исходном виде и его содержимое не защищено от нарушения конфиденциальности. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа, принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа^[17]. Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.

Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления ${\displaystyle a=b^{c}{\bmod {n}}}$ представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью

${\displaystyle m^{e}{\bmod {n}}}$

${\displaystyle O\left(\ln e\right)}$

.

Использование китайской теоремы об остатках для ускорения расшифрования

При расшифровании или подписывании сообщения в алгоритме RSA показатель вычисляемой степени будет довольно большим числом (порядка 1000 бит). Поэтому требуется алгоритм, сокращающий количество операций. Так как числа ${\displaystyle p}$ и ${\displaystyle q}$ в разложении ${\displaystyle N=pq}$ известны владельцу закрытого ключа, то можно вычислить:

${\displaystyle m_{p}=C^{d}{\bmod {p}}=C^{d{\bmod {p-1}}}{\bmod {p}},}$ ${\displaystyle m_{q}=C^{d}{\bmod {q}}=C^{d{\bmod {q-1}}}{\bmod {q}}.}$

Поскольку ${\displaystyle p}$ и ${\displaystyle q}$ — числа порядка ${\displaystyle 2^{512},}$ на эти действия потребуется два возведения числа в 512-битовую степень по модулю 512-битового числа. Это существенно (для 1024 бит тестирование показало в 3 раза) быстрее, чем одно возведение в 1024-битовую степень по модулю 1024-битового числа. Далее осталось восстановить ${\displaystyle m}$ по ${\displaystyle m_{p}}$ и ${\displaystyle m_{q},}$ что можно сделать с помощью китайской теоремы об остатках^[20].

Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования^[21]

${\displaystyle c=E(m)=m^{e}\mod n}$.

Для вычисления ${\displaystyle m}$ по известным ${\displaystyle c,e,n}$ нужно найти такой ${\displaystyle d}$, чтобы

${\displaystyle e\cdot d\equiv 1{\pmod {\varphi (n)}},}$

то есть найти обратный элемент к ${\displaystyle e}$ в мультипликативной группе вычетов по модулю ${\displaystyle \varphi (n).}$

Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение ${\displaystyle \varphi (n)}$. Для вычисления функции Эйлера от известного числа ${\displaystyle n}$ необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — «потайной дверцей» (

${\displaystyle d}$

${\displaystyle \exp((c+o(1))k^{\frac {1}{3}}\log ^{\frac {2}{3}}k)}$ для некоторого ${\displaystyle c<2}$.

В 2010 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля^[22]. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года^[23]. С 31 декабря 2013 года браузеры Mozilla перестали поддерживать сертификаты удостоверяющих центров с ключами RSA меньше 2048 бит^[24].

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

В некоторых приложениях требуется ускорить процесс расшифровывания в алгоритме RSA. Поэтому выбирается небольшая расшифровывающая экспонента. В случае когда расшифровывающая экспонента ${\displaystyle d<N^{\frac {1}{4}}}$ можно определить ${\displaystyle d}$ за полиномиальное время с помощью атаки Винера^[20], опирающейся на непрерывные дроби.

Подробнее

По вещественному числу ${\displaystyle \alpha \in \mathbb {R} }$ определим последовательности:

${\displaystyle \alpha _{0}=\alpha ,p_{0}=q_{0}=1,p_{1}=a_{0}a_{1}+1,q_{1}=a_{1},}$
${\displaystyle \alpha _{i}=\lfloor \alpha _{i}\rfloor ,\alpha _{i+1}={\frac {1}{\alpha _{i}-a_{i}}},}$
${\displaystyle p_{i}=a_{i}p_{i-1}+p_{i-1}}$ при ${\displaystyle i\geq 2,}$

${\displaystyle q_{i}=a_{i}q_{i-1}+q_{i-1}}$ при ${\displaystyle i\geq 2.}$

Целые числа ${\displaystyle a_{0},a_{1},a_{2},...}$ называются непрерывной дробью, представляющей ${\displaystyle \alpha ,}$ а рациональные числа ${\displaystyle {\frac {p_{i}}{q_{i}}}-}$ подходящими дробями. Каждая из подходящих дробей несократима, а скорость роста их знаменателей сравнима с показательной. Один из важных результатов теории непрерывных дробей:

Если несократимая дробь ${\displaystyle {\frac {p}{q}}}$ удовлетворяет неравенству:
${\displaystyle \left|\alpha -{\frac {p}{q}}\right|\leq {\frac {1}{2q^{2}}},}$

то ${\displaystyle {\frac {p}{q}}-}$ одна из подходящих дробей в разложении ${\displaystyle \alpha }$ в непрерывную дробь.

Пусть у нас есть модуль ${\displaystyle N=pq,}$ причём ${\displaystyle q<p<2q.}$  Допустим нападающему известна шифрующая экспонента E, обладающая свойством
${\displaystyle Ed=1\mod \varphi ,}$
где ${\displaystyle \varphi =\varphi (N)=(p-1)(q-1).}$  Будем также считать, что ${\displaystyle E<\varphi ,}$ поскольку это выполнено в большинстве приложений. Из предположений следует, что
${\displaystyle Ed-k\varphi =1.}$
Следовательно,

${\displaystyle \left|{\frac {E}{\varphi }}-{\frac {k}{d}}\right|={\frac {1}{d\varphi }}.}$

${\displaystyle \left|N-\varphi \right|=\left|p+q-1\right|<3N^{\frac {1}{2}}.}$
Отсюда видно, что ${\displaystyle {\frac {E}{N}}-}$ довольно хорошее приближение для ${\displaystyle {\frac {k}{d}}.}$  Действительно,
${\displaystyle \left|{\frac {E}{N}}-{\frac {k}{d}}\right|=\left|{\frac {Ed-Nk}{dN}}\right|=\left|{\frac {Ed-k\varphi -Nk+k\varphi }{dN}}\right|=\left|{\frac {1-k(N-\varphi )}{dN}}\right|\leq \left|{\frac {3kN^{\frac {1}{2}}}{dN}}\right|={\frac {3k}{dN^{\frac {1}{2}}}}.}$

Так как ${\displaystyle E<\varphi ,}$ очевидно${\displaystyle ,k<d.}$ Кроме того, так как предполагалось, что ${\displaystyle d<{\frac {1}{4}}N^{\frac {1}{4}}.}$ Значит,

${\displaystyle \left|{\frac {E}{N}}-{\frac {k}{d}}\right|<{\frac {1}{2d^{2}}}.}$

Поскольку НОД${\displaystyle (k,d)=1,}$ то ${\displaystyle {\frac {k}{d}}-}$ подходящая дробь в разложении дроби ${\displaystyle {\frac {E}{N}}}$ в непрерывную. Таким образом, можно узнать расшифровывающую экспоненту, поочерёдно подставляя знаменатели подходящих дробей в выражение:

${\displaystyle (M^{E})^{d}=M\mod N}$

для некоторого случайного числа ${\displaystyle M.}$ Получив равенство, найдём ${\displaystyle d.}$ Общее число подходящих дробей, которое придётся проверить оценивается как ${\displaystyle O(lnN).}$

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

${\displaystyle d\leq {\frac {1}{3}}N^{\frac {1}{4}},}$

где ${\displaystyle d}$ — секретная экспонента, а ${\displaystyle N}$ — модуль RSA. Боне и Дерфи, используя двумерный аналог Теоремы Копперсмита, смогли обобщить атаку Винера^[20] на случай, когда

${\displaystyle d\leq N^{0,292}.}$

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

Система RSA используется для защиты

Также она используется в открытой системе шифрования

Из-за низкой скорости шифрования сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным сеансовым ключом (например,

• Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1976.1055638
• Gardner M. A New Kind of Cipher that Would Take Millions of Years to Break (англ.) // Scientific American — New York City: NPG, 1977. — Vol. 237, Iss. 2. — P. 120—124. — 5 p. — ISSN 0036-8733; 1946-7087 — doi:10.1038/SCIENTIFICAMERICAN0877-120
• Rivest R., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems (англ.) // Communications of the ACM — New York City: Association for Computing Machinery, 1978. — Vol. 21, Iss. 2. — P. 120—126. — ISSN 0001-0782; 1557-7317 — doi:10.1145/359340.359342
• Menezes A. J., Oorschot P. v., Vanstone S. A. Handbook of Applied Cryptography (англ.) — Boca Raton: CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0
• Boneh D. Twenty Years of attacks on the RSA Cryptosystem (англ.) // Notices of the American Mathematical Society / F. Morgan — AMS, 1999. — Vol. 46, Iss. 2. — P. 203–213. — ISSN 0002-9920; 1088-9477
• Bakhtiari M., Maarof M. A. Serious Security Weakness in RSA Cryptosystem (англ.) // International Journal of Computer Science Issues — 2012. — Vol. 9, Iss. 1, No 3. — P. 175—178. — ISSN 1694-0814; 1694-0784

• Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М. : Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0, ISBN 0-4712-2357-3.
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.