RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.
Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других.[1]
Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» (англ. New Directions in Cryptography)[2] перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом. Разработанный впоследствии алгоритм Диффи — Хеллмана позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных средств пользователи не могли быть уверены, с кем именно они сгенерировали общий секретный ключ.
Изучив эту статью, трое учёных Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами, им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.
В августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American, с разрешения Рональда Ривеста[3] появилось первое описание криптосистемы RSA.[4] Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом:
- 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 бит, также известно как RSA-129) и e=9007. За расшифровку была обещана награда в 100 долларов США. По заявлению Ривеста, для факторизации числа потребовалось бы более 40 квадриллионов лет.[5][1] Однако чуть более чем через 15 лет, 3 сентября 1993 года было объявлено о старте проекта распределённых вычислений с координацией через электронную почту по нахождению сомножителей числа RSA-129 и решению головоломки. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (две из которых были факс-машинами). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE (англ.)» («Волшебные слова — это брезгливый ягнятник»).[6][7] Полученную награду победители пожертвовали в фонд свободного программного обеспечения.
После публикации Мартина Гарднера полное описание новой криптосистемы любой желающий мог получить, выслав по почте запрос Рональду Ривесту, с приложенным конвертом с обратным адресом и марками на 35 центов.[4] Полное описание новой криптосистемы было опубликовано в журнале «Communications of the ACM» в феврале 1978 года.[8]
Заявка на патент была подана 14 декабря 1977 года, в качестве владельца был указан MIT. Патент 4405829 был выдан 20 сентября 1983 года, а 21 сентября 2000 года срок его действия истёк.[9] Однако за пределами США у изобретателей патента на алгоритм не было, так как в большинстве стран его необходимо было получить до первой публикации.[10]
В 1982 году Ривест, Шамир и Адлеман организовали компанию [12]
В ноябре 1993 года открыто публикуется версия 1.5 стандарта RFC 3447 — 2.1, 2002 год).
В декабре 1997 года была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал криптосистему аналогичную RSA в 1973 году.[13]
Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:
Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.
В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования за разумное время (обратной операции) необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложения числа на простые множители.
В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:
RSA-ключи генерируются следующим образом:[14]
Предположим, Боб хочет послать Алисе сообщение .
Сообщениями являются целые числа в интервале от до , т.е .
Алгоритм:[14]
|
Алгоритм:
|
Наиболее используемым в настоящее время является смешанный алгоритм шифрования, в котором сначала шифруется сеансовый ключ, а потом уже с его помощью участники шифруют свои сообщения симметричными системами. После завершения сеанса сеансовый ключ как правило уничтожается.
Алгоритм шифрования сеансового ключа выглядит следующим образом[16]:
Алгоритм:
|
Алгоритм:
|
В случае, когда сеансовый ключ больше, чем модуль сеансовый ключ разбивают на блоки нужной длины (в случае необходимости дополняют нулями) и шифруют каждый блок.
Действительно, для
Покажем, что:
Возможны два случая:
Поскольку числа и являются взаимно обратными относительно умножения по модулю , т.e
тогда:
где второе тождество следует из теоремы Ферма.
тогда
Таким образом, при всех выполняется равенство
Аналогично можно показать, что:
Тогда, из китайской теоремы об остатках
Этап | Описание операции | Результат операции |
---|---|---|
Генерация ключей | Выбрать два простых различных числа |
|
Вычислить модуль (произведение) |
|
|
Вычислить функцию Эйлера |
|
|
Выбрать открытую экспоненту |
|
|
Вычислить секретную экспоненту |
|
|
Опубликовать открытый ключ |
|
|
Сохранить закрытый ключ |
|
|
Шифрование | Выбрать текст для зашифровки |
|
Вычислить шифротекст |
|
|
Расшифрование | Вычислить исходное сообщение |
|
Система RSA может использоваться не только для шифрования, но и для цифровой подписи.
Предположим, что Алисе (стороне ) нужно отправить Бобу (стороне ) сообщение , подтверждённое электронной цифровой подписью.
Алгоритм:
|
Алгоритм:
|
Поскольку цифровая подпись обеспечивает как аутентификацию автора сообщения, так и подтверждение целостности содержимого подписанного сообщения, она служит аналогом подписи, сделанной от руки в конце рукописного документа.
Важное свойство цифровой подписи заключается в том, что её может проверить каждый, кто имеет доступ к открытому ключу её автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись. Например, сторона может переслать стороне электронный чек. После того как сторона проверит подпись стороны на чеке, она может передать его в свой банк, служащие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию.
Заметим, что подписанное сообщение не зашифровано. Оно пересылается в исходном виде и его содержимое не защищено от нарушения конфиденциальности. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа[16]. Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.
Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью алгоритма быстрого возведения в степень. С использованием этого алгоритма для вычисления требуется операций умножения по модулю[17].
Т. к. каждое вычисление на шаге 2 требует не более трёх умножений по модулю и этот шаг выполняется раз, то сложность алгоритма может быть оценена величиной .
Чтобы проанализировать время выполнения операций с открытым и закрытым ключами, предположим, что открытый ключ и закрытый ключ удовлетворяют соотношениям , . Тогда в процессах их применения выполняется соответственно и умножений по модулю.
Таким образом время выполнения операций растёт с увеличением количества ненулевых битов в двоичном представлении открытой экспоненты e. Чтобы увеличить скорость шифрования, значение e часто выбирают равным 17, 257 или 65537 — простым числам, двоичное представление которых содержит лишь две единицы: 1710=100012, 25710=1000000012, 6553710=100000000000000012 (простые числа Ферма).
По эвристическим оценкам длина секретной экспоненты , нетривиальным образом зависящей от открытой экспоненты и модуля , с большой вероятностью близка к длине . Поэтому расшифрование данных идёт медленнее чем шифрование, а проверка подписи быстрее чем её создание.
Алгоритм RSA намного медленнее, чем AES и другие алгоритмы, использующие симметричные блочные шифры.
При расшифровании или подписывании сообщения в алгоритме RSA показатель вычисляемой степени будет довольно большим числом (порядка 1000 бит). Поэтому требуется алгоритм, сокращающий количество операций. Так как числа и в разложении известны зашифровывающему[известны владельцу закрытого ключа!], то можно вычислить:
Поскольку и — числа порядка на эти действия потребуется два потенцирования с показателем 512 знаков по модулю 512-битового числа. Это существенно[насколько?] быстрее, чем одно потенцирование с 1024-битовым показателем по модулю числа с 1024 двоичными знаками. Далее осталось восстановить по и что можно сделать с помощью китайской теоремы об остатках.[18]
Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования
Для вычисления по известным нужно найти такой , чтобы
то есть
Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение . Для вычисления функции Эйлера от известного числа необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — «потайной дверцей» (англ. backdoor), которая используется для вычисления владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, так называемой факторизации, самый быстрый из которых на сегодняшний день — общий метод решета числового поля, скорость которого для k-битного целого числа составляет
В 2010 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля.[20] По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года.[21]. С 31 декабря 2013 года браузеры Mozilla перестанут поддерживать сертификаты удостоверяющих центров с ключами RSA меньше 2048 бит[22].
Кроме того, при неправильной или неоптимальной реализации или использовании алгоритма возможны специальные криптографические атаки, такие как атаки на схемы с малой секретной экспонентой или на схемы с общим выбранным значением модуля.
В некоторых приложениях требуется ускорить процесс расшифровывания в алгоритме RSA. Поэтому выбирается небольшая расшифровывающая экспонента. В случае когда расшифровывающая экспонента можно определить за полиномиальное время с помощью атаки Винера,[18] опирающейся на непрерывные дроби.
при
Целые числа называются непрерывной дробью, представляющей а рациональные числа подходящими дробями. Каждая из подходящих дробей несократима, а скорость роста их знаменателей сравнима с показательной. Один из важных результатов теории непрерывных дробей:
то одна из подходящих дробей в разложении в непрерывную дробь.
Пусть у нас есть модуль причём Допустим нападающему известна шифрующая экспонента E, обладающая свойствомТак как очевидно Кроме того, так как предполагалось, что Значит,
Поскольку НОД то подходящая дробь в разложении дроби в непрерывную. Таким образом, можно узнать расшифровывающую экспоненту, поочерёдно подставляя знаменатели подходящих дробей в выражение:
для некоторого случайного числа Получив равенство, найдём Общее число подходящих дробей, которое придётся проверить оценивается как
Атака Винера, описанная выше, возможна лишь в том случае, когда атакующему известно о неравенстве
где — секретная экспонента, а — модуль RSA. Бонех и Дерфи, используя двумерный аналог теоремы Копперсмита (англ.), смогли обобщить атаку Винера[18] на случай, когда
Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи.
Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.
Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптостойкий генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам симметричный криптоалгоритм (в данное время широкое применение находят AES, IDEA, Serpent, Twofish).
Алгоритм RSA.