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

Алгоритм криптографии с открытым ключом

RSA ( Ривест-Шамир-Адлеман ) — криптосистема с открытым ключом , одна из старейших, широко используемых для безопасной передачи данных. Инициализм «RSA» происходит от фамилий Рона Ривеста , Ади Шамира и Леонарда Адлемана , которые публично описали алгоритм в 1977 году. Эквивалентная система была тайно разработана в 1973 году в штаб - квартире правительственной связи (GCHQ), британском агентстве радиотехнической разведки , английский математик Клиффорд Кокс . Эта система была рассекречена в 1997 году. ^[2]

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

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

RSA — относительно медленный алгоритм. По этой причине он обычно не используется для прямого шифрования пользовательских данных. Чаще всего 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 :

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

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

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

Операция

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

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

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

и что, зная e и n или даже m , найти d может быть крайне сложно . Здесь символ ≡ обозначает модульное сравнение : т.е. оба ( m ^e ) ^d и m имеют одинаковый остаток при делении на n .

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

$${\displaystyle (m^{d})^{e}\equiv m{\pmod {n}}.}$$

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

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

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

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

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

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

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

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

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

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

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

Шифрование

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

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

$${\displaystyle c\equiv m^{e}{\pmod {n}}.}$$

Это можно сделать достаточно быстро, даже для очень больших чисел, используя модульное возведение в степень . Затем Боб передает c Алисе. Обратите внимание, что по крайней мере девять значений m дадут зашифрованный текст c, равный m , ^[a] , но на практике это маловероятно.

Расшифровка

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

$${\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m{\pmod {n}}.}$$

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

Пример

Вот пример шифрования и дешифрования RSA: ^[b]

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

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

2. Вычислите n = pq , давая

   ${\displaystyle n=61\times 53=3233.}$

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

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

4. Выберите любое число 2 < e < 780 , взаимно простое с 780. Выбор простого числа для e оставляет нам только проверку того, что e не является делителем 780.

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

5. Вычислите d , модульную мультипликативную обратную величину e ( mod λ ( n )) и получите
   
   $${\displaystyle d=413,}$$
   как ${\displaystyle 1=(17\times 413){\bmod {7}}80.}$

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

$${\displaystyle {\begin{aligned}c(m)&=m^{e}{\bmod {n}}\\&=m^{17}{\bmod {3}}233.\end{aligned}}}$$

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

$${\displaystyle {\begin{aligned}m(c)&=c^{d}{\bmod {n}}\\&=c^{413}{\bmod {3}}233.\end{aligned}}}$$

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

$${\displaystyle c=65^{17}{\bmod {3}}233=2790.}$$

Чтобы расшифровать c = 2790 , нужно вычислить

$${\displaystyle m=2790^{413}{\bmod {3}}233=65.}$$

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

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

Значения d _p , d _q и q _inv , являющиеся частью закрытого ключа, вычисляются следующим образом:

$${\displaystyle {\begin{aligned}d_{p}&=d{\bmod {(}}p-1)=413{\bmod {(}}61-1)=53,\\d_{q}&=d{\bmod {(}}q-1)=413{\bmod {(}}53-1)=49,\\q_{\text{inv}}&=q^{-1}{\bmod {p}}=53^{-1}{\bmod {6}}1=38\\&\Rightarrow (q_{\text{inv}}\times q){\bmod {p}}=38\times 53{\bmod {6}}1=1.\end{aligned}}}$$

Вот как d _p , d _q и q _inv используются для эффективного дешифрования (шифрование эффективно при выборе подходящей пары d и e ):

$${\displaystyle {\begin{aligned}m_{1}&=c^{d_{p}}{\bmod {p}}=2790^{53}{\bmod {6}}1=4,\\m_{2}&=c^{d_{q}}{\bmod {q}}=2790^{49}{\bmod {5}}3=12,\\h&=(q_{\text{inv}}\times (m_{1}-m_{2})){\bmod {p}}=(38\times -8){\bmod {6}}1=1,\\m&=m_{2}+h\times q=12+1\times 53=65.\end{aligned}}}$$

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

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

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

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

$${\displaystyle h=\operatorname {hash} (m),}$$

$${\displaystyle (h^{e})^{d}=h^{ed}=h^{de}=(h^{d})^{e}\equiv h{\pmod {n}}.}$$

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

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

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

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

Доказательство правильности RSA основано на маленькой теореме Ферма , утверждающей, что a ^{p − 1} ≡ 1 (mod p ) для любого целого числа a и простого числа p , не делящего a . ^{[примечание 1]}

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

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

mpqeded ≡ 1 (mod λ ( pq ))

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

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

hk^{[заметка 2]}

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

Чтобы показать, что m ^ed ≡ m (mod p ) , рассмотрим два случая:

1. Если m ≡ 0 (mod p ) , m кратно p . Таким образом , ^ed кратно p . Итак, m ^ed ≡ 0 ≡ m (mod p ) .
2. Если m 0 (mod p ) ${\displaystyle \not \equiv }$ ,

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

   где мы использовали малую теорему Ферма для замены m ^{p −1} mod p на 1.

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

1. Если m ≡ 0 (mod q ) , m ^ed кратно q . Итак, m ^ed ≡ 0 ≡ m (mod q ) .
2. Если m 0 (mod q ) ${\displaystyle \not \equiv }$ ,

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

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

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

Примечания

1. Мы не можем тривиально нарушить RSA, применив теорему (mod pq ), поскольку pq не является простым числом.
2. В частности, приведенное выше утверждение справедливо для любых e и d , которые удовлетворяют ed ≡ 1 (mod ( p - 1)( q - 1)) , поскольку ( p - 1)( q - 1) делится на λ ( pq ) и, таким образом, тривиально также через p − 1 и q − 1 . Однако в современных реализациях RSA обычно используется уменьшенный частный показатель d , который удовлетворяет только более слабому, но достаточному условию ed ≡ 1 (mod λ ( pq )) .
3. Это часть китайской теоремы об остатках , хотя и не является важной частью этой теоремы.

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

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

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

$${\displaystyle m^{ed}=m^{1+h\varphi (n)}=m(m^{\varphi (n)})^{h}\equiv m(1)^{h}\equiv m{\pmod {n}},}$$

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

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

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

Заполнение

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

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

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

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

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

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

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

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

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

В целях эффективности многие популярные криптобиблиотеки (такие как OpenSSL , Java и .NET ) используют для расшифровки и подписи следующую оптимизацию, основанную на китайской теореме об остатках . ^{[ нужна цитация ]} Следующие значения предварительно вычисляются и сохраняются как часть закрытого ключа:

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

Эти значения позволяют получателю более эффективно вычислять возведение в степень m = c ^d (mod pq ) следующим образом: , , , ^[c] .
      ${\displaystyle m_{1}=c^{d_{P}}{\pmod {p}}}$
      ${\displaystyle m_{2}=c^{d_{Q}}{\pmod {q}}}$
      ${\displaystyle h=q_{\text{inv}}(m_{1}-m_{2}){\pmod {p}}}$
      ${\displaystyle m=m_{2}+hq{\pmod {pq}}}$

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

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

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

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

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

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

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

По состоянию на 2020 год ^[update]самое большое общеизвестное факторизованное число RSA имело 829 бит (250 десятичных цифр, RSA-250 ). ^[30] Его факторизация с помощью современной распределенной реализации заняла около 2700 процессоро-лет. На практике ключи RSA обычно имеют длину от 1024 до 4096 бит. В 2003 году компания RSA Security подсчитала, что 1024-битные ключи, скорее всего, станут взломанными к 2010 году. ^[31] По состоянию на 2020 год неизвестно, можно ли взломать такие ключи, но минимальные рекомендации изменены как минимум на 2048 бит. ^[32] Обычно предполагается, что RSA безопасен, если n достаточно велико, за пределами квантовых вычислений.

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

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

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

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

Числа p и q не должны быть «слишком близкими», иначе факторизация Ферма для n будет успешной. Если p − q меньше 2 n ^1/4 ( n = p ⋅ q , что даже для «маленьких» 1024-битных значений n равно3 × 10 ⁷⁷ ), решение для p и q тривиально. Более того, если либо p - 1 , либо q - 1 имеет только небольшие простые множители, n можно быстро факторизовать с помощью алгоритма Полларда p - 1 , и, следовательно, такие значения p или q следует отбросить.

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

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

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

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

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

Они воспользовались слабостью, уникальной для криптосистем, основанной на факторизации целых чисел. Если n = pq — один открытый ключ, а n ’ = p ’ q ’ — другой, то если случайно p = p ’ (но q не равно q ’), то простое вычисление НОД( n , n ′ ) = p учитывает как n , так и n ', полностью ставя под угрозу оба ключа. Ленстра и др. Обратите внимание, что эту проблему можно свести к минимуму, используя сильное случайное начальное число с битовой длиной, вдвое превышающей предполагаемый уровень безопасности, или используя детерминированную функцию для выбора q при заданном p вместо независимого выбора p и q .

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

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

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

Временные атаки

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

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

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

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

Вариант этой атаки, получивший название «BERserk», появился еще в 2014 году. ^{[40] [41]} Он затронул криптобиблиотеку Mozilla NSS, которая, в частности, использовалась Firefox и Chrome.

Атаки анализа побочных каналов

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

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

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

Сложная реализация

Чтобы безопасно реализовать RSA, необходимо учитывать множество деталей (сильный PRNG , приемлемый публичный показатель и т. д.). Это усложняет реализацию, вплоть до того, что в книге «Практическая криптография с Go» предлагается по возможности избегать RSA. ^[44]

Реализации

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

• Ботан
• Надувной замок
• криптлиб
• Крипто++
• Libgcrypt
• Крапива
• OpenSSL
• волкСклеп
• ГнуTLS
• mbed TLS
• LibreSSL

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

• Математический портал

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

Примечания

1. А именно, значения m , которые равны -1, 0 или 1 по модулю p , а также равны -1, 0 или 1 по модулю q . Будет больше значений m , имеющих c = m, если p  - 1 или q  - 1 имеет другие делители, общие с e  - 1, кроме 2, потому что это дает больше значений m , таких что или соответственно. ${\displaystyle m^{e-1}{\bmod {p}}=1}$ ${\displaystyle m^{e-1}{\bmod {q}}=1}$
2. Используемые здесь параметры искусственно занижены, но также можно использовать OpenSSL для генерации и проверки реальной пары ключей.
3. Если , то некоторые ^{[ необходимы пояснения ]} библиотеки вычисляют h как . ${\displaystyle m_{1}<m_{2}}$ ${\displaystyle q_{\text{inv}}\left[\left(m_{1}+\left\lceil {\frac {q}{p}}\right\rceil p\right)-m_{2}\right]{\pmod {p}}}$

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

1. Ривест, Р.; Шамир, А.; Адлеман, Л. (февраль 1978 г.). «Метод получения цифровых подписей и криптосистем с открытым ключом» (PDF) . Коммуникации АКМ . 21 (2): 120–126. CiteSeerX  10.1.1.607.2677 . дои : 10.1145/359340.359342. S2CID  2873616. Архивировано из оригинала (PDF) 27 января 2023 г.
2. Смарт, Найджел (19 февраля 2008 г.). "Доктор Клиффорд Кокс CB". Бристольский университет . Проверено 14 августа 2011 г.
3. Кастельвекки, Давиде (30 октября 2020 г.). «Пионер квантовых вычислений предупреждает о самоуспокоенности по поводу безопасности Интернета». Природа . 587 (7833): 189. Бибкод : 2020Natur.587..189C. дои : 10.1038/d41586-020-03068-9. PMID  33139910. S2CID  226243008.Интервью Петра Шора 2020 года .
4. Диффи, В.; Хеллман, Мэн (ноябрь 1976 г.). «Новые направления в криптографии». Транзакции IEEE по теории информации . 22 (6): 644–654. CiteSeerX 10.1.1.37.9720 . дои : 10.1109/TIT.1976.1055638. ISSN  0018-9448. 
5. Ривест, Рональд. «Первые дни ЮАР – история и уроки» (PDF) .
6. Калдербанк, Майкл (20 августа 2007 г.). «Криптосистема RSA: история, алгоритм, простые числа» (PDF) .
7. Робинсон, Сара (июнь 2003 г.). «Все еще сохраняя секреты после многих лет атак, RSA заслужила признание своих основателей» (PDF) . СИАМ Новости . 36 (5).
8. Кокс, CC (20 ноября 1973 г.). «Примечание о несекретном шифровании» (PDF) . www.gchq.gov.uk. _ Архивировано из оригинала (PDF) 28 сентября 2018 года . Проверено 30 мая 2017 г.
9. Джим Зауэрберг. «От шифров с закрытым ключом к шифрам с открытым ключом за три простых шага».
10. Маргарет Коззенс и Стивен Дж. Миллер. «Математика шифрования: элементарное введение». п. 180.
11. Аласдер МакЭндрю. «Введение в криптографию с помощью программного обеспечения с открытым исходным кодом». п. 12.
12. Сурендер Р. Чилука. «Криптография с открытым ключом».
13. Нил Коблиц. «Криптография как средство обучения». Криптология, Vol. 21, № 4 (1997).
14. «RSA Security выпускает алгоритм шифрования RSA в общественное достояние» . Архивировано из оригинала 21 июня 2007 года . Проверено 3 марта 2010 г.
15. Боне, Дэн (1999). «Двадцать лет атак на криптосистему RSA». Уведомления Американского математического общества . 46 (2): 203–213.
16. Прикладная криптография, John Wiley & Sons, Нью-Йорк, 1996. Брюс Шнайер , с. 467.
17. Макки, Джеймс; Пинч, Ричард (1998). «Дальнейшие атаки на серверные криптосистемы RSA». CiteSeerX 10.1.1.33.1333 . 
18. Курс теории чисел и криптографии, Тексты для аспирантов по математике. № 114, Springer-Verlag, Нью-Йорк, 1987. Нил Коблиц , Второе издание, 1994. с. 94.
19. Духовный, Виктор (31 июля 2015 г.). «общие факторы в (p - 1) и (q - 1)». openssl-dev (список рассылки).
20. Духовный, Виктор (1 августа 2015 г.). «общие факторы в (p - 1) и (q - 1)». openssl-dev (список рассылки).
21. Джонсон, Дж.; Калиски, Б. (февраль 2003 г.). Стандарты криптографии с открытым ключом (PKCS) № 1: Спецификации криптографии RSA, версия 2.1. Сетевая рабочая группа. дои : 10.17487/RFC3447 . РФК 3447 . Проверено 9 марта 2016 г.
22. Хостад, Йохан (1986). «Об использовании RSA с низкой экспонентой в сети с открытым ключом». Достижения в криптологии – CRYPTO '85 Proceedings . Конспекты лекций по информатике. Том. 218. С. 403–408. дои : 10.1007/3-540-39799-X_29. ISBN 978-3-540-16463-0.
23. Копперсмит, Дон (1997). «Малые решения полиномиальных уравнений и уязвимости RSA с низким показателем» (PDF) . Журнал криптологии . 10 (4): 233–260. CiteSeerX 10.1.1.298.4806 . дои : 10.1007/s001459900030. S2CID  15726802. 
24. Гольдвассер, Шафи ; Микали, Сильвио (5 мая 1982 г.). «Вероятностное шифрование и как играть в мысленный покер, сохраняя в секрете всю частичную информацию». Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 365–377. дои : 10.1145/800070.802212. ISBN 978-0-89791-070-5. S2CID  10316867.
25. Корон, Жан-Себастьян; Джой, Марк; Наккеш, Дэвид; Пайе, Паскаль (2000). «Новые атаки на шифрование PKCS # 1 v1.5». В Прениле, Барт (ред.). Достижения в криптологии — EUROCRYPT 2000 . Конспекты лекций по информатике. Том. 1807. Берлин, Гейдельберг: Springer. стр. 369–381. дои : 10.1007/3-540-45539-6_25 . ISBN 978-3-540-45539-4.
26. «Алгоритм RSA».
27. Мачи, Эдмонд К. (29 марта 2013 г.). Атака с отслеживанием сетевой безопасности и реагирование на нее в сети Министерства обороны США. Траффорд. п. 167. ИСБН 978-1466985742.
28. Ленстра, Арьен; и другие. (Группа) (2000). «Факторизация 512-битного модуля RSA» (PDF) . Еврокрипт.
29. Миллер, Гэри Л. (1975). «Гипотеза Римана и тесты на простоту» (PDF) . Материалы седьмого ежегодного симпозиума ACM по теории вычислений . стр. 234–239.
30. Циммерманн, Пол (28 февраля 2020 г.). «Факторизация RSA-250». Cado-nfs-обсудить. Архивировано из оригинала 28 февраля 2020 г. Проверено 12 июля 2020 г.
31. Калиски, Берт (6 мая 2003 г.). «Размер ключа TWIRL и RSA». Лаборатории РСА . Архивировано из оригинала 17 апреля 2017 г. Проверено 24 ноября 2017 г.
32. Баркер, Элейн; Данг, Куинь (22 января 2015 г.). «Специальная публикация NIST 800-57, часть 3, редакция 1: Рекомендации по управлению ключами: Руководство по управлению ключами для конкретных приложений» (PDF) . Национальный институт стандартов и технологий . п. 12. дои :10.6028/NIST.SP.800-57pt3r1 . Проверено 24 ноября 2017 г.
33. Сэнди, Майкл (21 ноября 2011 г.). «Сертификатами RSA-512 злоупотребляют в реальных условиях» . Блог Fox-IT International .
34. Винер, Майкл Дж. (май 1990 г.). «Криптоанализ коротких секретных показателей RSA» (PDF) . Транзакции IEEE по теории информации . 36 (3): 553–558. дои : 10.1109/18.54902. S2CID  7120331.
35. Немек, Матус; Сис, Марек; Свенда, Петр; Клинец, Душан; Матяс, Вашек (ноябрь 2017 г.). «Возвращение атаки Копперсмита: практическая факторизация широко используемых модулей RSA» (PDF) . Материалы конференции ACM SIGSAC 2017 года по компьютерной и коммуникационной безопасности . ККС '17. дои : 10.1145/3133956.3133969.
36. Маркофф, Джон (14 февраля 2012 г.). «Недостаток, обнаруженный в методе онлайн-шифрования». Нью-Йорк Таймс .
37. Ленстра, Арьен К.; Хьюз, Джеймс П.; Ожье, Максим; Бос, Йоппе В.; Кляйнъунг, Торстен; Вахтер, Кристоф (2012). «Рон был неправ, Уит прав» (PDF) .
38. Хенингер, Надя (15 февраля 2012 г.). «Новое исследование: не нужно паниковать по поводу факторизуемых ключей — просто помните о своих P и Q». Свобода мастерить .
39. Брамли, Дэвид; Боне, Дэн (2003). «Удаленные атаки по времени практичны» (PDF) . Материалы 12-й конференции по симпозиуму по безопасности USENIX . ССИМ'03.
40. «Ошибка 'BERserk', обнаруженная в криптобиблиотеке Mozilla NSS, влияет на Firefox, Chrome» . 25 сентября 2014 года . Проверено 4 января 2022 г.
41. «Подделка подписи RSA в NSS» . Мозилла .
42. Аджичмез, Онур; Коч, Четин Кая; Зайферт, Жан-Пьер (2007). «О возможностях простого анализа предсказания ветвей». Материалы 2-го симпозиума ACM по информационной, компьютерной и коммуникационной безопасности . АЗИАККС '07. стр. 312–320. CiteSeerX 10.1.1.80.1438 . дои : 10.1145/1229285.1266999. 
43. Пеллегрини, Андреа; Бертакко, Валерия; Остин, Тодд (2010). «Атака аутентификации RSA на основе ошибок» (PDF) .
44. Исом, Кайл. «Практическая криптография с Go» . Проверено 4 января 2022 г.

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

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

Внешние ссылки

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