WikiSort.ru - Не сортированное

Атака Винера, названная в честь криптолога Майкла Дж. Винера, является типом криптографической атаки против алгоритма RSA. Атака использует метод непрерывной дроби, чтобы взломать систему при малом значении закрытой экспоненты ${\displaystyle d}$ .

Кратко о RSA

Прежде чем начать описание того, как работает атака Винера, стоит ввести некоторые понятия, которые используются в RSA^[1]. Более подробную информацию см. в основной статье о RSA.

Для шифрования сообщений по схеме RSA используется открытый ключ - пара чисел ${\displaystyle (e,N)}$ , для расшифрования - закрытый ключ ${\displaystyle (d,N)}$ . Числа ${\displaystyle e,d}$ называются открытой и закрытой экспонентой соответственно, число ${\displaystyle N}$ - модулем. Mодуль ${\displaystyle N=pq}$ , где ${\displaystyle p}$ и ${\displaystyle q}$ - два простых числа. Связь между закрытой, открытой экспонентой и модулем задаётся, как ${\displaystyle ed=1{\bmod {\varphi }}(N)}$ , где ${\displaystyle \varphi (N)=(p-1)(q-1)}$ функция Эйлера.

Если по открытому ключу ${\displaystyle (e,N)}$ за короткое время можно восстановить ${\displaystyle d}$ , то ключ уязвим: получив информацию о закрытом ключе ${\displaystyle (d,N)}$ , у злоумышленников появляется возможность расшифровать сообщение.

История алгоритма

Криптосистема RSA был изобретена Рональдом Ривестом, Ади Шамир и Леонардом Адлеманом и впервые опубликован в 1977 году^[1]. С момента публикации статьи криптосистема RSA была исследована на уязвимости многими исследователями.^[2] Большая часть таких атак используют потенциально опасные реализации алгоритма и пользуются явными условиями на какой-либо недочёт в алгоритме: общий модуль, малый открытый ключ, малый закрытый ключ^[3]. Так алгоритм атаки крипотографической атаки на алгоритм RSA с малым закрытым ключом был предложен криптологом Майклом Дж. Винером в статье, впервые опубликованной в 1990 году.^[4] Теорема винера утверждает о том, что если выполняется условие малости ключа, то закрытый ключ может быть найден за линейное время.

Малый закрытый ключ

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

Винер также представил некоторые контрмеры против его атаки. Два метода описаны ниже:^[5]

1. Выбор большого открытого ключа :

Заменить ${\displaystyle e}$ на ${\displaystyle e'}$ , где ${\displaystyle e'=e+k\cdot \varphi (N)}$ для некоторого большого ${\displaystyle k}$ . Когда ${\displaystyle e'}$ достаточно велик, то есть ${\displaystyle e'>N^{\frac {3}{2}}}$ , то атака Винера неприменима независимо от того, насколько мал ${\displaystyle d}$ .

2. Используя китайскую теорему об остатках:

Выбрать ${\displaystyle d}$ так, чтобы и ${\displaystyle d_{p}=d{\bmod {(}}p-1)}$ , и ${\displaystyle d_{q}=d{\bmod {(}}q-1)}$ были малы, но сам ${\displaystyle d}$ нет, то быстрое дешифрование сообщения ${\displaystyle C}$ может быть выполнено следующим образом:

1. Сначала вычисляется ${\displaystyle M_{p}=C^{d_{p}}{\bmod {p}}}$ и ${\displaystyle M_{q}=C^{d_{q}}{\bmod {q}}}$
2. Используя китайскую теорему об остатках, чтобы вычислить уникальное значение ${\displaystyle M\in \mathbb {Z_{N}} }$ , которое удовлетворяет ${\displaystyle M=M_{p}{\bmod {p}}}$ и ${\displaystyle M=M_{q}{\bmod {q}}}$ . Результат ${\displaystyle M}$ удовлетворяет ${\displaystyle M=C^{d}{\bmod {N}}}$ как и требовалось. Дело в том, что атака Винера здесь неприменима, потому что значение ${\displaystyle d{\bmod {\varphi }}(N)}$ может быть большим.

Как работает атака Винера

Поскольку

${\displaystyle ed=1{\pmod {\operatorname {lcm} (p-1,q-1))}}}$ ,

то существует целое ${\displaystyle K}$ такое, что:

${\displaystyle ed=K\times \operatorname {lcm} (p-1,q-1)+1}$ .

Стоит определить ${\displaystyle G=\gcd(p-1,q-1)}$ и подставить в предыдущее уравнение:

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

Если обозначить ${\displaystyle k={\frac {K}{\gcd(K,G)}}}$ и ${\displaystyle g={\frac {G}{\gcd(K,G)}}}$ , то подстановка в предудыщее уравнение даст:

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

Разделив обе части уравнения на ${\displaystyle dpq}$ , выходит что:

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

В итоге, ${\displaystyle {\frac {e}{pq}}}$ немного меньше, чем ${\displaystyle {\frac {k}{dg}}}$ , причём первая дробь состоит целиком из публичной информации. Тем не менее, метод проверки такого предположения всё ещё необходим. Принимая во внимание, что ${\displaystyle ed>pq}$ последнее уравнение может быть записано как:

${\displaystyle edg=k(p-1)(q-1)+g}$ .

Используя простые алгебраические операции и тождества, можно установить точность такого предположения.^[6]

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

Пусть ${\displaystyle N=pq}$ , где ${\displaystyle q<p<2q}$ . Пусть ${\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}}$ .

Имея ${\displaystyle \left\langle N,e\right\rangle }$ , где ${\displaystyle ed=1{\bmod {\varphi }}(N)}$ , взломщик может восстановить ${\displaystyle d}$ .^[7]

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

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

Поскольку ${\displaystyle ed=1{\bmod {\varphi }}(N)}$ , то существует ${\displaystyle {\mathit {k}}}$ при котором ${\displaystyle ed-k\varphi (N)=1}$ . Следовательно:

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

Значит, ${\displaystyle {\frac {k}{d}}}$ - это приближение ${\displaystyle {\frac {e}{\varphi (N)}}}$ . Несмотря на то что взломщик не знает ${\displaystyle \varphi (N)}$ , он может использовать ${\displaystyle N}$ чтобы его приблизить. Действительно, поскольку:

${\displaystyle \varphi (N)=N-p-q+1}$ and ${\displaystyle p+q-1<3{\sqrt {N}}}$ , мы имеем: ${\displaystyle \left\vert p+q-1\right\vert <3{\sqrt {N}}}$ и ${\displaystyle \left\vert N+1-\varphi (N)-1\right\vert <3{\sqrt {N}}}$

Используя ${\displaystyle N}$ вместо ${\displaystyle \varphi (N)}$ , получим:

${\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert =\left\vert {\frac {ed-kn}{Nd}}\right\vert =\left\vert {\frac {ed-k\varphi (N)-kN+k\varphi (N)}{Nd}}\right\vert }$

${\displaystyle =\left\vert {\frac {1-k(N-\varphi (N))}{Nd}}\right\vert \leq \left\vert {\frac {3k{\sqrt {N}}}{Nd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}d}}={\frac {3k}{d{\sqrt {N}}}}}$

Теперь, ${\displaystyle k\varphi (N)=ed-1<ed}$ , значит ${\displaystyle k\varphi (N)<ed}$ . Поскольку ${\displaystyle e<\varphi (N)}$ , значит ${\displaystyle k\varphi (N)<ed<\varphi (N)d}$ , и в итоге получается:

${\displaystyle k\varphi (N)<\varphi (N)d}$

где ${\displaystyle k<d}$

Так как ${\displaystyle k<d}$ и ${\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}}$ , следовательно:

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

Поскольку ${\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}},2d<3d}$ , то ${\displaystyle 2d<3d<N^{\frac {1}{4}}}$ , и исходя из этого ${\displaystyle 2d<N^{\frac {1}{4}}}$ , значит:

${\displaystyle (2){\frac {1}{2d}}>{\frac {1}{N^{\frac {1}{4}}}}}$

Из (1) и (2), можно заключить, что:

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

Смысл теоремы заключается в том, что если условие выше удовлетворено, то ${\displaystyle {\frac {k}{d}}}$ появляется среди подходящих дробей для неперывной дроби числа ${\displaystyle {\frac {e}{N}}}$ .

Следовательно, алгоритм в итоге найдёт такое ${\displaystyle {\frac {k}{d}}}$ ^[9].

Описание алгоритма

Рассматривается открытый RSA ключ ${\displaystyle (e,N)}$ , по которому необходимо определить закрытую экспоненту ${\displaystyle d}$ . Если известно, что ${\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}}$ , то это возможно сделать по следующему алгоритму ^[10]:

1. Разложить дробь ${\displaystyle {\frac {e}{N}}}$ в непрерывную дробь ${\displaystyle [a_{1},a_{2}...]}$ .

2. Для непрерывной дроби ${\displaystyle [a_{1},a_{2}...]}$ найти множество всех возможных подходящих дробей ${\displaystyle {\frac {k_{n}}{d_{n}}}}$ .

3. Исследовать подходящую дробь ${\displaystyle {\frac {k_{n}}{d_{n}}}}$ :

3.1. Определить возможное значение ${\displaystyle \varphi (N)}$ , вычислив ${\displaystyle f_{n}={\frac {ed_{n}-1}{k_{n}}}}$ .

3.2. Решив уравнение ${\displaystyle x^{2}-((N-f_{n})+1)x+N=0}$ , получить пару корней ${\displaystyle (p_{n},q_{n})}$ .

4. Если для пары корней ${\displaystyle (p_{n},q_{n})}$ выполняется равенство ${\displaystyle N=p_{n}\cdot q_{n}}$ , то закрытая экспонента найдена ${\displaystyle d=d_{n}}$ .

Если условие не выполняется или не удалось найти пару корней ${\displaystyle (p_{n},q_{n})}$ , то необходимо исследовать следующую подходящую дробь ${\displaystyle {\frac {k_{n+1}}{d_{n+1}}}}$ , вернувшись к шагу 3.

Пример работы алгоритма

Два данных примера ^[10] наглядно демонстрируют нахождение закрытой экспоненты ${\displaystyle d}$ , если известен открытый ключ RSA ${\displaystyle (e,N)}$ .

Для открытого ключа открытого ключа ${\displaystyle (1073780833,1220275921)}$ :

Получается, что ${\displaystyle d=25}$ . В этом примере можно заметить, что условие малости выполняется ${\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}\approx 62.30074...}$ .

Для открытого ключа RSA ${\displaystyle (e,N)=(1779399043,2796304957)}$ :

Получается, что ${\displaystyle d=11}$ . В этом примере так же можно заметить, что условие малости выполняется ${\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}\approx 76.65224...}$ .

Сложность алгоритма

Сложность алгоритма определяется количеством подходящих дробей для непрерывной дроби числа ${\displaystyle {\frac {e}{N}}}$ , что есть величина порядка ${\displaystyle O(log(n))}$ . То есть число ${\displaystyle d}$ восстанавливается за линейное время^[11] от длины ключа.

Ссылки

Литература

• Rivest R., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (англ.) // Communications of the ACM. — 1978. — P. 120–126.
• Wiener M. Cryptanalysis of short RSA secret exponents (англ.) // IEEE Transactions on Information Theory. — 1990. — P. 553–558.
• Coppersmith D., Franklin M., Patarin J., Reiter M. Low-Exponent RSA with Related Messages (англ.) // Proceedings of the 15th annual international conference on Theory and application of cryptographic techniques. — 1996. — P. 1-9.
• Boneh D. Twenty Years of attacks on the RSA Cryptosystem (англ.) // Notices of the American Mathematical Society (AMS). — 1999.
• Dujella A. Continued Fractions and RSA with Small Secret Exponent (англ.) // CoRR. — 2004. — P. 1-11.
• Khaled S. Mathematical Attacks on RSA Cryptosystem (англ.) // Journal of Computer Science. — 2006. — P. 665-671.
• Render E. Wiener's Attack on Short Secret Exponents // IEEE Proceedings. — 2007.
• Sarkar S., Maitra S. Revisiting Wiener’s Attack - New Weak Keys in RSA (англ.) // Indian Statistical Institute. — 2008.
• Justin J., Siddhart R., Sushant P., Shriket P. Study of RSA and Proposed Variant Against Wiener's Attack (англ.) // International Journal of Computer Applications. — 2010. — P. 15-20.
• Kedmi S. Python Implementation of Wiener's Attack (англ.). — 2016.
• Stinson D. Cryptography Theory and Practice. — 2e. — A CRC Press Company, 2002. — ISBN 1-58488-206-9.
• Герман О.Н, Нестеренко Ю.В. Теоретико-числовые методы в криптографии. — 1. — ACADEMA, 2012. — ISBN 978-5-7695-6786-5.