Атака Винера
, Атака Винера названная в честь криптолога Майкла Дж. Винера, представляет собой разновидность криптографической атаки на RSA . Атака использует метод непрерывной дроби , чтобы раскрыть секретный ключ d, когда d мал.
Общие сведения о RSA
[ редактировать ]Вымышленные персонажи Алиса и Боб — люди, которые хотят безопасно общаться. Точнее, Алиса хочет отправить Бобу сообщение, которое сможет прочитать только Боб. Сначала Боб выбирает два секретных простых числа p и q . RSA Затем он вычисляет модуль N = pq . Этот модуль RSA публикуется вместе с степени шифрования показателем e . N и e образуют пару открытых ключей ( e , N ) . Сделав эту информацию общедоступной, любой сможет зашифровать сообщения Бобу. Показатель дешифрования λ d удовлетворяет условию ed ≡ 1 (mod λ ( N )) где используется φ ( N ) обозначает функцию Кармайкла , хотя иногда , ( N ), функция тотента Эйлера (примечание: это порядок мультипликативной группа ( Z / N Z ) × , которая не обязательно является циклической группой). Экспоненты шифрования e и λ ( N ) также должны быть взаимно простыми , чтобы существовала модулярная инверсия . Факторизация d N может и закрытый ключ расшифровать хранятся в секрете, так что только Боб сообщение . Мы обозначаем пару секретных ключей как ( d , N ) . Шифрование сообщения M определяется формулой C ≡ M. и (mod N ) , а расшифровка зашифрованного текста C определяется C д ≡ ( М и ) д ≡ М Эд ≡ M (mod N ) (с использованием малой теоремы Ферма ).
Используя алгоритм Евклида , можно эффективно восстановить секретный ключ , известна факторизация N. d если Имея секретный ключ d , можно эффективно факторизовать N. модуль [ 1 ]
Маленький закрытый ключ
[ редактировать ]В криптосистеме RSA Боб мог бы использовать небольшое значение d , а не большое случайное число, чтобы улучшить RSA производительность дешифрования . Однако атака Винера показывает, что выбор небольшого значения d приведет к созданию небезопасной системы, в которой злоумышленник сможет восстановить всю секретную информацию, т. е. взломать систему RSA . Этот разрыв основан на теореме Винера, которая справедлива для малых значений d . Винер доказал, что злоумышленник может эффективно найти d, когда d < 1 / 3 N 1/4 . [ 2 ]
В статье Винера также представлены некоторые контрмеры против его атаки, которые позволяют быстро расшифровать. Ниже описаны два метода.
Выбор большого открытого ключа : Замените e на e ′, где e ′ = e + k ⋅ λ ( N ) для некоторого большого числа k . Когда e ′ достаточно велико, т.е. e ′ > N 3/2 , то атака Винера не может быть применена независимо от того, насколько мало d .
Используя китайскую теорему об остатках : предположим, что кто-то выбирает d так, что d p ≡ d (mod ( p − 1)) и d q ≡ d (mod ( q − 1)) малы, но сам d нет, тогда быстрое дешифрование C : можно сделать следующим образом
- Сначала вычислите M p ≡ C д п (mod p ) и M q ≡ C д q (мод q .
- Используйте китайскую теорему об остатках , чтобы вычислить уникальное значение 0 ≤ M < N , которое удовлетворяет условиям M ≡ M p (mod p ) и M ≡ M q (mod q) . Результат M удовлетворяет условиям M ≡ C д (мод N ) по мере необходимости. Дело в том, что атака Винера здесь не применима, поскольку значение d mod λ ( N ) может быть большим. [ 3 ]
Как работает атака
[ редактировать ]Обратите внимание, что
где G = НОД( п - 1, q - 1) .
Поскольку ed ≡ 1 (mod λ ( N ) , существует целое число K такое, что
Определение k = K / НОД( K , G ) и g = G / gcd( K , G ) и замена в приведенное выше дает:
- .
Разделено на dpq :
- , где .
Так, e / pq немного меньше, чем k / dg , причем первый полностью состоит из общедоступной информации . Однако метод проверки [ нужны разъяснения ] и догадка все еще требуется.
С помощью простых алгебраических манипуляций и тождеств можно проверить точность предположения . [ 1 ]
Теорема Винера
[ редактировать ]Пусть N = pq с q < p < 2 q . Пусть d < 1 / 3 N 1/4 .
Учитывая ⟨ N , e ⟩ с ed ≡ 1 (mod λ ( N )) , злоумышленник может эффективно восстановить d . [ 2 ] [ не удалось пройти проверку ]
Пример
[ редактировать ]![]() | Этот раздел может сбивать с толку или быть неясным для читателей . В частности, предполагается, что ed ≡ 1 (mod φ ( N )), в отличие от остальной части статьи, где вместо этого используется (mod λ ( N )). ( Апрель 2022 г. ) |
Предположим, что открытые ключи: ⟨ N , e ⟩ = ⟨90581, 17993⟩ . Атака должна определить d . Используя теорему Винера и цепные дроби для аппроксимации d , сначала мы пытаемся найти цепных дробей разложение е / N . Обратите внимание, что этот алгоритм находит дроби в их наименьших терминах. Мы знаем, что
В соответствии с непрерывных фракций расширением e / N , все сходящиеся к / д это:
Мы можем проверить, что первая подходящая дробь не приводит к факторизации N . Однако конвергентный 1 / 5 доходность
Теперь, если мы решим уравнение
затем находим корни x = 379; 239 . Таким образом, мы нашли факторизацию
- .
Обратите внимание, что для модуля N = 90581 теорема Винера будет работать, если
- .
Доказательство теоремы Винера
[ редактировать ]Доказательство основано на приближениях с использованием цепных дробей. [ 2 ] [ 4 ]
Поскольку ed = 1 (mod λ ( N )) , существует k такой, что ed − kλ ( N ) = 1 . Поэтому
- .
Пусть G = НОД( p − 1, q − 1) ; обратите внимание, что если ) используется φ ( N вместо λ ( N ), то доказательство можно заменить на G = 1 , а φ ( N ) заменить на λ ( N ).
Затем умножив на 1 / G ,
Следовательно, k / Gd — аппроксимация е / φ ( N ) . Хотя злоумышленник не знает φ ( N ), он может использовать N для его аппроксимации. Действительно, поскольку φ ( N ) = N − p − q + 1 и p + q − 1 < 3 √ N , мы имеем:
Используя N вместо φ ( N ), получаем:
Теперь kλ ( N ) = ed − 1 < ed , поэтому kλ ( N ) < ed . Поскольку e < λ ( N ) , поэтому kλ ( N ) < ed < λ ( N ) d , то получаем:
Поскольку k < d и d < 1 / 3 N 1/4 . Отсюда мы получаем:
- (1)
Поскольку d < 1 / 3 N 1/4 , 2 d < 3 d , то 2 d < 3 d < N 1/4 , получаем:
- , поэтому (2)
Из (1) и (2) можно сделать вывод, что
Если | х - а / б | < 1/2 б 2 , тогда a / b является подходящей функцией x , поэтому k / Gd появляется среди подходящих е / N . Следовательно, алгоритм действительно в конечном итоге найдет k / Gd . [ нужны дальнейшие объяснения ]
Ссылки
[ редактировать ]- ^ Jump up to: а б Л. Рендер, Элейн (2007). Атака Винера на короткие секретные показатели. [ мертвая ссылка ]
- ^ Jump up to: а б с Боне, Дэн (1999). Двадцать лет атак на криптосистему RSA. Уведомления Американского математического общества (AMS) 46 (2).
- ^ Цуй, Сяо-лей (2005). Атаки на криптосистему RSA.
- ^ Салах, Имад Халед; Дарвиш, Абдулла; Окейли, Салех (2006). «Математические атаки на криптосистему RSA» (PDF) . Журнал компьютерных наук . 2 (8): 665–671. дои : 10.3844/jcssp.2006.665.671 .
Дальнейшее чтение
[ редактировать ]- Дуйелла, Андрей (2004). Непрерывные дроби и RSA с малой секретной экспонентой.
- Винер, Майкл Дж. (1990). «Криптоанализ коротких секретных показателей RSA» . Труды по теории информации . 36 (3). IEEE : 553–558. дои : 10.1109/18.54902 . Проверено 9 марта 2024 г.
- Python-реализация атаки Винера.
- Р. Стинсон, Дуглас (2002). Теория и практика криптографии (2-е изд.). Компания CRC Press. стр. 200–204. ISBN 1-58488-206-9 .