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

Algorithm for public-key cryptography

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] [ самостоятельно опубликованный источник? ]}

They exploited a weakness unique to cryptosystems based on integer factorization. If n = pq is one public key, and n′ = p′q′ is another, then if by chance p = p′ (but q is not equal to q'), then a simple computation of gcd(n, n′) = p factors both n and n', totally compromising both keys. Lenstra et al. note that this problem can be minimized by using a strong random seed of bit length twice the intended security level, or by employing a deterministic function to choose q given p, instead of choosing p and q independently.

Nadia Heninger was part of a group that did a similar experiment. They used an idea of Daniel J. Bernstein to compute the GCD of each RSA key n against the product of all the other keys n' they had found (a 729-million-digit number), instead of computing each gcd(n, n′) separately, thereby achieving a very significant speedup, since after one large division, the GCD problem is of normal size.

Heninger says in her blog that the bad keys occurred almost entirely in embedded applications, including "firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones" from more than 30 manufacturers. Heninger explains that the one-shared-prime problem uncovered by the two groups results from situations where the pseudorandom number generator is poorly seeded initially, and then is reseeded between the generation of the first and second primes. Using seeds of sufficiently high entropy obtained from key stroke timings or electronic diode noise or atmospheric noise from a radio receiver tuned between stations should solve the problem.^[39]

Strong random number generation is important throughout every phase of public-key cryptography. For instance, if a weak generator is used for the symmetric keys that are being distributed by RSA, then an eavesdropper could bypass RSA and guess the symmetric keys directly.

Timing attacks

Kocher described a new attack on RSA in 1995: if the attacker Eve knows Alice's hardware in sufficient detail and is able to measure the decryption times for several known ciphertexts, Eve can deduce the decryption key d quickly. This attack can also be applied against the RSA signature scheme. In 2003, Boneh and Brumley demonstrated a more practical attack capable of recovering RSA factorizations over a network connection (e.g., from a Secure Sockets Layer (SSL)-enabled webserver).^[40] This attack takes advantage of information leaked by the Chinese remainder theorem optimization used by many RSA implementations.

One way to thwart these attacks is to ensure that the decryption operation takes a constant amount of time for every ciphertext. However, this approach can significantly reduce performance. Instead, most RSA implementations use an alternate technique known as cryptographic blinding. RSA blinding makes use of the multiplicative property of RSA. Instead of computing c^d (mod n), Alice first chooses a secret random value r and computes (r^ec)^d (mod n). The result of this computation, after applying Euler's theorem, is rc^d (mod n), and so the effect of r can be removed by multiplying by its inverse. A new value of r is chosen for each ciphertext. With blinding applied, the decryption time is no longer correlated to the value of the input ciphertext, and so the timing attack fails.

Adaptive chosen-ciphertext attacks

In 1998, Daniel Bleichenbacher described the first practical adaptive chosen-ciphertext attack against RSA-encrypted messages using the PKCS #1 v1 padding scheme (a padding scheme randomizes and adds structure to an RSA-encrypted message, so it is possible to determine whether a decrypted message is valid). Due to flaws with the PKCS #1 scheme, Bleichenbacher was able to mount a practical attack against RSA implementations of the Secure Sockets Layer protocol and to recover session keys. As a result of this work, cryptographers now recommend the use of provably secure padding schemes such as Optimal Asymmetric Encryption Padding, and RSA Laboratories has released new versions of PKCS #1 that are not vulnerable to these attacks.

A variant of this attack, dubbed "BERserk", came back in 2014.^[41][42] It impacted the Mozilla NSS Crypto Library, which was used notably by Firefox and Chrome.

Side-channel analysis attacks

A side-channel attack using branch-prediction analysis (BPA) has been described. Many processors use a branch predictor to determine whether a conditional branch in the instruction flow of a program is likely to be taken or not. Often these processors also implement simultaneous multithreading (SMT). Branch-prediction analysis attacks use a spy process to discover (statistically) the private key when processed with these processors.

Simple Branch Prediction Analysis (SBPA) claims to improve BPA in a non-statistical way. In their paper, "On the Power of Simple Branch Prediction Analysis",^[43] the authors of SBPA (Onur Aciicmez and Cetin Kaya Koc) claim to have discovered 508 out of 512 bits of an RSA key in 10 iterations.

A power-fault attack on RSA implementations was described in 2010.^{[44][self-published source?]} The author recovered the key by varying the CPU power voltage outside limits; this caused multiple power faults on the server.

Tricky implementation

There are many details to keep in mind in order to implement RSA securely (strong PRNG, acceptable public exponent, etc.). This makes the implementation challenging, to the point the book Practical Cryptography With Go suggests avoiding RSA if possible.^[45]

Implementations

Some cryptography libraries that provide support for RSA include:

• Botan
• Bouncy Castle
• cryptlib
• Crypto++
• Libgcrypt
• Nettle
• OpenSSL
• wolfCrypt
• GnuTLS
• mbed TLS
• LibreSSL

See also

• Mathematics portal

• Acoustic cryptanalysis
• Computational complexity theory
• Diffie–Hellman key exchange
• Digital Signature Algorithm
• Elliptic-curve cryptography
• Key exchange
• Key management
• Key size
• Public-key cryptography
• Rabin cryptosystem
• Trapdoor function

Notes

1. Namely, the values of m which are equal to −1, 0, or 1 modulo p while also equal to −1, 0, or 1 modulo q. There will be more values of m having c = m if p − 1 or q − 1 has other divisors in common with e − 1 besides 2 because this gives more values of m such that ${\displaystyle m^{e-1}{\bmod {p}}=1}$ or ${\displaystyle m^{e-1}{\bmod {q}}=1}$ respectively.
2. The parameters used here are artificially small, but one can also OpenSSL can also be used to generate and examine a real keypair.
3. If ${\displaystyle m_{1}<m_{2}}$, then some^{[clarification needed]} libraries compute h as ${\displaystyle q_{\text{inv}}\left[\left(m_{1}+\left\lceil {\frac {q}{p}}\right\rceil p\right)-m_{2}\right]{\pmod {p}}}$.

References

1. Rivest, R.; Shamir, A.; Adleman, L. (February 1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (PDF). Communications of the ACM. 21 (2): 120–126. CiteSeerX 10.1.1.607.2677. doi:10.1145/359340.359342. S2CID 2873616. Archived from the original (PDF) on 2023-01-27.
2. Smart, Nigel (February 19, 2008). "Dr Clifford Cocks CB". Bristol University. Retrieved August 14, 2011.
3. Castelvecchi, Davide (2020-10-30). "Quantum-computing pioneer warns of complacency over Internet security". Nature. 587 (7833): 189. Bibcode:2020Natur.587..189C. doi:10.1038/d41586-020-03068-9. PMID 33139910. S2CID 226243008. 2020 interview of Peter Shor.
4. Diffie, W.; Hellman, M. E. (November 1976). "New directions in cryptography". IEEE Transactions on Information Theory. 22 (6): 644–654. CiteSeerX 10.1.1.37.9720. doi:10.1109/TIT.1976.1055638. ISSN 0018-9448.
5. Rivest, Ronald. "The Early Days of RSA – History and Lessons" (PDF).
6. Calderbank, Michael (2007-08-20). "The RSA Cryptosystem: History, Algorithm, Primes" (PDF).
7. Robinson, Sara (June 2003). "Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders" (PDF). SIAM News. 36 (5).
8. Cocks, C. C. (20 November 1973). "A Note on Non-Secret Encryption" (PDF). www.gchq.gov.uk. Archived from the original (PDF) on 28 September 2018. Retrieved 2017-05-30.
9. Jim Sauerberg. "From Private to Public Key Ciphers in Three Easy Steps".
10. Margaret Cozzens and Steven J. Miller. "The Mathematics of Encryption: An Elementary Introduction". p. 180.
11. Alasdair McAndrew. "Introduction to Cryptography with Open-Source Software". p. 12.
12. Surender R. Chiluka. "Public key Cryptography".
13. Neal Koblitz. "Cryptography As a Teaching Tool". Cryptologia, Vol. 21, No. 4 (1997).
14. "RSA Security Releases RSA Encryption Algorithm into Public Domain". Archived from the original on June 21, 2007. Retrieved 2010-03-03.
15. Boneh, Dan (1999). "Twenty Years of attacks on the RSA Cryptosystem". Notices of the American Mathematical Society. 46 (2): 203–213.
16. Applied Cryptography, John Wiley & Sons, New York, 1996. Bruce Schneier, p. 467.
17. McKee, James; Pinch, Richard (1998). "Further Attacks on Server-Aided RSA Cryptosystems". CiteSeerX 10.1.1.33.1333.
18. A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, New York, 1987. Neal Koblitz, Second edition, 1994. p. 94.
19. Dukhovni, Viktor (July 31, 2015). "common factors in (p − 1) and (q − 1)". openssl-dev (Mailing list).
20. Dukhovni, Viktor (August 1, 2015). "common factors in (p − 1) and (q − 1)". openssl-dev (Mailing list).
21. Johnson, J.; Kaliski, B. (February 2003). Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1. Network Working Group. doi:10.17487/RFC3447. RFC 3447. Retrieved 9 March 2016.
22. Håstad, Johan (1986). "On using RSA with Low Exponent in a Public Key Network". Advances in Cryptology – CRYPTO '85 Proceedings. Lecture Notes in Computer Science. Vol. 218. pp. 403–408. doi:10.1007/3-540-39799-X_29. ISBN 978-3-540-16463-0.
23. Coppersmith, Don (1997). "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities" (PDF). Journal of Cryptology. 10 (4): 233–260. CiteSeerX 10.1.1.298.4806. doi:10.1007/s001459900030. S2CID 15726802.
24. Goldwasser, Shafi; Micali, Silvio (1982-05-05). "Probabilistic encryption & how to play mental poker keeping secret all partial information". Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. New York, NY, USA: Association for Computing Machinery. pp. 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). "New Attacks on PKCS#1 v1.5 Encryption". In Preneel, Bart (ed.). 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 Algorithm".
27. "OpenSSL bn_s390x.c". Github. Retrieved 2 August 2024.
28. Machie, Edmond K. (29 March 2013). Network security traceback attack and react in the United States Department of Defense network. Trafford. p. 167. ISBN 978-1466985742.
29. Lenstra, Arjen; et al. (Group) (2000). "Factorization of a 512-bit RSA Modulus" (PDF). Eurocrypt.
30. Miller, Gary L. (1975). "Riemann's Hypothesis and Tests for Primality" (PDF). Proceedings of Seventh Annual ACM Symposium on Theory of Computing. pp. 234–239.
31. Zimmermann, Paul (2020-02-28). "Factorization of RSA-250". Cado-nfs-discuss. Archived from the original on 2020-02-28. Retrieved 2020-07-12.
32. Kaliski, Burt (2003-05-06). "TWIRL and RSA Key Size". RSA Laboratories. Archived from the original on 2017-04-17. Retrieved 2017-11-24.
33. Barker, Elaine; Dang, Quynh (2015-01-22). "NIST Special Publication 800-57 Part 3 Revision 1: Recommendation for Key Management: Application-Specific Key Management Guidance" (PDF). National Institute of Standards and Technology. p. 12. doi:10.6028/NIST.SP.800-57pt3r1. Retrieved 2017-11-24.
34. Sandee, Michael (November 21, 2011). "RSA-512 certificates abused in-the-wild". Fox-IT International blog.
35. Wiener, Michael J. (May 1990). "Cryptanalysis of short RSA secret exponents" (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 (November 2017). "The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli" (PDF). Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. CCS '17. doi:10.1145/3133956.3133969.
37. Markoff, John (February 14, 2012). "Flaw Found in an Online Encryption Method". The New York Times.
38. Lenstra, Arjen K.; Hughes, James P.; Augier, Maxime; Bos, Joppe W.; Kleinjung, Thorsten; Wachter, Christophe (2012). "Ron was wrong, Whit is right" (PDF).
39. Heninger, Nadia (February 15, 2012). "New research: There's no need to panic over factorable keys–just mind your Ps and Qs". Freedom to Tinker.
40. Brumley, David; Boneh, Dan (2003). "Remote timing attacks are practical" (PDF). Proceedings of the 12th Conference on USENIX Security Symposium. SSYM'03.
41. "'BERserk' Bug Uncovered In Mozilla NSS Crypto Library Impacts Firefox, Chrome". 25 September 2014. Retrieved 4 January 2022.
42. "RSA Signature Forgery in NSS". Mozilla.
43. Acıiçmez, Onur; Koç, Çetin Kaya; Seifert, Jean-Pierre (2007). "On the power of simple branch prediction analysis". Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security. ASIACCS '07. pp. 312–320. CiteSeerX 10.1.1.80.1438. doi:10.1145/1229285.1266999.
44. Pellegrini, Andrea; Bertacco, Valeria; Austin, Todd (2010). "Fault-Based Attack of RSA Authentication" (PDF).
45. Isom, Kyle. "Practical Cryptography With Go". Retrieved 4 January 2022.

Further reading

• Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). Handbook of Applied Cryptography. CRC Press. ISBN 978-0-8493-8523-0.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 881–887. ISBN 978-0-262-03293-3.

External links

• The Original RSA Patent as filed with the U.S. Patent Office by Rivest; Ronald L. (Belmont, MA), Shamir; Adi (Cambridge, MA), Adleman; Leonard M. (Arlington, MA), December 14, 1977, U.S. patent 4,405,829.
• RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2
• Explanation of RSA using colored lamps on YouTube
• Thorough walk through of RSA
• Prime Number Hide-And-Seek: How the RSA Cipher Works
• Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: On the Power of Simple Branch Prediction Analysis