RSA ( Ривест-Шамир-Адлеман ) — криптосистема с открытым ключом , одна из старейших, широко используемых для безопасной передачи данных. Инициализм «RSA» происходит от фамилий Рона Ривеста , Ади Шамира и Леонарда Адлемана , которые публично описали алгоритм в 1977 году. Эквивалентная система была тайно разработана в 1973 году в штаб - квартире правительственной связи (GCHQ), британском агентстве радиотехнической разведки , английский математик Клиффорд Кокс . Эта система была рассекречена в 1997 году. [2]
В криптосистеме с открытым ключом ключ шифрования является общедоступным и отличается от ключа дешифрования , который хранится в секрете (частном). Пользователь RSA создает и публикует открытый ключ на основе двух больших простых чисел вместе со вспомогательным значением. Простые числа держатся в секрете. Сообщения могут быть зашифрованы кем угодно с помощью открытого ключа, но могут быть декодированы только тем, кто знает закрытый ключ. [1]
Безопасность RSA основана на практической трудности факторизации произведения двух больших простых чисел , « проблеме факторизации ». Нарушение шифрования RSA известно как проблема RSA . Так ли это сложно, как проблема факторинга – вопрос открытый. [3] Не существует опубликованных методов взлома системы при использовании достаточно большого ключа.
RSA — относительно медленный алгоритм. По этой причине он обычно не используется для прямого шифрования пользовательских данных. Чаще всего RSA используется для передачи общих ключей для криптографии с симметричными ключами , которые затем используются для массового шифрования-дешифрования.
Идея асимметричной криптосистемы с открытым и закрытым ключами приписывается Уитфилду Диффи и Мартину Хеллману , которые опубликовали эту концепцию в 1976 году. Они также представили цифровые подписи и попытались применить теорию чисел. В их формулировке использовался общий секретный ключ, созданный путем возведения в степень некоторого числа по модулю простого числа. Однако они оставили открытой проблему реализации односторонней функции, возможно, потому, что сложность факторинга в то время не была хорошо изучена. [4]
Рон Ривест , Ади Шамир и Леонард Адлеман из Массачусетского технологического института в течение года предприняли несколько попыток создать функцию, которую трудно инвертировать. Ривест и Шамир, как ученые-компьютерщики, предложили множество потенциальных функций, а Адлеман, как математик, отвечал за обнаружение их слабых мест. Они испробовали множество подходов, в том числе « рюкзачный » и «полиномы перестановок». Какое-то время они думали, что желаемое невозможно из-за противоречивых требований. [5] В апреле 1977 года они отпраздновали Песах в доме студента и выпили много вина, прежде чем вернуться домой около полуночи. [6] Ривест, не в силах уснуть, лег на диван с учебником по математике и начал думать об их односторонней функции. Остаток ночи он провел, формализуя свою идею, и к рассвету у него была готова большая часть статьи. Алгоритм теперь известен как RSA — инициалы их фамилий расположены в том же порядке, что и их статья. [7]
Клиффорд Кокс , английский математик , работавший в штаб-квартире правительственных коммуникаций (GCHQ) британской разведки , описал аналогичную систему во внутреннем документе в 1973 году. [8] Однако, учитывая относительно дорогие компьютеры, необходимые для ее реализации в то время, это было считался в основном диковинкой и, насколько известно, никогда не использовался. Его идеи и концепции не были раскрыты до 1997 года из-за своей совершенно секретной классификации.
Kid-RSA (KRSA) — это упрощенный небезопасный шифр с открытым ключом, опубликованный в 1997 году и предназначенный для образовательных целей. Некоторые люди считают, что изучение Kid-RSA дает представление о RSA и других шифрах с открытым ключом, аналогичных упрощенному DES . [9] [10] [11] [12] [13]
Патент , описывающий алгоритм RSA, был выдан Массачусетскому технологическому институту 20 сентября 1983 года: патент США 4 405 829 «Система и метод криптографической связи». Из реферата патента DWPI :
Система включает в себя канал связи, соединенный по меньшей мере с одним терминалом, имеющим устройство кодирования, и, по меньшей мере, с одним терминалом, имеющим устройство декодирования. Сообщение, подлежащее передаче, шифруется в зашифрованный текст на терминале кодирования путем кодирования сообщения как числа М в заранее определенном наборе. Затем это число возводится в первую заранее определенную степень (связанную с предполагаемым приемником) и, наконец, вычисляется. Остаток или вычет C... вычисляется, когда возведенное в степень число делится на произведение двух заранее определенных простых чисел (связанных с предполагаемым получателем).
Подробное описание алгоритма было опубликовано в августе 1977 года в колонке журнала Scientific American « Математические игры» . [7] Это предшествовало дате подачи патента в декабре 1977 года. Следовательно, патент не имел юридической силы за пределами Соединенных Штатов . Если бы работа Кокса была широко известна, патент в Соединенных Штатах также не был бы законным.
На момент выдачи патента срок действия патента составлял 17 лет. Срок действия патента истекал 21 сентября 2000 г., но 6 сентября 2000 г. RSA Security опубликовала алгоритм в открытом доступе. [14]
Алгоритм RSA включает четыре этапа: генерацию ключей , распределение ключей, шифрование и дешифрование.
Основным принципом RSA является наблюдение о том, что практично найти три очень больших положительных целых числа e , d и n , такие, что с модульным возведением в степень для всех целых чисел m (при 0 ≤ m < n ):
и что, зная e и n или даже m , найти d может быть крайне сложно . Здесь символ ≡ обозначает модульное сравнение : т.е. оба ( m e ) d и m имеют одинаковый остаток при делении на n .
Кроме того, для некоторых операций удобно менять порядок двух возведений в степень: из предыдущего соотношения также следует
RSA включает в себя открытый ключ и закрытый ключ . Открытый ключ может быть известен каждому и используется для шифрования сообщений. Цель состоит в том, чтобы сообщения, зашифрованные открытым ключом, можно было расшифровать только за разумное время с использованием закрытого ключа. Открытый ключ представлен целыми числами n и e , а закрытый ключ — целым числом d (хотя n также используется в процессе расшифровки, поэтому его также можно рассматривать как часть закрытого ключа). m представляет сообщение (ранее подготовленное с помощью определенной техники, описанной ниже).
Ключи для алгоритма RSA генерируются следующим образом:
Открытый ключ состоит из модуля 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 , соответствующий
Это можно сделать достаточно быстро, даже для очень больших чисел, используя модульное возведение в степень . Затем Боб передает c Алисе. Обратите внимание, что по крайней мере девять значений m дадут зашифрованный текст c, равный m , [a] , но на практике это маловероятно.
Алиса может восстановить m из c , используя показатель степени своего секретного ключа d , вычислив
Учитывая m , она может восстановить исходное сообщение M , изменив схему заполнения.
Вот пример шифрования и дешифрования RSA: [b]
Открытый ключ : ( 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 ) (как она делает при расшифровке сообщения) и присоединяет его как «подпись» к сообщению. Когда Боб получает подписанное сообщение, он использует тот же алгоритм хеширования в сочетании с открытым ключом Алисы. Он возводит подпись в степень е (по модулю n ) (как он это делает при шифровании сообщения) и сравнивает полученное значение хеш-функции с значением хеш-функции сообщения. Если они согласны, он знает, что автор сообщения владел секретным ключом Алисы и что с момента отправки сообщение не подвергалось манипуляциям.
Это работает благодаря правилам возведения в степень :
Таким образом, ключи можно менять местами без потери общности, то есть закрытый ключ пары ключей может использоваться либо для:
Доказательство правильности RSA основано на маленькой теореме Ферма , утверждающей, что a p − 1 ≡ 1 (mod p ) для любого целого числа a и простого числа p , не делящего a . [примечание 1]
Мы хотим показать это
Поскольку λ ( pq ) = lcm ( p − 1, q − 1) по построению делится как на p − 1 , так и на q − 1 , мы можем написать
Чтобы проверить, конгруэнтны ли два числа, такие как m ed и m , по модулю pq , достаточно (и фактически эквивалентно) проверить, что они конгруэнтны по модулю p и по модулю q отдельно. [заметка 3]
Чтобы показать, что m ed ≡ m (mod p ) , рассмотрим два случая:
Проверка того, что m ed ≡ m (mod q ), происходит совершенно аналогично:
Это завершает доказательство того, что для любого целого числа m и целых чисел e , d таких, что ed ≡ 1 (mod λ ( pq ))
Хотя в оригинальной статье Ривеста, Шамира и Адлемана для объяснения того, почему работает RSA, использовалась маленькая теорема Ферма, часто встречаются доказательства, которые вместо этого полагаются на теорему Эйлера .
Мы хотим показать, что m ed ≡ 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 λ (n) ≡ 1 (mod n ) для всех m относительно простых к н .
Когда 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. [25] показали, что для некоторых типов сообщений такое заполнение не обеспечивает достаточно высокий уровень безопасности. Более поздние версии стандарта включают Optimal Asymmetric Encryption Padding (OAEP), который предотвращает эти атаки. Таким образом, OAEP следует использовать в любом новом приложении, а заполнение PKCS#1 v1.5 следует заменять везде, где это возможно. Стандарт PKCS#1 также включает схемы обработки, предназначенные для обеспечения дополнительной безопасности подписей RSA, например, схему вероятностной подписи для RSA ( RSA-PSS ).
Схемы безопасного заполнения, такие как RSA-PSS, столь же важны для безопасности подписи сообщений, как и для шифрования сообщений. Получены два патента США на PSS ( патент США 6 266 771 и патент США 7 036 014 ); однако срок действия этих патентов истек 24 июля 2009 г. и 25 апреля 2010 г. соответственно. Использование PSS больше не обременено патентами. [ оригинальное исследование? ] Обратите внимание, что использование разных пар ключей RSA для шифрования и подписи потенциально более безопасно. [26]
В целях эффективности многие популярные криптобиблиотеки (такие как OpenSSL , Java и .NET ) используют для расшифровки и подписи следующую оптимизацию, основанную на китайской теореме об остатках . [ нужна цитация ] Следующие значения предварительно вычисляются и сохраняются как часть закрытого ключа:
Эти значения позволяют получателю более эффективно вычислять возведение в степень m = c d (mod pq ) следующим образом: , , , [c] .
Это более эффективно, чем вычисление возведения в степень возведением в степень , хотя необходимо вычислить два модульных возведения в степень. Причина в том, что эти два модульных возведения в степень используют меньший показатель степени и меньший модуль.
Безопасность криптосистемы RSA основана на двух математических проблемах: проблеме факторизации больших чисел и проблеме RSA . Полная расшифровка зашифрованного текста RSA считается невозможной при условии, что обе эти проблемы сложны , т. е. не существует эффективного алгоритма для их решения. Обеспечение защиты от частичного дешифрования может потребовать добавления схемы безопасного заполнения . [27]
Проблема RSA определяется как задача извлечения корней e -й степени по модулю составного n : восстановление значения m такого, что c ≡ me (mod n ) , где ( n , e ) — открытый ключ RSA, а c — RSA. зашифрованный текст. В настоящее время наиболее перспективным подходом к решению проблемы RSA является факторизация модуля n . Имея возможность восстанавливать простые множители, злоумышленник может вычислить секретный показатель степени d из открытого ключа ( n , e ) , а затем расшифровать c, используя стандартную процедуру. Для этого злоумышленник факторизует n на p и q и вычисляет lcm( p − 1, q − 1) , что позволяет определить d по e . Никакого полиномиального метода факторизации больших целых чисел на классическом компьютере еще не найдено, но не доказано, что его существует; см. целочисленную факторизацию для обсуждения этой проблемы.
Множественное полиномиальное квадратичное сито (MPQS) можно использовать для факторизации общедоступного модуля n .
Первая факторизация RSA-512 в 1999 году использовала сотни компьютеров и потребовала эквивалентно 8400 MIPS-лет в течение примерно семи месяцев. [28] К 2009 году Бенджамин Муди мог получить 512-битный ключ RSA за 73 дня, используя только общедоступное программное обеспечение (GGNFS) и свой настольный компьютер (двухъядерный Athlon64 с процессором 1900 МГц). Для процесса просеивания требовалось чуть менее 5 гигабайт дискового пространства и около 2,5 гигабайт оперативной памяти.
Ривест, Шамир и Адлеман отметили [1] , что Миллер показал, что – при условии истинности расширенной гипотезы Римана – найти d из n и e так же сложно, как разложить n на p и q (с точностью до полиномиальной разницы во времени). [29] Однако Ривест, Шамир и Адлеман отметили в разделе IX/D своей статьи, что они не нашли доказательства того, что инвертирование RSA так же сложно, как факторизация.
По состоянию на 2020 год [update]самое большое общеизвестное факторизованное число RSA имело 829 бит (250 десятичных цифр, RSA-250 ). [30] Его факторизация с помощью современной распределенной реализации заняла около 2700 процессоро-лет. На практике ключи RSA обычно имеют длину от 1024 до 4096 бит. В 2003 году компания RSA Security подсчитала, что 1024-битные ключи, скорее всего, станут взломанными к 2010 году. [31] По состоянию на 2020 год неизвестно, можно ли взломать такие ключи, но минимальные рекомендации изменены как минимум на 2048 бит. [32] Обычно предполагается, что RSA безопасен, если n достаточно велико, за пределами квантовых вычислений.
Если n равно 300 битам или меньше, его можно посчитать за несколько часов на персональном компьютере , используя уже свободно доступное программное обеспечение. В 1999 году было показано, что 512-битные ключи практически можно взломать, когда RSA-155 был факторизован с использованием нескольких сотен компьютеров, а теперь они анализируются за несколько недель с использованием обычного оборудования. В 2011 году сообщалось об эксплойтах с использованием 512-битных сертификатов подписи кода, которые могли быть учтены. [33] Теоретическое аппаратное устройство под названием TWIRL , описанное Шамиром и Тромером в 2003 году, поставило под сомнение безопасность 1024-битных ключей. [31]
В 1994 году Питер Шор показал, что квантовый компьютер – если он когда-либо будет практически создан для этой цели – сможет учитывать полиномиальное время , нарушая RSA; см. алгоритм Шора .
Нахождение больших простых чисел p и q обычно осуществляется путем проверки случайных чисел правильного размера с помощью вероятностных тестов на простоту , которые быстро исключают практически все непростые числа.
Числа p и q не должны быть «слишком близкими», иначе факторизация Ферма для n будет успешной. Если p − q меньше 2 n 1/4 ( n = p ⋅ q , что даже для «маленьких» 1024-битных значений n равно3 × 10 77 ), решение для p и q тривиально. Более того, если либо p - 1 , либо q - 1 имеет только небольшие простые множители, n можно быстро факторизовать с помощью алгоритма Полларда p - 1 , и, следовательно, такие значения p или q следует отбросить.
Важно, чтобы частный показатель d был достаточно большим. Майкл Дж. Винер показал, что если p находится между q и 2 q (что вполне типично) и d < n 1/4 /3 , то d можно эффективно вычислить из n и e . [34]
Не существует известных атак на небольшие общедоступные показатели степени, такие как e = 3 , при условии, что используется правильное заполнение. Атака Копперсмита имеет множество применений для атаки на RSA, особенно если общедоступный показатель e мал и если зашифрованное сообщение короткое и не дополнено. 65537 — обычно используемое значение e ; это значение можно рассматривать как компромисс между предотвращением потенциальных атак с малым показателем и обеспечением эффективного шифрования (или проверки подписи). Специальная публикация NIST по компьютерной безопасности (SP 800-78, ред. 1, август 2007 г.) не допускает общедоступных показателей e меньше 65537, но не указывает причину этого ограничения.
В октябре 2017 года группа исследователей из Университета Масарика объявила об уязвимости ROCA , которая затрагивает ключи RSA, генерируемые алгоритмом, воплощенным в библиотеке от Infineon , известной как RSALib. Было выявлено, что уязвимо большое количество смарт-карт и доверенных платформенных модулей (TPM). Уязвимые ключи RSA легко идентифицируются с помощью тестовой программы, выпущенной командой. [35]
Для генерации простых чисел p и q необходимо использовать криптостойкий генератор случайных чисел , который правильно засеян адекватной энтропией . Анализ, сравнивающий миллионы открытых ключей, собранных из Интернета, был проведен в начале 2012 года Арьеном К. Ленстрой , Джеймсом П. Хьюзом, Максимом Ожье, Йоппе В. Босом, Торстеном Кляйнджунгом и Кристофом Вахтером. Им удалось факторизовать 0,2% ключей, используя только алгоритм Евклида. [36] [37] [ собственный источник? ]
Они воспользовались слабостью, уникальной для криптосистем, основанной на факторизации целых чисел. Если n = pq — один открытый ключ, а n ’ = p ’ q ’ — другой, то если случайно p = p ’ (но q не равно q ’), то простое вычисление НОД( n , n ′ ) = p учитывает как n , так и n ', полностью ставя под угрозу оба ключа. Ленстра и др. Обратите внимание, что эту проблему можно свести к минимуму, используя сильное случайное начальное число с битовой длиной, вдвое превышающей предполагаемый уровень безопасности, или используя детерминированную функцию для выбора q при заданном p вместо независимого выбора p и q .
Надя Хенингер была частью группы, проводившей аналогичный эксперимент. Они использовали идею Дэниела Дж. Бернштейна для вычисления НОД каждого ключа RSA n по произведению всех остальных ключей n ', которые они нашли (число из 729 миллионов цифр), вместо вычисления каждого НОД( n , n ′) отдельно, тем самым достигается весьма существенное ускорение, поскольку после одного большого деления задача НОД имеет нормальный размер.
Хенингер говорит в своем блоге, что неверные ключи почти полностью встречаются во встроенных приложениях, включая «брандмауэры, маршрутизаторы, VPN-устройства, устройства удаленного администрирования серверов, принтеры, проекторы и VOIP-телефоны» от более чем 30 производителей. Хенингер объясняет, что проблема одного общего простого числа, обнаруженная двумя группами, возникает в результате ситуаций, когда генератор псевдослучайных чисел изначально плохо заполняется, а затем повторно заполняется между генерацией первого и второго простых чисел. Использование начальных значений достаточно высокой энтропии, полученных из тайминга нажатия клавиш или шума электронных диодов или атмосферного шума радиоприемника, настроенного между станциями, должно решить проблему. [38]
Генерация сильных случайных чисел важна на каждом этапе криптографии с открытым ключом. Например, если для симметричных ключей, распространяемых RSA, используется слабый генератор, то злоумышленник может обойти RSA и напрямую угадать симметричные ключи.
Кохер описал новую атаку на RSA в 1995 году: если злоумышленник Ева достаточно подробно знает аппаратное обеспечение Алисы и сможет измерить время расшифровки для нескольких известных зашифрованных текстов, Ева сможет быстро определить ключ расшифровки d . Эту атаку также можно применить против схемы подписи RSA. В 2003 году Боне и Брамли продемонстрировали более практичную атаку, способную восстанавливать факторизации RSA через сетевое соединение (например, с веб-сервера с поддержкой Secure Sockets Layer (SSL)). [39] Эта атака использует информацию, утекшую в результате китайской оптимизации теоремы об остатках , используемой во многих реализациях RSA.
Один из способов предотвратить эти атаки — обеспечить, чтобы операция расшифровки занимала постоянное количество времени для каждого зашифрованного текста. Однако такой подход может существенно снизить производительность. Вместо этого в большинстве реализаций RSA используется альтернативный метод, известный как криптографическое ослепление . Ослепление RSA использует мультипликативное свойство RSA. Вместо вычисления c d (mod n ) Алиса сначала выбирает секретное случайное значение r и вычисляет ( re c ) d (mod n ) . Результатом этого вычисления после применения теоремы Эйлера будет rc d (mod n ) , и поэтому влияние r можно устранить, умножив его на обратное. Для каждого зашифрованного текста выбирается новое значение r . При применении ослепления время расшифровки больше не коррелирует со значением входного зашифрованного текста, и поэтому временная атака терпит неудачу.
В 1998 году Дэниел Блейхенбахер описал первую практическую адаптивную атаку с выбранным зашифрованным текстом против сообщений, зашифрованных RSA, с использованием схемы заполнения PKCS # 1 v1 (схема заполнения рандомизирует и добавляет структуру к сообщению, зашифрованному RSA, поэтому можно определить, является ли расшифрованное сообщение действительно). Из-за недостатков схемы PKCS #1 Блейхенбахер смог провести практическую атаку на реализации RSA протокола Secure Sockets Layer и восстановить ключи сеанса. В результате этой работы криптографы теперь рекомендуют использовать доказуемо безопасные схемы заполнения, такие как Optimal Asymmetric Encryption Padding , а RSA Laboratories выпустила новые версии PKCS #1, которые не уязвимы для этих атак.
Вариант этой атаки, получивший название «BERserk», появился еще в 2014 году. [40] [41] Он затронул криптобиблиотеку Mozilla NSS, которая, в частности, использовалась Firefox и Chrome.
Описана атака по побочному каналу с использованием анализа прогнозирования ветвей (BPA). Многие процессоры используют предсказатель ветвления , чтобы определить, будет ли выполнен условный переход в потоке команд программы или нет. Часто эти процессоры также реализуют одновременную многопоточность (SMT). Атаки с анализом предсказания ветвей используют шпионский процесс для обнаружения (статистического) закрытого ключа при обработке этими процессорами.
Простой анализ прогнозирования ветвей (SBPA) утверждает, что улучшает BPA нестатистическим способом. В своей статье «О возможностях простого анализа предсказания ветвей» [42] авторы SBPA (Онур Аджикмез и Четин Кая Коч) утверждают, что обнаружили 508 из 512 битов ключа RSA за 10 итераций.
Атака по сбою питания на реализации RSA была описана в 2010 году. [43] [ самостоятельно опубликованный источник? ] Автор восстановил ключ, изменив напряжение питания процессора за пределами допустимых пределов; это вызвало множественные сбои питания на сервере.
Чтобы безопасно реализовать RSA, необходимо учитывать множество деталей (сильный PRNG , приемлемый публичный показатель и т. д.). Это усложняет реализацию, вплоть до того, что в книге «Практическая криптография с Go» предлагается по возможности избегать RSA. [44]
Некоторые библиотеки шифрования, обеспечивающие поддержку RSA, включают: