RSA

RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом.

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

История

Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом. Разработанный впоследствии алгоритм Диффи-Хеллмана-Меркля позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных средств, один из пользователей не мог быть уверен, что он обменялся ключами именно с тем пользователем, который ему был нужен.

Изучив эту статью, трое ученых Рональд Райвест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman) из Массачусетского Технологического Института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами, им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

Описание RSA было опубликовано в августе 1977 года в журнале Scientific American. Авторы RSA поддерживали идею её активного распространения. В свою очередь, Агентство национальной безопасности (США), опасаясь использования этого алгоритма в негосударственных структурах, на протяжении нескольких лет безуспешно требовало прекращения распространения системы. Ситуация порой доходила до абсурда — например, когда программист Адам Бек (Adam Back) описал на языке Perl алгоритм RSA, состоящий из пяти строк, правительство США запретило распространение этой программы за пределами страны. Люди, недовольные подобным ограничением, в знак протеста напечатали текст этой программы на своих футболках.

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

В 1977 году создателями RSA была зашифрована фраза «The Magic Words are Squeamish Ossifrage» («Волшебные слова — это брезгливый ягнятник»). За расшифровку была обещана награда в 100 долларов США. Лишь в конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. На протяжении полугода более 600 добровольцев жертвовали процессорное время 1600 машин (две из которых были факс-машинами). Координирование проходило через Интернет, и это был один из первых подобных проектов распределённых вычислений. Полученную награду победители пожертвовали в фонд свободного программного обеспечения.

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

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

Введение

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

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

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

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

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

$\forall\,$ сообщения $M \in W\,$, где $W\,$ — множество допустимых сообщений.
  $\forall\,$ открытого и секретного ключа $P\,$ и $S\,$ 
    $\exist\,$ соответствующие функции шифрования $E_p()\,$ и расшифрования $D_s():\,$  
                     
                               $M=D_s(E_p(M))\,$
                               $M=D_p(E_s(M))\,$

Алгоритм создания открытого и секретного ключей

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

1. Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое).
2. Вычисляется их произведение n = pq, которое называется модулем.
3. Вычисляется значение функции Эйлера от числа n:

   φ(n) = (p − 1)(q − 1).

4. Выбирается целое число e (1 < e < φ(n)), взаимно простое со значением функции φ(n). Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
   • Число e называется открытой экспонентой (англ. public exponent)
   • Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в e.
   • Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.
5. Вычисляется число d, мультипликативно обратное к числу e по модулю φ(n), то есть число, удовлетворяющее условию:

   $d e \equiv 1\pmod{\varphi(n)},$ или: de = 1 + kφ(n), где k — некоторое целое число.

   • Примечание: Можно вычислять и так (e*d) mod ((p-1)*(q-1)) = 1. Результат операции i mod j — остаток от целочисленного деления i на j, то есть если имеем (d*3) mod 20 = 1. Значит d будет, например 7. (Может быть и другим, например 27).
   • Число d называется секретной экспонентой.
   • Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
6. Пара e, n публикуется в качестве открытого ключа RSA (англ. RSA public key).
7. Пара d, n играет роль секретного ключа RSA (англ. RSA private key) и держится в секрете.

Шифрование и расшифрование

Схема RSA

Предположим, сторона $B \,$ хочет послать стороне $A \,$ сообщение $M \,$.

Сообщением являются целые числа лежащие от $0 \,$ до $n-1 \,$, т.е $M \isin D=\mathbb{Z}_{n}\,$.

Алгоритм: Взять открытый ключ $(e,n) \,$ стороны $A \,$ Взять открытый текст $M \,$ Передать шифрованное сообщение: $P_A(M)=M^e \mod n~~~~~~~~~~(1)\,$

Алгоритм: Принять зашифрованное сообщение $C \,$ Применить свой секретный ключ $(d,n) \,$ для расшифровки сообщения: $S_A(C)=C^d \mod n~~~~~~~~~~(2)\,$

Корректность схемы RSA

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

Доказательство  

Действительно, для $\forall M \isin \mathbb{Z}_{n}\,$

$P(S(M))=S(P(M))= M^{ed} \mod n \,$

Докажем, что $M^{ed} \equiv M \pmod p ~~~\forall M \,$.

Возможны два случая:

• $M \not\equiv 0 \pmod p \,$.

Поскольку числа $e\,$ и $d\,$ являются взаимно обратными относительно умножения по модулю φ(n) = (p − 1)(q − 1), т.e

$ed=1+k(p-1)(q-1)\,$ для некоторого целого $k\,$ , тогда

$M^{ed}~~\equiv M(M^{p-1})^{k(q-1)} \pmod p \equiv$

$\equiv M(1)^{k(q-1)} \pmod p \equiv$

$\equiv M \pmod p ,$

где второе тождество следует из теоремы Ферма.

• $M \equiv 0 \pmod p \,$, тогда $M^{ed} \equiv M \pmod p \,$

Таким образом, при всех $M\,$ выполняется равенство

$M^{ed} \equiv M \pmod p\,$

Аналогично можно показать, что $M^{ed} \equiv M \pmod q~~~ \forall M\,$.

Таким образом, из Китайской теоремы об остатках

$\boldsymbol {M^{ed} \equiv M \pmod n~~~\forall M}\,$

Пример

Этап	Описание операции	Результат операции
Генерация ключей	Выбрать два простых числа	$p=3557, q=2579\,$
	Вычислить модуль	$n=p\cdot q=3557\cdot2579=9173503$
	Вычислить функцию Эйлера	φ(n) = (p − 1)(q − 1) = 9167368
	Выбрать открытую экспоненту	$e=3\,$
	Вычислить секретную экспоненту	$d=6111579\ (k=2)\,$
	Опубликовать открытый ключ	$(e,n)=(3,9173503)\,$
	Сохранить секретный ключ	$(d,n)=(6111579,9173503)\,$
Шифрование	Выбрать текст для зашифровки	$M=111111\,$
	Вычислить шифротекст	$P(M)=M^e \bmod n=111111^3\bmod\ 9173503=4051753\,$
Расшифрование	Вычислить исходное сообщение	$S(C)=C^d \bmod n=4051753^{6111579}\bmod\ 9173503=111111\,$

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

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

Предположим, что стороне $A\,$ нужно отправить стороне $B\,$ ответ $M'\,$, подтверждённый цифровой подписью.

Алгоритм: Взять открытый текст $M'~~~\,$ Создать цифровую подпись $\sigma \,$ с помощью своего секретного ключа$(d,n) \,$ $\sigma = S_A(M')=M'^d \mod n\,$ Передать пару $(M',\sigma )\,$, состоящую из сообщения и подписи.

Алгоритм: Принять пару $(M',\sigma )\,$ Взять открытый ключ $(e,n)\,$ стороны $A\,$ Проверить подлинность подписи: $P_A(\sigma )=\sigma ^e \mod n \equiv M' \rarr \,$ подпись верная

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

Важное свойство цифровой подписи заключается в том, что её может проверить каждый, кто имеет доступ к открытому ключу ее автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись. Например, сторона $A\,$ может переслать стороне $B\,$ электронный чек. После того как сторона $B\,$ проверит подпись стороны $A\,$ на чеке, она может передать его в свой банк, служащие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию.

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

Скорость работы алгоритма RSA

Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления $a=b^e \bmod n \,$ представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью алгоритма быстрого возведения в степень. Таким образом для вычисления $M^e \bmod n \,$ требуется $O( \ln e) \,$ операций умножения по модулю.

Доказательство  

• представим $e \,$ в двоичной системе счисления:

$e=e_{k} \cdot 2^{k}+e_{k-1} \cdot 2^{k-1}+...+e_{1} \cdot 2+e_{0}$, где $e_{k}=1, e_{i} \in \{ 0,1 \}$

• положим $M_0=M \,$ и затем для $i=1,...,k \,$ вычислим

$M_i=(M_{i-1}^2 \cdot M^{e_{k-i}} )\bmod n \,$

• найденное $M_k \,$ и будет искомым значением $M^e \bmod n \,$

Т.к каждое вычисление на шаге 2 требует не более трёх умножений по модулю $n \,$ и этот шаг выполняется $k \le \log_2 e \,$ раз, то сложность алгоритма может быть оценена величиной $O( \ln e) \,$.

Чтобы проанализировать время выполнения операций с открытым и секретным ключами, предположим, что открытый ключ $(e,n) \,$ и секретный ключ $(d,n) \,$ удовлетворяют соотношениям $\log_2 e =O(1),\log_2 d \le \beta \,$. Тогда в процессах их применения выполняется соответственно $O(1)\,$ и $O(\beta)\,$ умножений по модулю.

Таким образом время выполнения операций растёт с увеличением количества ненулевых битов в двоичном представлении открытой экспоненты e. Чтобы увеличить скорость шифрования, значение e часто выбирают равным 17, 257 или 65537 — простым числам, двоичное представление которых содержит лишь две единицы: 17 = 0x11, 257 = 0x101, 65537 = 0x10001 (простые числа Ферма). Стоит также заметить что скорость работы прямо зависит от количества умножений, и увеличение числа приводит к уменьшению скорости (т.к. в алгоритме быстрого умножения, на каждой итерации происходит умножение для увеличения степени). Т.е. если использовать вместо 17=0x11=0b10001 13=0x0D=0b1101 то кол-во умножений будет одинаковым, т.е. скорость работы будет сравнима в обоих случаях. Действительно: в первом случае: 4 умножения для получения степени 16 и 2 умножения результата на степень. Во втором случае: 3 умножения для получения степени 8 и 3 умножения результат на степень. Поэтому, вместо 17 можно использовать 13, а 65537 можно заменить на любое из (32771, 32801, 32833, 40961). ЗАМЕЧАНИЕ: Этот подход верен для случая быстрого окончания алгоритма, когда цикл завершается сразу, как только не остается не нулевых бит в степени.

По эвристическим оценкам длина секретной экспоненты d, нетривиальным образом зависящей от открытой экспоненты e и модуля n, с большой вероятностью близка к длине n. Поэтому расшифрование данных идёт медленнее чем шифрование, а проверка подписи быстрее чем подписание.

Алгоритм RSA намного медленнее чем DES и другие алгоритмы блочного шифрования.

Криптоанализ RSA

На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера $n \,$ в 1024 бита.

Группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года.

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

На первый шаг (выбор пары полиномов степени 6 и 1) было потрачено около полугода вычислений на 80 процессорах, что составило около 3 % времени, потраченного на главный этап алгоритма (просеивание), который выполнялся на сотнях компьютеров в течение почти двух лет. Если интерполировать это время на работу одного процессора AMD Opteron 2.2ГГц с 2Гб памяти, то получилось бы порядка 1500 лет. Обработка данных после просеивания для следующего ресурсоёмкого шага (линейной алгебры) потребовалось несколько недель на малом количестве процессоров. Заключительный шаг после нахождения нетривиальных решений ОСЛУ занял не более 12 часов.

Решение ОСЛУ проводилось с помощью метода Видемана на нескольких раздельных кластерах и длилось чуть менее 4 месяцев. При этом размер разреженной матрицы составил 192 796 550х192 795 550 при наличии 27 795 115 920 ненулевых элементов (то есть в среднем 144 ненулевых элементов на строку). Для хранения матрицы на жёстком диске понадобилось около 105 гигабайт. В то же время понадобилось около 5 терабайт сжатых данных для построения данной матрицы.

В итоге группе удалось вычислить 232-цифровой ключ, открывающий доступ к зашифрованным данным.

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

Зная разложение модуля $n \,$ на произведение двух простых чисел, противник может легко найти секретную экспоненту $d \,$ и тем самым взломать RSA. Однако на сегодняшний день самый быстрый алгоритм факторизации — решето обобщённого числового поля (General Number Field Sieve), скорость которого для k-битного целого числа составляет

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

не позволяет разложить большое целое за приемлемое время.

Применение RSA

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

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

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

Литература

• A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7.
• Венбо Мао Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 с. — 2 000 экз. — ISBN 5-8459-0847-7, ISBN 0-13-066943-1.
• Нильс Фергюсон, Брюс Шнайер Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: «Диалектика», 2004. — 432 с. — 3 000 экз. — 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.