RSA (криптосистема) - RSA (cryptosystem)

ЮАР (Ривест – Шамир – Адлеман) это криптосистема с открытым ключом который широко используется для безопасной передачи данных. Это также один из старейших. В акроним ЮАР происходит от фамилии Рон Ривест, Ади Шамир, и Леонард Адлеман, который публично описал алгоритм в 1977 г. Эквивалентная система была разработана тайно в 1973 г. GCHQ (британский разведка сигналов агентство), английский математик Клиффорд Кокс. Эта система была рассекреченный в 1997 г.^[1]

В открытом ключе криптосистема, то ключ шифрования публично и отличается от ключ дешифрования, который хранится в секрете (закрытом). Пользователь RSA создает и публикует открытый ключ на основе двух больших простые числа, вместе со вспомогательным значением. Простые числа держатся в секрете. Сообщения могут быть зашифрованы с помощью открытого ключа, но могут быть декодированы только тем, кто знает простые числа.^[2]

Безопасность RSA зависит от практических трудностей факторинг произведение двух больших простые числа, "проблема факторинга ". Нарушение RSA шифрование известен как Проблема RSA. Будь это так сложно, как проблема факторинга это открытый вопрос.^[3] Нет опубликованных методов для выхода из строя системы, если используется достаточно большой ключ.

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

История

Ади Шамир, соавтор ЮАР (остальные Рон Ривест и Леонард Адлеман )

Идея асимметричной криптосистемы с открытым и закрытым ключом принадлежит Уитфилд Диффи и Мартин Хеллман, который опубликовал эту концепцию в 1976 году. Они также ввели цифровые подписи и попытались применить теорию чисел. В их формулировке использовался общий секретный ключ, созданный путем возведения в степень некоторого числа по модулю простого числа. Однако они оставили открытой проблему реализации односторонней функции, возможно, потому, что сложность факторизации в то время не была хорошо изучена.^[4]

Рон Ривест, Ади Шамир, и Леонард Адлеман на Массачусетский Институт Технологий, сделал несколько попыток в течение года создать одностороннюю функцию, которую было трудно инвертировать. Ривест и Шамир, как компьютерщики, предложили множество потенциальных функций, а Адлеман, как математик, отвечал за обнаружение их слабых мест. Они испробовали множество подходов, включая "рюкзак на основе "и" многочленов с перестановками ". Какое-то время они думали, что то, чего они хотели достичь, было невозможно из-за противоречивых требований.^[5] В апреле 1977 года они провели Пасха в доме студента и выпил много Манишевиц вино перед возвращением домой около полуночи.^[6] Ривест, не сумев заснуть, лег на диван с учебником математики и начал думать об их односторонней функции. Он провел остаток ночи, формулируя свою идею, и к рассвету у него была готова большая часть бумаги. Алгоритм теперь известен как RSA - инициалы их фамилий в том же порядке, что и их бумага.^[7]

Клиффорд Кокс, английский математик работая на Британский спецслужба Штаб правительственной связи (GCHQ) описал эквивалентную систему во внутреннем документе в 1973 году.^[8] Однако, учитывая относительно дорогие компьютеры, необходимые для его реализации в то время, это считалось в основном диковинкой и, насколько известно, никогда не применялось. Однако его открытие не было раскрыто до 1997 года из-за его сверхсекретной классификации.

Kid-RSA (KRSA) - это упрощенный шифр с открытым ключом, опубликованный в 1997 году и предназначенный для образовательных целей. Некоторые люди считают, что изучение Kid-RSA дает представление о RSA и других шифрах с открытым ключом, аналогично упрощенный DES.^{[9][10][11][12][13]}

Патент

А патент описание алгоритма RSA было предоставлено Массачусетский технологический институт 20 сентября 1983 г .: Патент США 4,405,829 «Система и метод криптографической связи». Из DWPI Резюме патента:

Система включает в себя канал связи, подключенный по меньшей мере к одному терминалу, имеющему устройство кодирования, и по меньшей мере к одному терминалу, имеющему устройство декодирования. Сообщение, которое должно быть передано, зашифровывается в зашифрованный текст на кодирующем терминале путем кодирования сообщения как числа M в заранее определенном наборе. Затем это число увеличивается до первой заданной мощности (связанной с предполагаемым приемником) и, наконец, вычисляется. Остаток или остаток C ... вычисляется, когда возведенное в степень число делится на произведение двух предопределенных простых чисел (связанных с предполагаемым получателем).

Подробное описание алгоритма было опубликовано в августе 1977 г. в Scientific American с Математические игры столбец.^[7] Это предшествовало дате подачи патента в декабре 1977 года. Следовательно, патент не имел юридической силы за пределами Соединенные Штаты. Если бы работа Кокса была широко известна, патент в Соединенных Штатах также не был бы законным.

Когда был выдан патент, условия патента были 17 лет. Срок действия патента истекал 21 сентября 2000 г., когда RSA Безопасность передал алгоритм в общественное достояние 6 сентября 2000 г.^[14]

Операция

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

Основным принципом RSA является наблюдение, что на практике можно найти три очень больших положительных целых числа. е, d, и п, так что с модульное возведение в степень для всех целых чисел м (с 0 ≤ м < п):

${displaystyle (m ^ {e}) ^ {d} Equiv m {pmod {n}}}$

и это знание е и п, или даже м, найти d. В тройной бар (≡) здесь означает модульное соответствие.

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

${displaystyle (m ^ {d}) ^ {e} Equiv m {pmod {n}}}$

RSA включает открытый ключ и закрытый ключ. Открытый ключ может быть известен каждому, и он используется для шифрования сообщений. Предполагается, что сообщения, зашифрованные с помощью открытого ключа, могут быть дешифрованы только за разумное время с использованием закрытого ключа. Открытый ключ представлен целыми числами п и е; а закрытый ключ - целым числом d (несмотря на то что п также используется в процессе дешифрования, поэтому его также можно рассматривать как часть закрытого ключа). м представляет собой сообщение (предварительно подготовленное с использованием определенной техники, описанной ниже).

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

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

1. Выберите два разных простые числа п и q.
   • В целях безопасности целые числа п и q должны выбираться случайным образом и должны быть одинаковыми по величине, но отличаться по длине на несколько цифр, чтобы затруднить факторинг.^[2] Простые целые числа можно эффективно найти с помощью тест на простоту.
   • п и q держатся в секрете.
2. Вычислить п = pq.
   • п используется как модуль как для открытого, так и для закрытого ключей. Его длина, обычно выражаемая в битах, является длина ключа.
   • п выпускается как часть открытого ключа.
3. Вычислить λ(п), куда λ является Тотальная функция Кармайкла. С п = pq, λ(п) = lcm (λ(п),λ(q)), и с тех пор п и q простые, λ(п) = φ (п) = п - 1 и аналогично λ(q) = q - 1. Следовательно λ(п) = lcm (п − 1, q − 1).
   • λ(п) держится в секрете.
   • Lcm можно рассчитать через Евклидов алгоритм, поскольку lcm (а,б) = | ab |/ gcd (а,б).
4. Выберите целое число е такой, что 1 < е < λ(п) и gcd (е, λ(п)) = 1; то есть, е и λ(п) находятся совмещать.
   • е имея короткий битовая длина и маленький Вес Хэмминга приводит к более эффективному шифрованию - наиболее часто выбираемое значение для е является 2¹⁶ + 1 = 65,537. Наименьшее (и самое быстрое) возможное значение для е равно 3, но такое маленькое значение для е было показано, что в некоторых настройках он менее безопасен.^[15]
   • е выпускается как часть открытого ключа.
5. Определять d в качестве d ≡ е⁻¹ (мод λ(п)); то есть, d это модульный мультипликативный обратный из е по модулю λ(п).
   • Это означает: решить для d уравнение d⋅е ≡ 1 (мод λ(п)); d можно эффективно вычислить с помощью Расширенный алгоритм Евклида, поскольку, благодаря е и λ(п) будучи взаимно простыми, указанное уравнение является формой Личность Безу, куда d является одним из коэффициентов.
   • d держится в секрете как показатель закрытого ключа.

В открытый ключ состоит из модуля п и публичная (или шифрованная) экспонента е. В закрытый ключ состоит из частного (или дешифрования) показателя d, который необходимо держать в секрете. п, q, и λ(п) также должны храниться в секрете, потому что их можно использовать для вычисления d. Фактически, все они могут быть выброшены после d был вычислен.^[16]

В исходной статье RSA^[2] то Функция Эйлера φ(п) = (п − 1)(q − 1) используется вместо λ(п) для вычисления частного показателя d. С φ(п) всегда делится на λ(п) алгоритм тоже работает. Что Функция Эйлера может также рассматриваться как следствие Теорема Лагранжа применяется к мультипликативная группа целых чисел по модулю pq. Таким образом, любой d удовлетворение d⋅е ≡ 1 (мод φ(п)) также удовлетворяет d⋅е ≡ 1 (мод λ(п)). Однако вычисления d по модулю φ(п) иногда дает результат больше, чем необходимо (т.е. d > λ(п)). Большинство реализаций RSA будут принимать экспоненты, созданные с использованием любого метода (если они используют частный показатель d вообще, вместо использования оптимизированного метода дешифрования на основе китайской теоремы об остатках описано ниже), но некоторые стандарты, такие как FIPS 186-4 может потребовать, чтобы d < λ(п). Любые «негабаритные» частные экспоненты, не соответствующие этому критерию, всегда могут быть сокращены по модулю λ(п), чтобы получить меньшую эквивалентную экспоненту.

Поскольку любые общие факторы (п − 1) и (q − 1) присутствуют в факторизации п − 1 = pq − 1 = (п − 1)(q − 1) + (п − 1) + (q − 1),^[17] рекомендуется, чтобы (п − 1) и (q − 1) имеют только очень маленькие общие факторы, если таковые имеются, помимо необходимых 2.^{[2][18][19][20]}

Примечание: авторы оригинальной статьи RSA выполняют генерацию ключа, выбирая d а затем вычисление е как модульный мультипликативный обратный из d по модулю φ(п), тогда как большинство текущих реализаций RSA, таких как следующие PKCS # 1, сделайте обратное (выберите е и вычислить d). Поскольку выбранный ключ может быть небольшим, тогда как вычисляемый ключ обычно не является, алгоритм документа RSA оптимизирует дешифрование по сравнению с шифрованием, в то время как современный алгоритм оптимизирует шифрование.^[2][21]

Распределение ключей

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

Чтобы Боб мог отправлять свои зашифрованные сообщения, Алиса передает свой открытый ключ (п, е) к Бобу по надежному, но не обязательно секретному маршруту. Закрытый ключ Алисы (d) никогда не распространяется.

Шифрование

После того, как Боб получит открытый ключ Алисы, он может отправить сообщение M Алисе.

Для этого он сначала обращается M (строго говоря, незаполненный открытый текст) в целое число м (строго говоря, дополненный открытый текст), так что 0 ≤ м < п с помощью согласованного обратимого протокола, известного как схема заполнения. Затем он вычисляет зашифрованный текст c, используя открытый ключ Алисы е, соответствующий

${displaystyle m ^ {e} Equiv c {pmod {n}}}$

Это можно сделать достаточно быстро даже для очень больших чисел, используя модульное возведение в степень. Затем Боб передает c Алисе.

Расшифровка

Алиса может поправиться м из c используя ее показатель закрытого ключа d вычисляя

${displaystyle c ^ {d} эквив (м ^ {е}) ^ {d} экв м {пмод {п}}}$

Данный м, она может восстановить исходное сообщение M путем изменения схемы заполнения.

Пример

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

1. Выберите два различных простых числа, например

   ${displaystyle p = 61}$ и ${displaystyle q = 53}$

2. Вычислить п = pq давая

   ${displaystyle n = 61 imes 53 = 3233}$

3. Вычислить Тотальная функция Кармайкла продукта как λ(п) = lcm (п − 1, q − 1) давая

   ${displaystyle lambda (3233) = operatorname {lcm} (60,52) = 780}$

4. Выберите любой номер 1 < е < 780 то есть совмещать на 780. Выбор простого числа для е оставляет нам только проверить это е не является делителем 780.

   Позволять ${displaystyle e = 17}$

5. Вычислить d, то модульный мультипликативный обратный из е (мод λ(п)) уступая,

   ${displaystyle d = 413}$

   Рабочий пример для модульного мультипликативного обратного:

   ${displaystyle d imes e = 1 {mod {lambda}} (n)}$

   ${displaystyle 413 imes 17 = 1 {mod {7}} 80}$

В открытый ключ является (п = 3233, е = 17). Для мягкого простой текст сообщение м, функция шифрования

${displaystyle c (m) = m ^ {17} {mod {3}} 233}$

В закрытый ключ является (п = 3233, d = 413). Для зашифрованного зашифрованный текст c, функция дешифрования

${displaystyle m (c) = c ^ {413} {mod {3}} 233}$

Например, чтобы зашифровать м = 65, мы рассчитываем

${displaystyle c = 65 ^ {17} {mod {3}} 233 = 2790}$

Расшифровать c = 2790, мы рассчитываем

${displaystyle m = 2790 ^ {413} {mod {3}} 233 = 65}$

Оба эти вычисления могут быть эффективно вычислены с использованием алгоритм квадратного и умножения за модульное возведение в степень. В реальных жизненных ситуациях выбранные простые числа будут намного больше; в нашем примере было бы тривиально разложить на множители п, 3233 (полученный из свободно доступного открытого ключа) обратно к простым числам п и q. е, также из открытого ключа, затем инвертируется, чтобы получить d, таким образом получив закрытый ключ.

Практические реализации используют Китайская теорема об остатках для ускорения расчета с использованием модуля факторов (mod pq используя мод п и мод q).

Ценности d_п, d_q и q_inv, которые являются частью закрытого ключа, вычисляются следующим образом:

${displaystyle {egin {align} d_ {p} = {} & d {mod {(}} p-1) = 413 {mod {(}} 61-1) = 53 d_ {q} = {} & d {mod {(}} q-1) = 413 {mod {(}} 53-1) = 49 q_ {ext {inv}} = {} & q ^ {- 1} {mod {p}} = 53 ^ {- 1} {mod {6}} 1 = 38 Rightarrow {} & (q_ {ext {inv}} imes q) {mod {p}} = 38 imes 53 {mod {6}} 1 = 1end {выровнено}} }$

Вот как d_п, d_q и q_inv используются для эффективного дешифрования. (Шифрование эффективно при выборе подходящего d и е пара)

${displaystyle {egin {align} m_ {1} & = c ^ {d_ {p}} {mod {p}} = 2790 ^ {53} {mod {6}} 1 = 4 m_ {2} & = c ^ {d_ {q}} {mod {q}} = 2790 ^ {49} {mod {5}} 3 = 12 h & = (q_ {ext {inv}} время (m_ {1} -m_ {2} )) {mod {p}} = (38 imes -8) {mod {6}} 1 = 1 m & = m_ {2} + h imes q = 12 + 1 imes 53 = 65end {выровнено}}}$

Подписание сообщений

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

Предположим, Алиса хочет отправить Бобу подписанное сообщение. Для этого она может использовать свой закрытый ключ. Она производит хеш-значение сообщения, возводит его в степень d (по модулю п) (как она это делает при расшифровке сообщения) и прикрепляет ее как «подпись» к сообщению. Когда Боб получает подписанное сообщение, он использует тот же алгоритм хеширования в сочетании с открытым ключом Алисы. Он поднимает подпись во власть е (по модулю п) (как он это делает при шифровании сообщения) и сравнивает полученное хеш-значение с хеш-значением сообщения. Если они согласны, он знает, что автор сообщения владел закрытым ключом Алисы и что сообщение не подвергалось подделке с момента его отправки.

Это работает из-за возведение в степень правила:

${displaystyle h = {ext {hash}} (m);}$

${displaystyle (h ^ {e}) ^ {d} = h ^ {ed} = h ^ {de} = (h ^ {d}) ^ {e} Equiv h {pmod {n}}}$

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

1. Расшифровать сообщение, предназначенное только для получателя, которое может быть зашифровано любым, у кого есть открытый ключ (асимметричный зашифрованный транспорт).
2. Зашифровать сообщение, которое может быть расшифровано кем угодно, но которое может быть зашифровано только одним человеком; это обеспечивает цифровую подпись.

Доказательства правильности

Доказательство с помощью малой теоремы Ферма.

Доказательство правильности RSA основано на Маленькая теорема Ферма, заявив, что а^{п − 1} ≡ 1 (мод п) для любого целого а и премьер п, не деля а.

Мы хотим показать, что

${displaystyle (m ^ {e}) ^ {d} Equiv m {pmod {pq}}}$

для каждого целого числа м когда п и q различные простые числа и е и d натуральные числа, удовлетворяющие ред ≡ 1 (мод λ(pq)).

С λ(pq) = lcm (п − 1, q − 1) по построению делится на оба п − 1 и q − 1, мы можем написать

${displaystyle ed-1 = h (p-1) = k (q-1)}$

для некоторых неотрицательных целых чисел час и k.^{[примечание 1]}

Чтобы проверить, есть ли два числа, например м^ред и м, совпадают модpq, достаточно (и фактически эквивалентно) проверить, что они конгруэнтны по модулюп и модq раздельно. ^{[заметка 2]}

Показывать м^ред ≡ м (мод п), мы рассматриваем два случая:

1. Если м ≡ 0 (мод п), м кратно п. Таким образом м^ред кратно п. Так м^ред ≡ 0 ≡ м (мод п).
2. Если м ${displaystyle ot Equiv}$ 0 (мод п),

${displaystyle m ^ {ed} = m ^ {ed-1} m = m ^ {h (p-1)} m = (m ^ {p-1}) ^ {h} mequiv 1 ^ {h} mequiv m {pmod {p}},}$

где мы использовали Маленькая теорема Ферма заменить м^п−1 мод п с 1.

Подтверждение того, что м^ред ≡ м (мод q) происходит совершенно аналогично:

1. Если м ≡ 0 (мод q), м^ред кратно q. Так м^ред ≡ 0 ≡ м (мод q).
2. Если м ${displaystyle ot Equiv}$ 0 (мод q),

${displaystyle m ^ {ed} = m ^ {ed-1} m = m ^ {k (q-1)} m = (m ^ {q-1}) ^ {k} mequiv 1 ^ {k} mequiv m {pmod {q}}.}$

Это завершает доказательство того, что для любого целого числа м, и целые числа е, d такой, что ред ≡ 1 (мод λ(pq)),

${displaystyle (m ^ {e}) ^ {d} Equiv m {pmod {pq}}.}$

Примечания:

Доказательство с использованием теоремы Эйлера.

Хотя в оригинальной статье Ривеста, Шамира и Адлемана для объяснения того, почему работает RSA, использовалась небольшая теорема Ферма, обычно можно найти доказательства, которые вместо этого полагаются на Теорема Эйлера.

Мы хотим показать, что м^ред ≡ м (мод п), куда п = pq является произведением двух разных простых чисел и е и d натуральные числа, удовлетворяющие ред ≡ 1 (мод φ(п)). С е и d положительные, мы можем написать ред = 1 + hφ(п) для некоторого неотрицательного целого числа час. Предполагая который м относительно проста с п, у нас есть

${displaystyle m ^ {ed} = m ^ {1 + hvarphi (n)} = m (m ^ {varphi (n)}) ^ {h} эквивалент m (1) ^ {h} эквив m {pmod {n} }}$

где предпоследнее сравнение следует из Теорема Эйлера.

В общем, для любого е и d удовлетворение ред ≡ 1 (мод λ(п)), такой же вывод следует из Кармайкл обобщение теоремы Эйлера, в котором говорится, что м^λ(п) ≡ 1 (мод п) для всех м относительно простой п.

Когда м не является относительно простым п, только что приведенный аргумент недействителен. Это маловероятно (только часть 1/п + 1/q − 1/(pq) числа обладают этим свойством), но даже в этом случае желаемое совпадение остается верным. Либо м ≡ 0 (мод п) или же м ≡ 0 (мод q), и эти случаи можно рассмотреть, используя предыдущее доказательство.

Прокладка

Атаки на простой RSA

Существует ряд атак на простой RSA, как описано ниже.

• При шифровании с низкими показателями шифрования (например, е = 3) и малые значения м, (т.е. м < п^1/е) результат м^е строго меньше модуля п. В этом случае зашифрованные тексты можно легко расшифровать, взяв екорень зашифрованного текста над целыми числами.
• Если такое же текстовое сообщение отправлено на е или более получателей в зашифрованном виде, и получатели имеют одинаковый показатель степени е, но разные п, q, и поэтому п, то исходное текстовое сообщение легко расшифровать с помощью Китайская теорема об остатках. Йохан Хастад заметил, что эта атака возможна, даже если чистые тексты не равны, но злоумышленник знает линейную связь между ними.^[22] Позднее эта атака была улучшена Дон Копперсмит (видеть Атака медника ).^[23]
• Поскольку шифрование RSA - это детерминированный алгоритм шифрования (т.е. не имеет случайного компонента) злоумышленник может успешно запустить атака по выбранному открытому тексту против криптосистемы, шифруя вероятные открытые тексты под открытым ключом и проверяя, равны ли они зашифрованному тексту. Криптосистема называется семантически безопасный если злоумышленник не может отличить два шифрования друг от друга, даже если злоумышленник знает (или выбрал) соответствующие открытые тексты. Как описано выше, RSA без заполнения не является семантически безопасным.^[24]
• RSA обладает тем свойством, что продукт двух зашифрованных текстов равен шифрованию продукта соответствующих открытых текстов. То есть м₁^ем₂^е ≡ (м₁м₂)^е (мод п). Из-за этого мультипликативного свойства a атака по выбранному зашифрованному тексту возможно. Например, злоумышленник, который хочет узнать расшифровку зашифрованного текста. c ≡ м^е (мод п) может спросить у держателя приватного ключа d расшифровать ничего не подозревающий зашифрованный текст c′ ≡ cr^е (мод п) за некоторую ценность р выбран злоумышленником. Из-за мультипликативного свойства c′ - это шифрование Мистер (мод п). Следовательно, если злоумышленник успешно проведет атаку, он узнает Мистер (мод п) из которого они могут извлечь сообщение м путем умножения Мистер с модульной инверсией р по модулю п.^{[нужна цитата ]}
• Учитывая частную экспоненту d можно эффективно разложить модуль п = pq. И учитывая факторизацию модуля п = pq, можно получить любой закрытый ключ (d ', n) генерируется с открытым ключом (е ', п).^[15]

Схемы заполнения

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

Такие стандарты как PKCS # 1 были тщательно разработаны для безопасного заполнения сообщений до шифрования RSA. Поскольку эти схемы дополняют открытый текст м с некоторым количеством дополнительных битов размер незаполненного сообщения M должно быть несколько меньше. Схемы заполнения RSA должны быть тщательно разработаны, чтобы предотвратить изощренные атаки, которым может способствовать предсказуемая структура сообщения. Ранние версии стандарта PKCS # 1 (до версии 1.5) использовали конструкцию, которая, по-видимому, делала RSA семантически безопасным. Однако на Крипто 1998 г. Блейхенбахер показал, что эта версия уязвима для практических адаптивная атака по выбранному зашифрованному тексту. Кроме того, на Еврокрипт 2000, Coron et al.^{[нужна цитата ]} показал, что для некоторых типов сообщений это заполнение не обеспечивает достаточно высокого уровня безопасности. Более поздние версии стандарта включают Оптимальное заполнение асимметричным шифрованием (OAEP), который предотвращает эти атаки. Таким образом, OAEP следует использовать в любом новом приложении, а заполнение PKCS # 1 v1.5 следует заменять везде, где это возможно. Стандарт PKCS # 1 также включает схемы обработки, предназначенные для обеспечения дополнительной безопасности для подписей RSA, например Схема вероятностной подписи для RSA (RSA-PSS ).

Схемы безопасного заполнения, такие как RSA-PSS, столь же важны для безопасности подписи сообщений, как и для шифрования сообщений. Были выданы два патента США на PSS (USPTO 6266771 и USPTO 70360140); однако срок действия этих патентов истек 24 июля 2009 г. и 25 апреля 2010 г. соответственно. Использование PSS больше не ограничивается патентами.^{[оригинальное исследование? ]} Обратите внимание, что использование разных пар ключей RSA для шифрования и подписи потенциально более безопасно.^[25]

Безопасность и практические соображения

Использование китайского алгоритма остатка

Для повышения эффективности многие популярные криптографические библиотеки (например, OpenSSL, Ява и .СЕТЬ ) используйте следующую оптимизацию для расшифровки и подписи на основе Китайская теорема об остатках. Следующие значения предварительно вычисляются и сохраняются как часть закрытого ключа:

• ${displaystyle p}$ и ${displaystyle q}$: простые числа из ключевого поколения,
• ${displaystyle d_ {P} = d {pmod {p-1}}}$,
• ${displaystyle d_ {Q} = d {pmod {q-1}}}$ и
• ${displaystyle q_ {ext {inv}} = q ^ {- 1} {pmod {p}}}$.

Эти значения позволяют получателю вычислить возведение в степень. м = c^d (мод pq) более эффективно следующим образом:

• ${displaystyle m_ {1} = c ^ {d_ {P}} {pmod {p}}}$
• ${displaystyle m_ {2} = c ^ {d_ {Q}} {pmod {q}}}$
• ${displaystyle h = q_ {ext {inv}} (m_ {1} -m_ {2}) {pmod {p}}}$ (если ${displaystyle m_ {1}$ затем некоторые^{[требуется разъяснение ]} библиотеки вычисляют час в качестве ${displaystyle q_ {ext {inv}} left [left (m_ {1} + leftlceil {frac {q} {p}} ightceil pight) -m_ {2} ight] {pmod {p}}}$)
• ${displaystyle m = m_ {2} + hq, {pmod {p * q}}}$

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

Целочисленная факторизация и проблема RSA

Безопасность криптосистемы RSA основана на двух математических задачах: проблеме факторинг больших чисел и Проблема RSA. Считается, что полное дешифрование зашифрованного текста RSA невозможно, если предположить, что обе эти проблемы являются сложными, т. Е. Не существует эффективного алгоритма для их решения. Обеспечение защиты от частичный расшифровка может потребовать добавления безопасного схема заполнения.^[26]

В Проблема RSA определяется как задача взять екорни th по модулю составного п: восстановление значения м такой, что c ≡ м^е (мод п), куда (п, е) является открытым ключом RSA и c представляет собой зашифрованный текст RSA. В настоящее время наиболее многообещающим подходом к решению проблемы RSA является фактор модуля п. Имея возможность восстанавливать простые множители, злоумышленник может вычислить секретную экспоненту d из открытого ключа (п, е), затем расшифровать c используя стандартную процедуру. Для этого атакующий факторы п в п и q, и вычисляет lcm (п − 1, q − 1) что позволяет определить d из е. Полиномиального метода факторизации больших целых чисел на классическом компьютере еще не было найдено, но не было доказано, что его не существует. Видеть целочисленная факторизация для обсуждения этой проблемы.

Множественное полиномиальное квадратичное сито (MPQS) может использоваться для определения общедоступного модуля упругости. п.

Первая факторизация RSA-512 в 1999 г. использовала сотни компьютеров и потребовала 8 400 операций в секунду в год за время примерно в семь месяцев.^[27] К 2009 году Бенджамин Муди мог разложить ключ RSA-512 бит за 73 дня, используя только общедоступное программное обеспечение (GGNFS) и свой настольный компьютер (двухъядерный Athlon64 с процессором 1900 МГц). Для процесса просеивания требовалось чуть менее пяти гигабайт дискового пространства и около 2,5 гигабайт оперативной памяти.

Ривест, Шамир и Адлеман отметили ^[2] что Миллер показал это - если допустить истинность Расширенная гипотеза Римана - находка d из п и е так же сложно, как факторинг п в п и q (с точностью до полиномиальной разницы во времени).^[28] Однако Ривест, Шамир и Адлеман отметили в разделе IX / D своей статьи, что они не нашли доказательства того, что инвертирование RSA так же сложно, как разложение на множители.

По состоянию на 2020 год^{[Обновить]}, крупнейший общеизвестный факторный Номер RSA было 829 бит (250 десятичных цифр, РСА-250 ).^[29] Его факторизация с помощью современной распределенной реализации заняла около 2700 процессорных лет. На практике ключи RSA обычно имеют длину от 1024 до 4096 бит. RSA Безопасность думал, что к 2010 году 1024-битные ключи, скорее всего, станут взломанными,^[30]; по состоянию на 2020 год неизвестно, было ли это так, но минимальные рекомендации переместились как минимум на 2048 бит.^[31] Обычно предполагается, что RSA безопасен, если п достаточно велик, за пределами квантовых вычислений.

Если п 300 биты или короче, его можно учесть за несколько часов в персональный компьютер, используя программное обеспечение, уже имеющееся в свободном доступе. Ключи на 512 бит оказались практически взламываемыми в 1999 году, когда RSA-155 был факторизован с использованием нескольких сотен компьютеров, а сейчас они разложены за несколько недель с использованием обычного оборудования. В 2011 г. сообщалось об эксплойтах с использованием 512-битных сертификатов для подписи кода, которые могли быть учтены.^[32] Теоретическое аппаратное устройство под названием TWIRL, описанный Шамиром и Тромером в 2003 году, поставил под сомнение безопасность 1024-битных ключей.^[30]

В 1994 г. Петр Шор показал, что квантовый компьютер - если бы его можно было практически создать для этой цели - можно было бы учитывать полиномиальное время, нарушая RSA; видеть Алгоритм Шора.

Неправильная генерация ключей

Эта секция нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: Криптосистема "RSA"  – Новости  · газеты  · книги  · ученый  · JSTOR (Октябрь 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Нахождение больших простых чисел п и q обычно выполняется путем проверки случайных чисел правильного размера с помощью вероятностных тесты на простоту которые быстро устраняют практически все непростые позиции.

Цифры п и q не должно быть "слишком близко", иначе Факторизация Ферма за п быть успешным. Если п − q меньше 2п^1/4 (п = п * q, что даже для небольших 1024-битных значений п является 3×10⁷⁷) решение для п и q тривиально. Кроме того, если либо п - 1 или q - 1 имеет только малые простые множители, п можно быстро учесть Алгоритм Полларда p - 1, и такие значения п или же q следовательно, следует отказаться.

Важно, чтобы частный показатель d быть достаточно большим. Майкл Дж. Винер показал, что если п между q и 2q (что вполне типично) и d < п^1/4/3, тогда d можно эффективно вычислить из п ие.^[33]

Нет известных атак на мелких публичных представителей, таких как е = 3при условии, что используется правильный отступ. Атака медника имеет множество применений в атаке RSA, особенно если публичный показатель е является небольшим, и если зашифрованное сообщение короткое и не заполнено. 65537 это часто используемое значение дляе; это значение можно рассматривать как компромисс между предотвращением потенциальных атак с малой степенью экспоненты и возможностью эффективного шифрования (или проверки подписи). Специальная публикация NIST по компьютерной безопасности (SP 800-78 Ред. 1 от августа 2007 г.) не разрешает публичные экспоненты е меньше 65537, но не указывает причину этого ограничения.

В октябре 2017 года группа исследователей из Масариковский университет объявил о ROCA уязвимость, который влияет на ключи RSA, сгенерированные алгоритмом, реализованным в библиотеке из Infineon известный как RSALib. Большое количество смарт-карт и доверенные платформенные модули (TPM) были показаны затронутые. Уязвимые ключи RSA легко идентифицировать с помощью тестовой программы, выпущенной командой.^[34]

Важность сильной генерации случайных чисел

Криптографически сильный генератор случайных чисел, который был должным образом засеян адекватной энтропией, должен использоваться для генерации простых чисел п и q. Анализ, сравнивающий миллионы открытых ключей, собранных из Интернета, был проведен в начале 2012 г. Арьен К. Ленстра, Джеймс П. Хьюз, Максим Ожье, Йопп В. Бос, Торстен Кляйнджунг и Кристоф Вахтер. Они смогли разложить 0,2% ключей, используя только алгоритм Евклида.^[35][36]

Они использовали уникальную уязвимость криптосистем, основанную на целочисленной факторизации. Если п = pq это один открытый ключ и п′ = п′q′ это другой, то если случайно п = п′ (но q не равно q′), То простое вычисление gcd (п,п′) = п факторы как п и п′, Полностью скомпрометировав оба ключа. Lenstra et al. обратите внимание, что эту проблему можно минимизировать, используя сильное случайное начальное число битовой длины, вдвое превышающей предполагаемый уровень безопасности, или используя детерминированную функцию для выбора q данный пвместо выбора п и q независимо.

Надя Хенингер был частью группы, проводившей аналогичный эксперимент. Они использовали идею Дэниел Дж. Бернштейн для вычисления GCD каждого ключа RSA п против продукта всех других ключей п'Они нашли (число из 729 миллионов цифр), вместо того, чтобы вычислять каждый НОД (п,п′) По отдельности, благодаря чему достигается очень значительное ускорение, поскольку после одного большого деления проблема GCD становится нормального размера.

Хенингер говорит в своем блоге, что плохие ключи почти полностью возникли во встроенных приложениях, включая «межсетевые экраны, маршрутизаторы, устройства VPN, устройства удаленного администрирования серверов, принтеры, проекторы и телефоны VOIP» от более чем 30 производителей. Хенингер объясняет, что проблема одного общего простого числа, обнаруженная двумя группами, является результатом ситуаций, когда генератор псевдослучайных чисел изначально плохо загружается, а затем повторно заполняется между генерацией первого и второго простых чисел. Использование затравок с достаточно высокой энтропией, полученных из таймингов клавиш или шума электронных диодов или атмосферный шум от радиоприемника, настроенного между станциями, должно решить проблему.^[37]

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

Время атаки

Кохер описал новую атаку на RSA в 1995 году: если злоумышленник Ева знает оборудование Алисы достаточно подробно и может измерить время дешифрования для нескольких известных шифрованных текстов, Ева может определить ключ дешифрования. d быстро. Эта атака также может быть применена против схемы подписи RSA. В 2003 г. Boneh и Брамли продемонстрировали более практичную атаку, способную восстанавливать факторизации RSA через сетевое соединение (например, из Уровень защищенных гнезд Веб-сервер с поддержкой (SSL))^[38] Эта атака использует информацию, просочившуюся Китайская теорема об остатках оптимизация, используемая во многих реализациях RSA.

Один из способов предотвратить эти атаки - обеспечить, чтобы операция дешифрования занимала постоянное количество времени для каждого зашифрованного текста. Однако такой подход может значительно снизить производительность. Вместо этого в большинстве реализаций RSA используется альтернативный метод, известный как криптографическая слепота. Ослепление RSA использует мультипликативное свойство RSA. Вместо вычислений c^d (мод п), Алиса сначала выбирает секретное случайное значение р и вычисляет (р^еc)^d (мод п). Результат этого вычисления после применения Теорема Эйлера, является rc^d (мод п) и так эффект р можно удалить, умножив на обратное. Новое значение р выбирается для каждого зашифрованного текста. При применении ослепления время дешифрования больше не коррелирует со значением входного зашифрованного текста, и поэтому временная атака терпит неудачу.

Адаптивные атаки по выбранному зашифрованному тексту

В 1998 г. Даниэль Блейхенбахер описал первый практический адаптивная атака по выбранному зашифрованному тексту против сообщений, зашифрованных RSA, с использованием PKCS # 1 v1 схема заполнения (схема заполнения рандомизирует и добавляет структуру к сообщению, зашифрованному RSA, поэтому можно определить, является ли расшифрованное сообщение действительным). Из-за недостатков схемы PKCS # 1 Блейхенбахер смог провести практическую атаку на реализации RSA Уровень защищенных сокетов протокол и восстановить ключи сеанса. В результате этой работы криптографы теперь рекомендуют использовать доказуемо безопасные схемы заполнения, такие как Оптимальное заполнение асимметричным шифрованием, а RSA Laboratories выпустила новые версии PKCS # 1, которые не уязвимы для этих атак.

Атаки анализа побочного канала

Была описана атака по побочному каналу с использованием анализа предсказания ветвлений (BPA). Многие процессоры используют предсказатель ветвления для определения вероятности выполнения условного перехода в потоке команд программы. Часто эти процессоры также реализуют одновременная многопоточность (SMT). Атаки с анализом предсказания ветвления используют шпионский процесс для обнаружения (статистически) закрытого ключа при обработке этими процессорами.

Simple Branch Prediction Analysis (SBPA) утверждает, что улучшает BPA нестатистическим способом. В своей статье «О силе анализа с предсказанием простых ветвей»^[39] авторы SBPA (Онур Ачичмез и Цетин Кая Коч ) утверждают, что обнаружил 508 из 512 бит ключа RSA за 10 итераций.

В 2010 году была описана атака сбоя питания на реализации RSA.^[40] Автор восстановил ключ, внеся допустимые пределы напряжения питания процессора; это вызвало несколько сбоев питания на сервере.

Реализации

Некоторые криптографические библиотеки, обеспечивающие поддержку RSA, включают:

• Ботан
• Надувной Замок
• cryptlib
• Крипто ++
• Libgcrypt
• Крапива
• OpenSSL
• волк
• GnuTLS
• mbed TLS
• LibreSSL

Смотрите также

• Акустический криптоанализ
• Теория вычислительной сложности
• Длина криптографического ключа
• Обмен ключами Диффи – Хеллмана
• Обмен ключами
• Ключевой менеджмент
• Криптография с эллиптической кривой
• Криптография с открытым ключом
• Функция люка

Рекомендации

дальнейшее чтение

• Менезеш, Альфред; van Oorschot, Paul C .; Ванстон, Скотт А. (октябрь 1996 г.). Справочник по прикладной криптографии. CRC Press. ISBN  978-0-8493-8523-0.
• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001). Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр.881 –887. ISBN  978-0-262-03293-3.

внешняя ссылка

• Оригинальный патент RSA, поданный Ривестом в Патентное ведомство США; Рональд Л. (Бельмонт, Массачусетс), Шамир; Ади (Кембридж, Массачусетс), Адлеман; Леонард М. (Арлингтон, Массачусетс), 14 декабря 1977 г., Патент США 4,405,829 .
• PKCS # 1: стандарт криптографии RSA (RSA Laboratories интернет сайт)
  • В PKCS #1 стандарт "дает рекомендации по реализации криптография с открытым ключом на основе ЮАР алгоритм, охватывающий следующие аспекты: криптографические примитивы; шифрование схемы; подпись схемы с приложением; ASN.1 синтаксис для представления ключей и для идентификации схем ".
• Объяснение RSA с использованием цветных ламп на YouTube
• Тщательная прогулка по ЮАР
• Поиск простых чисел: как работает шифр RSA
• Онур Ачиичмез, Четин Кая Коч, Жан-Пьер Зейферт: О силе анализа с предсказанием простых ветвей
• Новая уязвимость в криптографии RSA, блог CAcert NEWS
• Пример реализации RSA с заполнением PKCS # 1 (исходный код GPL)
• Статья Кохера о временных атаках
• Анимированное объяснение RSA с его математической подоплекой от CrypTool
• Грайм, Джеймс. «Шифрование RSA». Numberphile. Брэди Харан.
• Как ключ RSA используется для шифрования в реальном мире