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

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

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

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

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

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

История

Ади Шамир , соавтор RSA (другие — Рон Ривест и Леонард Адлеман )

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

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

Клиффорд Кокс , английский математик, работавший в британском разведывательном агентстве Government Communications Headquarters (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 Security опубликовала алгоритм в открытом доступе 6 сентября 2000 года. ^[14]

Операция

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

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

Целые числа n и e составляют открытый ключ, d представляет закрытый ключ, а m представляет сообщение. Модульное возведение в степень до e и d соответствует шифрованию и дешифрованию соответственно.

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

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

Ключи для алгоритма 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) .
   • НОК можно вычислить с помощью алгоритма Евклида , поскольку НОК( a ,  b ) = ⁠| аб |/НОД( а ,  б )⁠ .
   • λ ( n ) держится в секрете.
4. Выберите целое число e такое, что 1 < e < λ ( n ) и gcd ( 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 ) (как она делает при расшифровке сообщения) и прикрепляет его в качестве «подписи» к сообщению. Когда Боб получает подписанное сообщение, он использует тот же алгоритм хэширования в сочетании с открытым ключом Алисы. Он возводит подпись в степень e (по модулю 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]}

Мы хотим показать, что для каждого целого числа m, когда p и q — различные простые числа, а e и d — положительные целые числа, удовлетворяющие условию ed ≡ 1 (mod λ ( pq )) . $${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}}$$

Поскольку λ ( pq ) = lcm ( p − 1, q − 1) по построению делится как на p − 1 , так и на q − 1 , мы можем записать для некоторых неотрицательных целых чисел h и k . ^{[примечание 2]} $${\displaystyle ed-1=h(p-1)=k(q-1)}$$

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

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

1. Если m ≡ 0 (mod p ) , m кратно p . Таким образом, m ^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, взаимно простых с n .

Когда 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} ) результат m ^e строго меньше модуля n . В этом случае шифртексты можно легко расшифровать, взяв корень e из шифртекста по целым числам.
• Если одно и то же сообщение в открытом тексте отправляется 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 Корон и др. ^[25] показали, что для некоторых типов сообщений это заполнение не обеспечивает достаточно высокого уровня безопасности. Более поздние версии стандарта включают оптимальное асимметричное шифрование (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 ) используют для расшифровки и подписания следующую оптимизацию, основанную на китайской теореме об остатках . ^{[27] [ необходима цитата ]} Следующие значения предварительно вычисляются и сохраняются как часть закрытого ключа:

• ${\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}$

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

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

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

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

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

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

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

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

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

В 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 . ^[35]

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

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

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

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

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

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

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

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

Атаки по времени

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

Один из способов предотвратить эти атаки — гарантировать, что операция расшифровки занимает постоянное количество времени для каждого зашифрованного текста. Однако этот подход может значительно снизить производительность. Вместо этого большинство реализаций RSA используют альтернативный метод, известный как криптографическое ослепление . Ослепление RSA использует мультипликативное свойство RSA. Вместо вычисления c ^d (mod n ) Алиса сначала выбирает секретное случайное значение r и вычисляет ( r ^e 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 году. ^{[41] [42]} Он затронул криптографическую библиотеку Mozilla NSS, которая использовалась, в частности, в Firefox и Chrome.

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

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

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

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

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

Чтобы безопасно реализовать RSA, нужно учитывать множество деталей (сильный PRNG , приемлемая публичная экспонента и т. д.). Это усложняет реализацию, вплоть до того, что в книге Practical Cryptography With Go рекомендуется избегать RSA, если это возможно. ^[45]

Реализации

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

• Ботан
• Надувной замок
• криптлиб
• Крипто++
• Libgcrypt
• Крапива
• OpenSSL
• wolfCrypt
• GnuTLS
• 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) . Сообщения ACM . 21 (2): 120–126. CiteSeerX  10.1.1.607.2677 . doi :10.1145/359340.359342. S2CID  2873616. Архивировано из оригинала (PDF) 2023-01-27.
2. Смарт, Найджел (19 февраля 2008 г.). «Dr Clifford Cocks CB». Университет Бристоля . Получено 14 августа 2011 г.
3. Кастельвекки, Давиде (30.10.2020). «Пионер квантовых вычислений предупреждает о самоуспокоенности в вопросах безопасности Интернета». Nature . 587 (7833): 189. Bibcode :2020Natur.587..189C. doi :10.1038/d41586-020-03068-9. PMID  33139910. S2CID  226243008.Интервью Питера Шора 2020 года .
4. Диффи, У.; Хеллман, М. Э. (ноябрь 1976 г.). «Новые направления в криптографии». Труды IEEE по теории информации . 22 (6): 644–654. CiteSeerX 10.1.1.37.9720 . doi :10.1109/TIT.1976.1055638. ISSN  0018-9448. 
5. Ривест, Рональд. «Ранние дни RSA – История и уроки» (PDF) .
6. Колдербэнк, Майкл (2007-08-20). «Криптосистема RSA: история, алгоритм, простые числа» (PDF) .
7. Робинсон, Сара (июнь 2003 г.). «Все еще охраняя секреты после многих лет атак, RSA зарабатывает почести своим основателям» (PDF) . SIAM News . 36 (5).
8. Cocks, CC (20 ноября 1973 г.). «Заметка о несекретном шифровании» (PDF) . www.gchq.gov.uk . Архивировано из оригинала (PDF) 28 сентября 2018 г. . Получено 2017-05-30 .
9. Джим Зауэрберг. «От шифров с закрытым ключом к шифрам с открытым ключом за три простых шага».
10. Маргарет Коззенс и Стивен Дж. Миллер. «Математика шифрования: элементарное введение». стр. 180.
11. Аласдер МакЭндрю. «Введение в криптографию с открытым исходным кодом». стр. 12.
12. Сурендер Р. Чилука. «Криптография с открытым ключом».
13. Нил Коблиц. «Криптография как средство обучения». Криптология, т. 21, № 4 (1997).
14. "RSA Security выпускает алгоритм шифрования RSA в общественное достояние". Архивировано из оригинала 21 июня 2007 г. Получено 2010-03-03 .
15. Boneh, Dan (1999). «Двадцать лет атак на криптосистему RSA». Notices of the American Mathematical Society . 46 (2): 203–213.
16. Прикладная криптография, John Wiley & Sons, Нью-Йорк, 1996. Брюс Шнайер , стр. 467.
17. Макки, Джеймс; Пинч, Ричард (1998). «Дальнейшие атаки на серверные криптосистемы RSA». CiteSeerX 10.1.1.33.1333 . 
18. Курс теории чисел и криптографии, Graduate Texts in Math. № 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. Сетевая рабочая группа. doi : 10.17487/RFC3447 . RFC 3447. Получено 9 марта 2016 г.
22. Хастад, Йохан (1986). «Об использовании RSA с низкой экспонентой в сети с открытым ключом». Достижения в криптологии – Труды CRYPTO '85 . Конспект лекций по информатике. Том 218. С. 403–408. doi :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 . doi :10.1007/s001459900030. S2CID  15726802. 
24. Голдвассер, Шафи ; Микали, Сильвио (1982-05-05). «Вероятностное шифрование и как играть в ментальный покер, сохраняя в тайне всю частичную информацию». Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений — STOC '82 . Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 365–377. doi :10.1145/800070.802212. ISBN 978-0-89791-070-5. S2CID  10316867.
25. Coron, Jean-Sébastien; Joye, Marc; Naccache, David; Paillier, Pascal (2000). «Новые атаки на шифрование PKCS#1 v1.5». В Preneel, Bart (ред.). Advances in Cryptology — EUROCRYPT 2000. Lecture Notes in Computer Science. Vol. 1807. Berlin, Heidelberg: Springer. pp. 369–381. doi : 10.1007/3-540-45539-6_25 . ISBN 978-3-540-45539-4.
26. «Алгоритм RSA».
27. "OpenSSL bn_s390x.c". Github . Получено 2 августа 2024 г. .
28. Machie, Edmond K. (29 марта 2013 г.). Сетевая безопасность отслеживает атаки и реагирует на них в сети Министерства обороны США. Траффорд. стр. 167. ISBN 978-1466985742.
29. Lenstra, Arjen; et al. (Group) (2000). «Факторизация 512-битного модуля RSA» (PDF) . Eurocrypt.
30. Миллер, Гэри Л. (1975). «Гипотеза Римана и тесты на простоту» (PDF) . Труды седьмого ежегодного симпозиума ACM по теории вычислений . стр. 234–239.
31. Циммерман, Пол (28.02.2020). "Факторизация RSA-250". Cado-nfs-discuss. Архивировано из оригинала 28.02.2020 . Получено 12.07.2020 .
32. Kaliski, Burt (2003-05-06). "TWIRL и размер ключа RSA". RSA Laboratories . Архивировано из оригинала 2017-04-17 . Получено 2017-11-24 .
33. Баркер, Элейн; Данг, Куинх (22.01.2015). "Специальная публикация NIST 800-57, часть 3, редакция 1: Рекомендации по управлению ключами: руководство по управлению ключами для конкретных приложений" (PDF) . Национальный институт стандартов и технологий . стр. 12. doi :10.6028/NIST.SP.800-57pt3r1 . Получено 24.11.2017 .
34. Сэнди, Майкл (21 ноября 2011 г.). «Сертификаты RSA-512 злоупотребляют в дикой природе». Блог Fox-IT International .
35. Винер, Майкл Дж. (май 1990 г.). «Криптоанализ коротких секретных экспонент RSA» (PDF) . IEEE Transactions on Information Theory . 36 (3): 553–558. doi :10.1109/18.54902. S2CID  7120331.
36. Nemec, Matus; Sys, Marek; Svenda, Petr; Klinec, Dusan; Matyas, Vashek (ноябрь 2017 г.). «Возвращение атаки Копперсмита: практическая факторизация широко используемых модулей RSA» (PDF) . Труды конференции ACM SIGSAC 2017 года по компьютерной и коммуникационной безопасности . CCS '17. doi :10.1145/3133956.3133969.
37. Маркофф, Джон (14 февраля 2012 г.). «В методе онлайн-шифрования обнаружен недостаток». The New York Times .
38. Ленстра, Арьен К.; Хьюз, Джеймс П.; Ожье, Максим; Бос, Йоппе В.; Кляйнъюнг, Торстен; Вахтер, Кристоф (2012). «Рон был неправ, Уит прав» (PDF) .
39. Хенингер, Надя (15 февраля 2012 г.). «Новое исследование: не нужно паниковать из-за факторизуемых ключей — просто следите за своими P и Q». Свобода мастерить .
40. Брамли, Дэвид; Бонех, Дэн (2003). «Удаленные атаки по времени практичны» (PDF) . Труды 12-й конференции по симпозиуму по безопасности USENIX . SSYM'03.
41. «Обнаружена ошибка 'BERserk' в криптографической библиотеке Mozilla NSS, влияющая на Firefox и Chrome». 25 сентября 2014 г. Получено 4 января 2022 г.
42. "Подделка подписи RSA в NSS". Mozilla .
43. Acıiçmez, Onur; Koç, Çetin Kaya; Seifert, Jean-Pierre (2007). «О силе простого анализа предсказания ветвлений». Труды 2-го симпозиума ACM по информационной, компьютерной и коммуникационной безопасности . ASIACCS '07. С. 312–320. CiteSeerX 10.1.1.80.1438 . doi :10.1145/1229285.1266999. 
44. Пеллегрини, Андреа; Бертакко, Валерия; Остин, Тодд (2010). «Атака аутентификации RSA на основе ошибок» (PDF) .
45. Айсом, Кайл. "Практическая криптография с Go" . Получено 4 января 2022 г.

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

• Менезес, Альфред; ван Ооршот, Пол К.; Ванстоун, Скотт А. (октябрь 1996 г.). Справочник по прикладной криптографии . CRC Press. ISBN 978-0-8493-8523-0.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 881–887. ISBN 978-0-262-03293-3.

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

• Оригинальный патент RSA, поданный в Патентное ведомство США Ривестом; Рональдом Л. (Белмонт, Массачусетс), Шамиром; Ади (Кембридж, Массачусетс), Адлеманом; Леонардом М. (Арлингтон, Массачусетс), 14 декабря 1977 г., патент США 4 405 829 .
• RFC 8017: PKCS #1: Спецификации криптографии RSA версии 2.2
• Объяснение RSA с использованием цветных ламп на YouTube
• Тщательный анализ RSA
• Прятки с простыми числами: как работает шифр RSA
• Онур Ачиичмез, Четин Кая Коч, Жан-Пьер Сейферт: О силе простого анализа предсказания ветвлений