Войти
| Общие | |
|---|---|
| Дизайнеры | Рон Ривест, Ади Шамир и Леонард Адлеман |
| Впервые опубликовано | 1977 |
| Сертификат | PKCS # 1, IEEE 1363 |
| Детали шифра | |
| Размеры ключей | от 1024 до 4096 бит, типично |
| Раунды | 1 |
| Лучший публичный криптоанализ | |
| Сито общего числового поля для классических компьютеров;. Шора алгоритм для квантовых компьютеров.. Неисправен 829-битный ключ. | |
RSA (Ривест – Шамир – Адлеман ) - Криптосистема с открытым ключом, широко используемая для безопасной передачи данных. Он также является одним из старейших. Акроним RSA происходит от фамилий Рон Ривест, Ади Шамир и Леонард Адлеман, которые публично описал алгоритм в 1977 г. Эквивалентная система была тайно разработана в 1973 г. в GCHQ (британское агентство по разведке сигналов ) английским математиком Клиффордом Коксом. Эта система была рассекречена в 1997 году.
В криптосистеме с открытым ключом ключ шифрования является открытым и отличается от ключ дешифрования, который хранится в секрете (частном). Пользователь RSA создает и публикует открытый ключ на основе двух больших простых чисел, а также вспомогательного значения. Простые числа держатся в секрете. Сообщения могут быть зашифрованы с помощью открытого ключа, но могут быть декодированы только тем, кто знает простые числа.
Безопасность RSA зависит от практических трудностей факторизации продукта двух больших простых чисел, "проблема факторизации ". Нарушение шифрования RSA известно как проблема RSA. Является ли это столь же сложной задачей, как проблема факторинга, вопрос открытый. Нет опубликованных методов для выхода из строя системы, если используется достаточно большой ключ.
RSA - относительно медленный алгоритм. Из-за этого он обычно не используется для прямого шифрования пользовательских данных. Чаще RSA используется для передачи общих ключей для шифрования с симметричным ключом , которые затем используются для массового шифрования-дешифрования.
Ади Шамир, соавтор RSA (другие - Рон Ривест и Леонард Адлеман )Идея асимметричной криптосистемы с открытым и закрытым ключом принадлежит Уитфилду Диффи и Мартин Хеллман, опубликовавший эту концепцию в 1976 году. Они также ввели цифровые подписи и попытались применить теорию чисел. В их формулировке использовался общий секретный ключ, созданный возведением в степень некоторого числа по модулю простого числа. Однако они оставили открытой проблему реализации односторонней функции, возможно, потому что сложность факторизации в то время не была хорошо изучена.
Рон Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института в течение года предпринял несколько попыток создать одностороннюю функцию, которую было бы трудно обратить. Ривест и Шамир, как компьютерщики, предложили множество потенциальных функций, а Адлеман, как математик, отвечал за обнаружение их слабых мест. Они испробовали множество подходов, в том числе «на основе ранца » и «многочлены перестановок». Какое-то время они думали, что то, чего они хотят, невозможно из-за противоречивых требований. В апреле 1977 года они провели Песах в доме студента и выпили много вина Manischewitz, прежде чем вернуться домой около полуночи. Ривест, неспособный заснуть, лег на диван с учебником математики и начал думать об их односторонней функции. Он провел остаток ночи, формулируя свою идею, и к рассвету у него была готова большая часть бумаги. Алгоритм теперь известен как RSA - инициалы их фамилий в том же порядке, что и их статья.
Клиффорд Кокс, английский математик, работающий на британское разведывательное управление Правительственный штаб связи (GCHQ) описал эквивалентную систему во внутреннем документе в 1973 году. Однако, учитывая относительно дорогие компьютеры, необходимые для ее реализации в то время, это считалось в основном диковинкой и, поскольку насколько известно, никогда не был развернут. Однако его открытие не было раскрыто до 1997 года из-за его сверхсекретной классификации.
Kid-RSA (KRSA) - это упрощенный шифр с открытым ключом, опубликованный в 1997 году и предназначенный для образовательных целей. Некоторые люди считают, что изучение Kid-RSA дает представление о RSA и других шифрах с открытым ключом, аналогично упрощенному DES.
A патент, описывающий алгоритм RSA, был предоставлен MIT 20 сентября 1983 г.: США Патент 4,405,829 «Система и метод криптографической связи». Из выдержки из патента DWPI :
Система включает в себя канал связи, подключенный по меньшей мере к одному терминалу, имеющему устройство кодирования, и по меньшей мере к одному терминалу, имеющему устройство декодирования. Сообщение, которое должно быть передано, зашифровывается до зашифрованного текста на кодирующем терминале путем кодирования сообщения как числа M в заранее определенном наборе. Затем это число увеличивается до первой заданной мощности (связанной с предполагаемым приемником) и, наконец, вычисляется. Остаток или остаток C... вычисляется, когда возведенное в степень число делится на произведение двух заранее определенных простых чисел (связанных с предполагаемым получателем).
Подробное описание алгоритма было опубликовано в августе 1977 года в Столбец Mathematical Games журнала Scientific American. Это предшествовало дате подачи патента в декабре 1977 года. Следовательно, патент не имел юридической силы за пределами США. Если бы работа Кокса была широко известна, патент в Соединенных Штатах также был бы незаконным.
Когда был выдан патент, срок действия патента составлял 17 лет. Срок действия патента истекал 21 сентября 2000 г., когда 6 сентября 2000 г. RSA Security передала алгоритм в общественное достояние.
Алгоритм RSA включает четыре шага: ключ генерация, распределение ключей, шифрование и дешифрование.
Основным принципом RSA является наблюдение, что на практике можно найти три очень больших положительных целых числа e, d и n, такие, что с модульным возведением в степень для всех целых чисел m (с 0 ≤ m < n):
и зная e и n, или даже m, может быть чрезвычайно сложно найти d. тройная черта (≡) здесь обозначает модульное сравнение.
Кроме того, для некоторых операций удобно, чтобы порядок двух возведения в степень можно изменить, и это отношение также подразумевает:
RSA включает в себя открытый ключ и закрытый ключ. Открытый ключ может быть известен каждому, и он используется для шифрования сообщений. Предполагается, что сообщения, зашифрованные с помощью открытого ключа, могут быть расшифрованы только в разумное количество времени с использованием закрытого ключа. Открытый ключ представлен целыми числами n и e; и закрытый ключ целым числом d (хотя n также используется в процессе дешифрования. Таким образом, его можно также рассматривать как часть закрытого ключа). m представляет сообщение (предварительно подготовленное с помощью определенной техники, описанной ниже).
Ключи для алгоритма RSA генерируются следующим образом:
Открытый ключ состоит из модуля 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 может потребовать, чтобы d < λ(n). Any "oversized" private exponents not meeting that criterion may always be reduced modulo λ(n) to obtain a smaller equivalent exponent.
Поскольку любые общие множители (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 by using an agreed-upon reversible protocol known as a схема заполнения. Затем он вычисляет зашифрованный текст c, используя открытый ключ Алисы e, соответствующий
Это может быть выполняется достаточно быстро, даже для очень больших чисел, с использованием модульного возведения в степень. Затем Боб передает c Алисе.
Алиса может восстановить m из c, используя показатель степени своего секретного ключа d, вычислив
Учитывая m, она может восстановить исходное сообщение M, изменив схему заполнения.
Вот пример шифрования и дешифрования RSA. Используемые здесь параметры искусственно малы, но можно также использовать OpenSSL для генерации и проверки реальной пары ключей..
и 
открытый ключ (n = 3233, e = 17). Для сообщения m с заполненным открытым текстом функция шифрования:
закрытый ключ : (n = 3233, d = 413). Для зашифрованного зашифрованного текста c функция дешифрования:
Например, чтобы зашифровать m = 65, мы вычисляем
Чтобы расшифровать c = 2790, мы вычисляем
Оба эти вычисления могут быть эффективно вычислены с использованием алгоритма квадратного и умножения для модульного возведения в степень. В реальных жизненных ситуациях выбранные простые числа будут намного больше; в нашем примере было бы тривиально разложить n, 3233 (полученное из свободно доступного открытого ключа) обратно на простые числа p и q. e, также из открытого ключа, затем инвертируется, чтобы получить d, таким образом получая закрытый ключ.
В практических реализациях используется китайская теорема об остатках для ускорения вычислений с использованием модуля множителей (mod pq с использованием mod p и mod q).
Значения d p, d q и q inv, которые являются частью закрытого ключа, вычисляются следующим образом:
Вот как d p, d q и q inv используются для эффективного дешифрования. (Шифрование эффективно при выборе подходящей пары d и e)
Предположим, Алиса использует открытый ключ Боба, чтобы отправить ему зашифрованное сообщение. В сообщении она может заявить, что она Алиса, но Боб не имеет возможности проверить, действительно ли сообщение было от Алисы, поскольку любой может использовать открытый ключ Боба для отправки ему зашифрованных сообщений. Чтобы проверить источник сообщения, RSA может также использоваться для подписи сообщения.
Предположим, Алиса хочет отправить подписанное сообщение Бобу. Для этого она может использовать свой закрытый ключ. Она создает хэш-значение сообщения, возводит его в степень d (по модулю n) (как она это делает при дешифровании сообщения) и прикрепляет его как «подпись» к сообщению. Когда Боб получает подписанное сообщение, он использует тот же алгоритм хеширования в сочетании с открытым ключом Алисы. Он возводит подпись в степень e (по модулю n) (как он это делает при шифровании сообщения) и сравнивает полученное значение хеш-функции с фактическим значением хеш-функции сообщения. Если они согласны, он знает, что автор сообщения владел закрытым ключом Алисы и что с тех пор сообщение не подвергалось подделке.
Это работает из-за правил возведения в степень :
Таким образом, ключи можно менять местами без потерь Вообще говоря, закрытый ключ пары ключей может использоваться либо для:
Доказательство правильности RSA основано на маленькой теореме Ферма, утверждающей что a ≡ 1 (mod p) для любого целого числа a и простого числа p, не делящего a.
Мы хотим показать, что
для любого целого числа m, когда p и q - различные простые числа, а e и d - натуральные числа, удовлетворяющие ed ≡ 1 (mod λ (pq)).
Поскольку λ (pq) = lcm (p - 1, q - 1) по построению делится как на p - 1, так и на q - 1, мы можем написать
для некоторых неотрицательных целых чисел h и k.
Чтобы проверить, совпадают ли два числа, например, m и m, по модулю pq, достаточно (и фактически эквивалентно) проверить, что они совпадают по модулю p и по модулю q по отдельности.
Чтобы показать m ≡ m (mod p), мы рассмотрим два случая:
0 (mod p),
Проверка того, что m ≡ m (mod q) проходит совершенно аналогичным образом:
0 (mod q),
Это завершает доказательство того, что для любого целого m и целых e, d таких, что ed ≡ 1 (mod λ (pq)),
Примечания:
Хотя оригинал В статье Ривеста, Шамира и Адлемана для объяснения того, почему работает RSA, использовалась небольшая теорема Ферма, часто встречаются доказательства, которые вместо этого полагаются на теорему Эйлера.
Мы хотим показать, что m ≡ m (mod n), где n = pq - произведение двух разных простых чисел, а e и d - натуральные числа, удовлетворяющие ed ≡ 1 (mod φ (n)). Поскольку e и d положительны, мы можем записать ed = 1 + hφ (n) для некоторого неотрицательного целого числа h. Предполагая, что m взаимно просто с 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 обычно включают некоторую форму структурированного, рандомизированного заполнения в значение 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 (USPTO 6266771 и USPTO 70360140); однако срок действия этих патентов истек 24 июля 2009 г. и 25 апреля 2010 г. соответственно. Использование PSS больше не ограничивается патентами. Обратите внимание, что использование разных пар ключей RSA для шифрования и подписи потенциально более безопасно.
Для повышения эффективности многие популярные криптографические библиотеки (например, OpenSSL, Java и .NET ) используйте следующую оптимизацию для дешифрования и подписи на основе китайской теоремы об остатках. Следующие значения предварительно вычисляются и сохраняются как часть закрытого ключа:
и 
: простые числа из генерация ключа,
,
и
.Эти значения позволяют получателю более эффективно вычислять возведение в степень m = c (mod pq) следующим образом:
(если 
Это более эффективно, чем вычисление возведения в степень возведением в квадрат, даже если необходимо вычислить два модульных возведения в степень. Причина в том, что оба этих модульных возведения в степень используют меньший показатель степени и меньший модуль.
Безопасность криптосистемы RSA основана на двух математических задачах: проблеме разложения больших чисел и проблеме RSA. Считается, что полное дешифрование зашифрованного текста RSA невозможно при условии, что обе эти проблемы являются сложными, то есть не существует эффективного алгоритма для их решения. Обеспечение защиты от частичного дешифрования может потребовать добавления безопасной схемы заполнения .
. Проблема RSA определяется как задача взятия корней eth по модулю составного 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 г. использовала сотни компьютеров и потребовала 8 400 операций в секунду в год за время, прошедшее около семи месяцев. К 2009 году Бенджамин Муди мог разложить ключ RSA-512 бит за 73 дня, используя только общедоступное программное обеспечение (GGNFS) и свой настольный компьютер (двухъядерный Athlon64 с процессором 1900 МГц). Для процесса просеивания требовалось чуть менее пяти гигабайт дисковой памяти и около 2,5 гигабайт оперативной памяти.
Ривест, Шамир и Адлеман отметили, что Миллер показал, что - при условии истинности расширенной гипотезы Римана - найти d из n и e так же сложно, как разложить n на p и q (с точностью до полиномиальной разницы во времени). Однако Ривест, Шамир и Адлеман отметили в разделе IX / D своей статьи, что они не нашли доказательства того, что инвертирование RSA так же сложно, как факторизация.
По состоянию на 2020 год самый большой общеизвестный факторный номер RSA составлял 829 бит (250 десятичных цифр, RSA-250 ). Его факторизация с помощью современной распределенной реализации заняла около 2700 процессорных лет. На практике ключи RSA обычно имеют длину от 1024 до 4096 бит. RSA Security полагал, что к 2010 году 1024-битные ключи, скорее всего, станут поддающимися взлому; по состоянию на 2020 год неизвестно, было ли это так, но минимальные рекомендации перешли как минимум на 2048 бит. Обычно предполагается, что RSA безопасен, если n достаточно велико, за пределами квантовых вычислений.
Если n равно 300 бит или меньше, его можно разложить на множители за несколько часов на персональном компьютере, используя уже свободно доступное программное обеспечение. Ключи из 512 битов показали, что их можно практически взломать в 1999 году, когда RSA-155 был разложен на несколько сотен компьютеров, а теперь они разложены за несколько недель с использованием обычного оборудования. В 2011 году сообщалось об эксплойтах с использованием 512-битных сертификатов подписи кода, которые могли быть учтены. Теоретическое аппаратное устройство с именем TWIRL, описанное Шамиром и Тромером в 2003 году, поставило под сомнение безопасность 1024-битных ключей.
В 1994 году Питер Шор показал, что квантовый компьютер - если его когда-либо можно будет практически создать для этой цели - сможет учитывать полином . время, нарушение RSA; см. алгоритм Шора.
Нахождение больших простых чисел p и q обычно выполняется путем тестирования случайных чисел нужного размера с помощью вероятностных тестов на простоту, которые быстро устраняют виртуальные все непростые.
Числа p и q не должны быть "слишком близкими", иначе факторизация Ферма для n будет успешной. Если p - q меньше 2n (n = p * q, что даже для небольших 1024-битных значений n составляет 3 × 10), решение для p и q тривиально. Кроме того, если либо p - 1, либо q - 1 имеет только маленькие простые множители, n можно быстро разложить на множители алгоритмом p - 1 Полларда, и, следовательно, такие значения p или q должны быть отброшены.
Важно, чтобы частный показатель d был достаточно большим. показал, что если p находится между q и 2q (что довольно типично) и d < n/3, then d can be computed efficiently from n and 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 ′), то простое вычисление gcd (n, n ′) = p множители как n, так и n ′, полностью скомпрометировав оба ключа. Lenstra et al. обратите внимание, что эту проблему можно минимизировать, используя сильное случайное начальное число битовой длины, вдвое превышающей предполагаемый уровень безопасности, или используя детерминированную функцию для выбора q при заданном p вместо выбора p и q независимо.
Надя Хенингер была частью группы, которая провела аналогичный эксперимент. Они использовали идею Дэниела Дж. Бернштейна для вычисления GCD каждого ключа RSA n относительно произведения всех других ключей n ', которые они нашли (729 число миллионов цифр), вместо того, чтобы вычислять каждый НОД (n, n ') отдельно, тем самым достигая очень значительного ускорения, поскольку после одного большого деления проблема НОД имеет нормальный размер.
Хенингер говорит в своем блоге, что плохие ключи почти полностью возникли во встроенных приложениях, включая «межсетевые экраны, маршрутизаторы, устройства VPN, устройства удаленного администрирования серверов, принтеры, проекторы и телефоны VOIP» от более чем 30 производителей. Хенингер объясняет, что проблема одного общего простого числа, обнаруженная двумя группами, является результатом ситуаций, когда генератор псевдослучайных чисел изначально плохо загружается, а затем повторно заполняется между генерацией первого и второго простых чисел. Использование начальных чисел с достаточно высокой энтропией, полученной из таймингов нажатия клавиш или шума электронных диодов или атмосферного шума от радиоприемника, настроенного между станциями, должно решить проблему.
Генерация сильных случайных чисел важна во всех этап криптографии с открытым ключом. Например, если для симметричных ключей, распространяемых RSA, используется слабый генератор, то перехватчик может обойти RSA и напрямую угадать симметричные ключи.
Кохер описал новую атаку на RSA в 1995 году: если злоумышленник Ева знает оборудование Алисы достаточно подробно и может измерить время дешифрования для нескольких известных шифровальных текстов, Ева может сделать выводы ключ дешифрования d быстро. Эта атака также может быть применена против схемы подписи RSA. В 2003 году Boneh и Brumley продемонстрировали более практичную атаку, способную восстанавливать факторизации RSA через сетевое соединение (например, из Secure Sockets Layer (SSL) - включен веб-сервер) Эта атака использует информацию, просочившуюся из китайской теоремы об остатках оптимизации, используемой многими реализациями RSA.
Один из способов предотвратить эти атаки - убедиться, что операция дешифрования занимает постоянное количество времени для каждого зашифрованного текста. Однако такой подход может значительно снизить производительность. Вместо этого в большинстве реализаций RSA используется альтернативный метод, известный как криптографическое ослепление. Ослепление RSA использует мультипликативное свойство RSA. Вместо вычисления c (mod n) Алиса сначала выбирает секретное случайное значение r и вычисляет (rc) (mod n). Результатом этого вычисления после применения теоремы Эйлера будет rc (mod n), поэтому влияние r может быть устранено умножением на обратное. Для каждого зашифрованного текста выбирается новое значение r. При применении ослепления время дешифрования больше не коррелирует со значением входного зашифрованного текста, и поэтому временная атака терпит неудачу.
В 1998 году Даниэль Блейхенбахер описал первую практическую адаптивную атаку с выбранным шифротекстом на сообщения, зашифрованные RSA, с использованием PKCS # 1 v1 схема заполнения (схема заполнения рандомизирует и добавляет структуру к зашифрованному RSA сообщению, чтобы можно было определить, является ли расшифрованное сообщение действительным). Из-за недостатков схемы PKCS # 1 Блейхенбахер смог провести практическую атаку на реализации RSA протокола Secure Socket Layer и восстановить ключи сеанса. В результате этой работы криптографы теперь рекомендуют использовать доказанно безопасные схемы заполнения, такие как Optimal Asymmetric Encryption Padding, а RSA Laboratories выпустила новые версии PKCS # 1, которые не уязвимы для этих атак.
Описана атака побочного канала с использованием анализа предсказания ветвления (BPA). Многие процессоры используют предсказатель ветвления , чтобы определить, будет ли условный переход в потоке команд программы вероятен или нет. Часто эти процессоры также реализуют одновременную многопоточность (SMT). Атаки с анализом предсказания ветвления используют шпионский процесс для обнаружения (статистически) закрытого ключа при обработке этими процессорами.
Simple Branch Prediction Analysis (SBPA) утверждает, что улучшает BPA нестатистическим способом. В своей статье «О силе простого анализа предсказания ветвлений» авторы SBPA (и) утверждают, что обнаружили 508 из 512 бит ключа RSA за 10 итераций.
Атака сбоя питания на реализациях RSA была описана в 2010 году. Автор восстановил ключ, изменив напряжение питания процессора вне пределов; это вызвало несколько сбоев питания на сервере.
Некоторые криптографические библиотеки, обеспечивающие поддержку RSA, включают:
Портал математики 