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

Эта статья о криптосистеме. Информацию о компании см. в разделе RSA Security .

ЮАР

Общий
Дизайнеры	Рон Ривест , Ади Шамир и Леонард Адлеман
Впервые опубликовано	1977
Сертификация	ПККС#1 , ANSI X9.31
Деталь шифрования
Размеры ключей	переменная, но обычно от 2048 до 4096 бит
Раунды	1
Лучший публичный криптоанализ
Общее сито числового поля для классических компьютеров; Алгоритм Шора для квантовых компьютеров. 829 -битный ключ был сломан.

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

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

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

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

История

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

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

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

Клиффорд Кокс , английский математик , работавший в британской разведки штаб-квартире правительственных коммуникаций (GCHQ), описал аналогичную систему во внутреннем документе в 1973 году. Однако, учитывая, что в то время для его реализации требовались относительно дорогие компьютеры, он считался в основном диковинкой и, насколько известно, так и не был использован. Его идеи и концепции не были раскрыты до 1997 года из-за своей совершенно секретной классификации.

Kid-RSA (KRSA) — это упрощенный небезопасный шифр с открытым ключом, опубликованный в 1997 году и предназначенный для образовательных целей. Некоторые люди считают, что изучение Kid-RSA дает представление о RSA и других шифрах с открытым ключом, аналогичных упрощенному DES .

Патент

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

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

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

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

Операция

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

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

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

Однако, если даны только e и n , найти d чрезвычайно сложно .

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

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

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

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

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

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

В оригинальной статье RSA φ функция Эйлера ( 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) , рекомендуется, чтобы ( p − 1) и ( q − 1) имели только очень маленькие общие делители, если таковые имеются, помимо необходимых 2.

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

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

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

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

Шифрование

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

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

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

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

Расшифровка

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

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

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

Пример

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

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

   $p=61$ и $q=53$.

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

   $n=61\times 53=3233.$

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

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

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

   Позволять $e=17$.

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

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

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

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

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

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

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

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

$$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 , являющиеся частью закрытого ключа, вычисляются следующим образом:

$${\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 ):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$$ed-1=h(p-1)=k(q-1)$$

для некоторых неотрицательных целых чисел h и k .

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

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

1. Если m ≡ 0 (mod p ) , m кратно p . Таким образом, м ^Эд кратно p . Так что м ^Эд ≡ 0 ≡ м (мод п ) .
2. Если М $\not \equiv$ 0 (против р ) ,

   $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 ^{р -1} мод р с 1.

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

1. Если m ≡ 0 (mod q ) , m ^Эд кратно q . Так что м ^Эд ≡ 0 ≡ м (мод q ) .
2. Если М $\not \equiv$ 0 (мод q ) ,

   $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 ) )

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

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

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

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

$$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 ^{λ (н)} ≡ 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 и} ), результат m ^Это строго меньше модуля n . В этом случае зашифрованный текст можно легко расшифровать, взяв корень е -й степени из зашифрованного текста над целыми числами.
• Если одно и то же сообщение в открытом виде отправляется e или нескольким получателям в зашифрованном виде, и получатели имеют один и тот же показатель степени e , но разные p , q и, следовательно, n , то исходное сообщение в виде открытого текста легко расшифровать. с помощью китайской теоремы об остатках . Йохан Хостад заметил, что такая атака возможна, даже если открытые тексты не равны, но злоумышленник знает линейную связь между ними. Эта атака позже была улучшена Доном Копперсмитом (см. Атака Копперсмита ).
• Поскольку шифрование RSA представляет собой детерминированный алгоритм шифрования (т. е. не имеет случайного компонента), злоумышленник может успешно запустить атаку против криптосистемы с использованием выбранного открытого текста , зашифровав вероятные открытые тексты открытым ключом и проверив, равны ли они зашифрованному тексту. Криптосистема называется семантически безопасной, если злоумышленник не может отличить два шифрования друг от друга, даже если злоумышленник знает (или выбрал) соответствующие открытые тексты. RSA без заполнения не является семантически безопасным.
• RSA обладает тем свойством, что произведение двух зашифрованных текстов равно шифрованию произведения соответствующих открытых текстов. То есть м ₁ ^Это m_м2 ^Это ≡ ( м ₁ м ₂ ) ^Это (мод . н ) . Из-за этого мультипликативного свойства атака с использованием выбранного зашифрованного текста возможна . Например, злоумышленник, желающий узнать, как расшифровать зашифрованный текст, c ≡ m. ^Это (mod n ) может попросить владельца закрытого ключа d расшифровать не вызывающий подозрений зашифрованный текст c ′ ≡ cr ^Это (mod n ) для некоторого значения r, выбранного злоумышленником. Из-за мультипликативного свойства c ' является шифрованием mr (mod n ) . Следовательно, если атакующий преуспеет в атаке, он узнает mr (mod n ), из которого сможет получить сообщение m , умножив mr на модульное обратное значение r по модулю n .
• Учитывая частный показатель d , можно эффективно факторизовать модуль n = pq . А учитывая факторизацию модуля n = pq , можно получить любой закрытый ключ ( d ', n ), сгенерированный на основе открытого ключа ( e ', n ).

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

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

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

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

практические

китайского

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

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

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

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

RSA

См. также: RSA Factoring Challenge , Записи целочисленной факторизации и Алгоритм Шора.

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

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

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

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

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

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

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

В 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 .

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

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

Важность генерации

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

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

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

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

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

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

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

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

выбранного зашифрованного

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

Вариант этой атаки, получивший название «BERserk», появился еще в 2014 году. Это повлияло на криптобиблиотеку Mozilla NSS, которая, в частности, использовалась Firefox и Chrome.

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

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

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

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

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

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

Реализации

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

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

См. также

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

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

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

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

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