Атака Винера

, Атака Винера названная в честь криптолога Майкла Дж. Винера, представляет собой разновидность криптографической атаки на 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. модуль

Маленький закрытый ключ

В криптосистеме RSA Боб мог бы использовать небольшое значение d , а не большое случайное число, чтобы улучшить RSA производительность дешифрования . Однако атака Винера показывает, что выбор небольшого значения d приведет к созданию небезопасной системы, в которой злоумышленник сможет восстановить всю секретную информацию, т. е. взломать систему RSA . Этот разрыв основан на теореме Винера, которая справедлива для малых значений d . Винер доказал, что злоумышленник может эффективно найти d, когда d < ⁠ 1 / 3 ⁠  N ^1/4 .

В статье Винера также представлены некоторые контрмеры против его атаки, которые позволяют быстро расшифровать. Ниже описаны два метода.

Выбор большого открытого ключа : Замените 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 : можно сделать следующим образом

1. Сначала вычислите M _p ≡ C ^{д _п} (mod p ) и M _q ≡ C ^{д _q} (мод q .
2. Используйте китайскую теорему об остатках , чтобы вычислить уникальное значение 0 ≤ M < N , которое удовлетворяет условиям M ≡ M _p (mod p ) и M ≡ M _q (mod q) . Результат M удовлетворяет условиям M ≡ C ^д (мод N ) по мере необходимости. Дело в том, что атака Винера здесь не применима, поскольку значение d mod λ ( N ) может быть большим.

См. также: RSA (алгоритм) § Использование китайского алгоритма остатка

Как работает атака

Обратите внимание, что

$\lambda (N)=\operatorname {lcm} (p-1,q-1)={\frac {(p-1)(q-1)}{G}}={\frac {\varphi (N)}{G}}$

где G = НОД( п - 1, q - 1) .

Поскольку ed ≡ 1 (mod λ ( N ) , существует целое число K такое, что

$ed=K\times \lambda (N)+1$

$ed={\frac {K}{G}}(p-1)(q-1)+1$

Определение k = ⁠ K / НОД( K , G ) ⁠ и g = ⁠ G / gcd( K , G ) ⁠ и замена в приведенное выше дает:

$ed={\frac {k}{g}}(p-1)(q-1)+1$.

Разделено на dpq :

${\frac {e}{pq}}={\frac {k}{dg}}(1-\delta )$, где $\delta ={\frac {p+q-1-{\frac {g}{k}}}{pq}}$.

Так, ⁠ e / pq ⁠ немного меньше, чем ⁠ k / dg ⁠ , причем первый полностью состоит из общедоступной информации . Однако метод проверки и догадка все еще требуется.

С помощью простых алгебраических манипуляций и тождеств можно проверить точность предположения .

Теорема Винера

Пусть N = pq с q < p < 2 q . Пусть d < ⁠ 1 / 3 ⁠  N ^1/4 .

Учитывая ⟨ N , e ⟩ с ed ≡ 1 (mod λ ( N )) , злоумышленник может эффективно восстановить d .

Пример

Предположим, что открытые ключи: ⟨ N , e ⟩ = ⟨90581, 17993⟩ . Атака должна определить d . Используя теорему Винера и цепные дроби для аппроксимации d , сначала мы пытаемся найти цепных дробей разложение ⁠ е / N ⁠ . Обратите внимание, что этот алгоритм находит дроби в их наименьших терминах. Мы знаем, что

${\frac {e}{N}}={\frac {17993}{90581}}={\cfrac {1}{5+{\cfrac {1}{29+\dots +{\cfrac {1}{3}}}}}}=\left[0,5,29,4,1,3,2,4,3\right]$

В соответствии с непрерывных фракций расширением ⁠ e / N ⁠ , все сходящиеся ⁠ к / д ⁠ это:

${\frac {k}{d}}=0,{\frac {1}{5}},{\frac {29}{146}},{\frac {117}{589}},{\frac {146}{735}},{\frac {555}{2794}},{\frac {1256}{6323}},{\frac {5579}{28086}},{\frac {17993}{90581}}$

Мы можем проверить, что первая подходящая дробь не приводит к факторизации N . Однако конвергентный ⁠ 1 / 5 ⁠ доходность

$\varphi (N)={\frac {ed-1}{k}}={\frac {17993\times 5-1}{1}}=89964$

Теперь, если мы решим уравнение

$x^{2}-\left(\left(N-\varphi (N)\right)+1\right)x+N=0$

$x^{2}-\left(\left(90581-89964\right)+1\right)x+90581=0$

$x^{2}-618x+90581=0$

затем находим корни x = 379; 239 . Таким образом, мы нашли факторизацию

$N=90581=379\times 239=p\times q$.

Обратите внимание, что для модуля N = 90581 теорема Винера будет работать, если

$d<{\frac {N^{1/4}}{3}}\approx 5.7828$.

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

Доказательство основано на приближениях с использованием цепных дробей.

Поскольку ed = 1 (mod λ ( N )) , существует k такой, что ed − kλ ( N ) = 1 . Поэтому

$\left|{\frac {e}{\lambda (N)}}-{\frac {k}{d}}\right\vert ={\frac {1}{d\lambda (N)}}$.

Пусть G = НОД( p − 1, q − 1) ; обратите внимание, что если ) используется φ ( N вместо λ ( N ), то доказательство можно заменить на G = 1 , а φ ( N ) заменить на λ ( N ).

Затем умножив на ⁠ 1 / G ⁠ ,

$\left|{\frac {e}{\varphi (N)}}-{\frac {k}{Gd}}\right\vert ={\frac {1}{d\varphi (N)}}$

Следовательно, ⁠ k / Gd ⁠ — аппроксимация ⁠ е / φ ( N ) ⁠ . Хотя злоумышленник не знает φ ( N ), он может использовать N для его аппроксимации. Действительно, поскольку φ ( N ) = N − p − q + 1 и p + q − 1 < 3 √ N , мы имеем:

$\left\vert p+q-1\right\vert <3{\sqrt {N}}$

$\left\vert N-\varphi (N)\right\vert <3{\sqrt {N}}$

Используя N вместо φ ( N ), получаем:

${\begin{aligned}\left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert &=\left\vert {\frac {edG-kN}{NGd}}\right\vert \\&=\left\vert {\frac {edG-k\varphi (N)-kN+k\varphi (N)}{NGd}}\right\vert \\&=\left\vert {\frac {1-k(N-\varphi (N))}{NGd}}\right\vert \\&<\left\vert {\frac {-k(N-\varphi (N))}{NGd}}\right\vert (\because 0<|N-\varphi (N)|)\\&<\left\vert {\frac {3k{\sqrt {N}}}{NGd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}Gd}}\leq {\frac {3k}{d{\sqrt {N}}}}\end{aligned}}$

Теперь kλ ( N ) = ed − 1 < ed , поэтому kλ ( N ) < ed . Поскольку e < λ ( N ) , поэтому kλ ( N ) < ed < λ ( N ) d , то получаем:

$k\lambda (N)<\lambda (N)d$

$k<d$

Поскольку k < d и d < ⁠ 1 / 3 ⁠  N ^1/4 . Отсюда мы получаем:

(1) $\left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert <{\frac {1}{dN^{\frac {1}{4}}}}$

Поскольку d < ⁠ 1 / 3 ⁠  N ^1/4 , 2 d < 3 d , то 2 d < 3 d < N ^1/4 , получаем:

$2d<N^{1/4}$, поэтому (2) ${\frac {1}{2d}}>{\frac {1}{N^{1/4}}}$

Из (1) и (2) можно сделать вывод, что

$\left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert <{\frac {3k}{d{\sqrt {N}}}}<{\frac {1}{d\cdot 2d}}={\frac {1}{2d^{2}}}$

Если | х - ⁠ а / б ⁠ | < ⁠ 1/2 ​ б ​ ² ⁠ , тогда ⁠ a / b ⁠ является подходящей функцией x , поэтому ⁠ k / Gd ⁠ появляется среди подходящих ⁠ е / N ⁠ . Следовательно, алгоритм действительно в конечном итоге найдет ⁠ k / Gd ⁠ .

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

• Копперсмит, Дон (1996). RSA с низкой экспонентой и связанными сообщениями. Шпрингер-Верлаг Берлин Гейдельберг.

• Дуйелла, Андрей (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 .