Криптоанализ RSA
- 1 year ago
- 0
- 0
RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом , основывающийся на вычислительной сложности задачи факторизации больших полупростых чисел .
Криптосистема RSA стала первой системой, пригодной и для шифрования , и для цифровой подписи . Алгоритм используется в большом числе криптографических приложений, включая PGP , S/MIME , TLS / SSL , IPSEC / IKE и других .
Алгоритм шифрования с открытым и закрытым ключом приписывается Уитфилду Диффи и Мартину Хеллману , которые опубликовали эту концепцию в 1976 году. Они также ввели цифровые подписи и попытались применить теорию чисел. В их формулировке использовался секретный ключ с общим доступом, созданный путем экспоненциализации некоторого числа, простого по модулю. Однако они оставили открытой проблему реализации односторонней функции, возможно, потому что сложность факторизации в то время не была хорошо изучена.
Рон Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института в течение года предприняли несколько попыток создать одностороннюю функцию, которую было бы трудно инвертировать. Ривест и Шамир, будучи компьютерными учеными, предложили множество потенциальных функций, а Адлеман, будучи математиком, отвечал за поиск их слабых мест. Они опробовали множество подходов, включая "ранцевый" и "перестановочные полиномы". Какое-то время они думали, что-то, чего они хотели достичь, невозможно из-за противоречивых требований. В апреле 1977 года они провели Песах в доме одного из студентов и выпили много манишевицкого вина, а затем вернулись к себе домой около полуночи. Ривест, не в силах заснуть, лег на диван с учебником математики и начал думать о своей односторонней функции. Остаток ночи он провел, формализуя свою идею, и к рассвету большая часть статьи была готова. Алгоритм теперь известен как RSA - инициалы их фамилий в том же порядке, что и в их статье.
Клиффорд Кокс, английский математик, работавший в британской разведывательной службе Government Communications Headquarters (GCHQ), описал эквивалентную систему во внутреннем документе в 1973 г. Однако, учитывая относительно дорогие компьютеры, необходимые для ее реализации в то время, она считалась в основном курьезом и, насколько известно, так и не была применена. Однако его открытие было раскрыто только в 1997 году из-за его сверхсильного засекречивания.
В августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American с разрешения Рональда Ривеста появилось первое описание криптосистемы RSA . Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом:
- 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 квадриллионов лет . Однако чуть более, чем через 15 лет, 3 сентября 1993 года , было объявлено о запуске проекта распределённых вычислений с координацией через электронную почту по нахождению сомножителей числа RSA-129 и решению головоломки. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (три из которых были факс-машинами [ источник не указан 2991 день ] ). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу « » («Волшебные слова — это брезгливый ягнятник ») . Полученную награду победители пожертвовали в фонд свободного программного обеспечения .
После публикации Мартина Гарднера полное описание новой криптосистемы любой желающий мог получить, выслав по почте запрос Рональду Ривесту с приложенным конвертом с обратным адресом и марками на 35 центов. Полное описание новой криптосистемы было опубликовано в журнале « Communications of the ACM » в феврале 1978 года .
Заявка на патент была подана 14 декабря 1977 года, в качестве владельца был указан MIT. Патент 4405829 был выдан 20 сентября 1983 года , а 21 сентября 2000 года срок его действия истёк . Однако за пределами США у изобретателей патента на алгоритм не было, так как в большинстве стран его необходимо было получить до первой публикации .
В 1982 году Ривест, Шамир и Адлеман организовали компанию (в настоящий момент — подразделение EMC ). В 1989 году RSA, вместе с симметричным шифром DES , упоминается в , тем самым начиная использование алгоритма в зарождающейся сети Internet , а в 1990 году использовать алгоритм начинает министерство обороны США .
В ноябре 1993 года открыто публикуется версия 1.5 стандарта , описывающего применение RSA для шифрования и создания электронной подписи. Последние версии стандарта также доступны в виде RFC ( — 1.5, 1993 год; — 2.0, 1998 год; — 2.1, 2002 год).
В декабре 1997 года была обнародована информация, согласно которой британский математик (Clifford Cocks), работавший в центре правительственной связи ( GCHQ ) Великобритании , описал криптосистему, аналогичную RSA в 1973 году .
Криптографические системы с открытым ключом используют так называемые односторонние функции , которые обладают следующим свойством:
Под односторонностью понимается не математически доказанная однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.
В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложение числа на простые множители.
В криптографической системе с открытым ключом каждый участник располагает как открытым ключом ( англ. public key ), так и закрытым ключом ( англ. private key ). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными , то есть:
RSA-ключи генерируются следующим образом :
Предположим, Боб хочет послать Алисе сообщение .
Сообщениями являются целые числа в интервале от до .
Алгоритм шифрования :
|
Алгоритм расшифрования :
|
Данная схема на практике не используется по причине того, что она не является практически надёжной (semantically secured). Действительно, односторонняя функция E(m) является детерминированной — при одних и тех же значениях входных параметров (ключа и сообщения) выдаёт одинаковый результат. Это значит, что не выполняется необходимое условие практической (семантической) надёжности шифра.
Более надёжным является смешанный алгоритм шифрования, в котором сначала шифруется сеансовый ключ, а потом уже с его помощью участники шифруют свои сообщения симметричными системами. После завершения сеанса сеансовый ключ, как правило, уничтожается.
Алгоритм шифрования сеансового ключа выглядит следующим образом :
Алгоритм :
|
Алгоритм :
|
В случае, когда сеансовый ключ больше, чем модуль , сеансовый ключ разбивают на блоки нужной длины (в случае необходимости дополняют нулями) и шифруют каждый блок.
Действительно, для
Покажем, что:
Возможны два случая:
Поскольку числа и являются взаимно обратными относительно умножения по модулю , т.e
тогда:
где второе тождество следует из теоремы Ферма .
тогда
Таким образом, при всех выполняется равенство
Аналогично можно показать, что:
Тогда, из китайской теоремы об остатках
Этап | Описание операции | Результат операции |
---|---|---|
Генерация ключей | Выбрать два простых различных числа |
|
Вычислить произведение |
|
|
Вычислить функцию Эйлера |
|
|
|
||
|
||
Опубликовать открытый ключ |
|
|
Сохранить закрытый ключ |
|
|
Шифрование | Выбрать текст для зашифрования |
|
Вычислить шифротекст |
|
|
Расшифрование | Вычислить исходное сообщение |
|
Система RSA может использоваться не только для шифрования, но и для цифровой подписи .
Предположим, что Алисе (стороне ) нужно отправить Бобу (стороне ) сообщение , подтверждённое электронной цифровой подписью .
Алгоритм :
|
Алгоритм :
|
Поскольку цифровая подпись обеспечивает как аутентификацию автора сообщения, так и подтверждение целостности содержимого подписанного сообщения, она служит аналогом подписи, сделанной от руки в конце рукописного документа.
Важное свойство цифровой подписи заключается в том, что её может проверить каждый, кто имеет доступ к открытому ключу её автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись. Например, сторона может переслать стороне электронный чек. После того как сторона проверит подпись стороны на чеке, она может передать его в свой банк, служащие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию.
Заметим, что подписанное сообщение не зашифровано . Оно пересылается в исходном виде и его содержимое не защищено от нарушения конфиденциальности. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа, принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа . Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.
Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью алгоритма быстрого возведения в степень . С использованием этого алгоритма для вычисления требуется операций умножения по модулю .
Т. к. каждое вычисление на шаге 2 требует не более трёх умножений по модулю и этот шаг выполняется раз, то сложность алгоритма может быть оценена величиной .
Чтобы проанализировать время выполнения операций с открытым и закрытым ключами, предположим, что открытый ключ и закрытый ключ удовлетворяют соотношениям , . Тогда в процессах их применения выполняется соответственно и умножений по модулю.
Таким образом время выполнения операций растёт с увеличением количества ненулевых битов в двоичном представлении открытой экспоненты e . Чтобы увеличить скорость шифрования, значение e часто выбирают равным 17, 257 или 65537 — простым числам , двоичное представление которых содержит лишь две единицы: 17 10 =10001 2 , 257 10 =100000001 2 , 65537 10 =10000000000000001 2 (простые числа Ферма ).
По эвристическим оценкам длина секретной экспоненты , нетривиальным образом зависящей от открытой экспоненты и модуля , с большой вероятностью близка к длине . Поэтому расшифрование данных идёт медленнее, чем шифрование, а проверка подписи – быстрее, чем её создание.
Алгоритм RSA намного медленнее, чем AES и другие алгоритмы, использующие симметричные блочные шифры .
При расшифровании или подписывании сообщения в алгоритме RSA показатель вычисляемой степени будет довольно большим числом (порядка 1000 бит). Поэтому требуется алгоритм, сокращающий количество операций. Так как числа и в разложении известны владельцу закрытого ключа, то можно вычислить:
Поскольку и — числа порядка на эти действия потребуется два возведения числа в 512-битовую степень по модулю 512-битового числа. Это существенно (для 1024 бит тестирование показало в 3 раза) быстрее, чем одно возведение в 1024-битовую степень по модулю 1024-битового числа. Далее осталось восстановить по и что можно сделать с помощью китайской теоремы об остатках .
Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования
Для вычисления по известным нужно найти такой , чтобы
то есть найти обратный элемент к в мультипликативной группе вычетов по модулю
Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение . Для вычисления функции Эйлера от известного числа необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — «потайной дверцей» ( англ. backdoor ), которая используется для вычисления владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, так называемой факторизации , самый быстрый из которых на сегодняшний день — общий метод решета числового поля , скорость которого для k-битного целого числа составляет
В 2010 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля . По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года . С 31 декабря 2013 года браузеры Mozilla перестали поддерживать сертификаты удостоверяющих центров с ключами RSA меньше 2048 бит .
Кроме того, при неправильной или неоптимальной реализации или использовании алгоритма возможны специальные криптографические атаки, такие как атаки на схемы с малой секретной экспонентой или на схемы с общим выбранным значением модуля.
В некоторых приложениях требуется ускорить процесс расшифровывания в алгоритме RSA. Поэтому выбирается небольшая расшифровывающая экспонента. В случае когда расшифровывающая экспонента можно определить за полиномиальное время с помощью атаки Винера , опирающейся на непрерывные дроби .
при
Целые числа
называются
непрерывной дробью
, представляющей
а рациональные числа
подходящими дробями. Каждая из подходящих дробей несократима, а скорость роста их знаменателей сравнима с показательной.
Один из важных результатов теории
непрерывных дробей
:
то одна из подходящих дробей в разложении в непрерывную дробь .
Пусть у нас есть модуль причём Допустим нападающему известна шифрующая экспонента E, обладающая свойством
Так как очевидно Кроме того, так как предполагалось, что Значит,
Поскольку НОД
то
подходящая дробь в разложении дроби
в
непрерывную
. Таким образом, можно узнать расшифровывающую экспоненту, поочерёдно подставляя знаменатели подходящих дробей в выражение:
для некоторого случайного числа Получив равенство, найдём Общее число подходящих дробей, которое придётся проверить оценивается как
Атака Винера
, описанная выше, возможна лишь в том случае, когда атакующему известно о неравенстве
где
— секретная экспонента, а
— модуль RSA.
Боне
и Дерфи, используя двумерный аналог
Теоремы Копперсмита
, смогли обобщить
атаку Винера
на случай, когда
Атака посредника не опасна если злоумышленник может только прослушивать канал связи по которому передаётся открытый ключ. В этом случаи злоумышленник сможет перехватить открытый ключ и зашифрованные сообщения, и подписи. Но при условии, что злоумышленник перехватил ключ и может отправлять сообщения по каналу связи. Злоумышленник может отправлять ложные сообщения.
Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи .
Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами .
Из-за низкой скорости шифрования сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным сеансовым ключом (например, AES , IDEA , Serpent , Twofish ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема . Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптографически стойкий генератор псевдослучайных чисел для формирования случайного сеансового ключа симметричного шифрования.