Атака Винера

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

Кратко о RSA

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

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

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

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

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

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

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

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

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

Заменить

e

на

e'

, где

e'=e+k\cdot \varphi (N)

для некоторого большого

k

. Когда

e'

достаточно велик, то есть

e'>N^{\frac {3}{2}}

, то атака Винера неприменима независимо от того, насколько мал

d

.

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

Выбрать

d

так, чтобы и

d_{p}=d{\bmod {(}}p-1)

, и

d_{q}=d{\bmod {(}}q-1)

были малы, но сам

d

нет, то быстрое дешифрование сообщения

C

может быть выполнено следующим образом:

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

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

Поскольку

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

,

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

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

.

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

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

.

Если обозначить $k={\frac {K}{\gcd(K,G)}}$ и $g={\frac {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}}

.

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

edg=k(p-1)(q-1)+g

.

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

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

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

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

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

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

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

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

.

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

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

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

\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

=\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}}}}

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

k\varphi (N)<\varphi (N)d

где

k<d

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

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

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

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

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

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

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

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

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

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

1. Разложить дробь

{\frac {e}{N}}

в непрерывную дробь

[a_{1},a_{2}...]

.

2. Для непрерывной дроби

[a_{1},a_{2}...]

найти множество всех возможных подходящих дробей

{\frac {k_{n}}{d_{n}}}

.

3. Исследовать подходящую дробь

{\frac {k_{n}}{d_{n}}}

:

3.1. Определить возможное значение

\varphi (N)

, вычислив

f_{n}={\frac {ed_{n}-1}{k_{n}}}

.

3.2. Решив уравнение

x^{2}-((N-f_{n})+1)x+N=0

, получить пару корней

(p_{n},q_{n})

.

4. Если для пары корней

(p_{n},q_{n})

выполняется равенство

N=p_{n}\cdot q_{n}

, то закрытая экспонента найдена

d=d_{n}

.

Если условие не выполняется или не удалось найти пару корней

(p_{n},q_{n})

, то необходимо исследовать следующую подходящую дробь

{\frac {k_{n+1}}{d_{n+1}}}

, вернувшись к шагу 3.

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

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

Для открытого ключа RSA $(e,N)=(1073780833,1220275921)$ :

Таблица: нахождение закрытой экспоненты d
e/N = [0, 1, 7, 3, 31, 5, 2, 12, 1, 28, 13, 2, 1, 2, 3]
n	k_n / d_n	phi_n	p_n	q_n	p_n q_n
0	0/1	-	-	-	-
1	1/1	1073780832	-	-	-
2	7/8	1227178094	-	-	-
3	22/25	1220205492	30763	39667	1220275921

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

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

Таблица: нахождение закрытой экспоненты d
e/N = [0, 1, 1, 1, 2, 1, 340, 2, 1, 1, 3, 2, 3, 1, 21, 188]
n	k_n / d_n	f_n	p_n	q_n	p_n q_n
0	0/1	-	-	-	-
1	1/1	1779399042	-	-	-
2	1/2	3558798085	-	-	-
3	2/3	2669098564	-	-	-
4	5/8	2847038468	-	-	-
5	7/11	2796198496	47129	59333	2796304957

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

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

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

Ссылки

↑ ¹ ² Rivest, 1978.
↑ Boneh, 1999, Introduction, p. 1.
↑ Coppersmith, 1996.
↑ Wiener, 1990.
↑ Wiener, 1990, Combatting the Continued Fraction Attack on RSA., p. 557.
↑ Render, 2007.
↑ Boneh, 1999.
↑ Khaled, 2006.
↑ Герман, 2012, Об уязвимости системы RSA. Малый секретный ключ., pp. 283-284.
↑ ¹ ² Kedmi, 2016.
↑ Герман, 2012, Об уязвимости системы RSA. Малый секретный ключ., p. 284: «Количество же этих дробей есть величина порядка O(ln(n)), то есть число d восстанавливается за линейное время».

Литература

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.

[_ec99ba321dd6d8b1-1] ¹ ² Rivest, 1978.

[_70b5f76ce5cfd31a-2] Boneh, 1999, Introduction, p. 1.

[_fa0352b7fc08021c-3] Coppersmith, 1996.

[_97573b1bf93cf77c-4] Wiener, 1990.

[_66f2e3fd84d55816-5] Wiener, 1990, Combatting the Continued Fraction Attack on RSA., p. 557.

[_b4ebba83707d3924-6] Render, 2007.

[_dd37a5ba3f09df55-7] Boneh, 1999.

[_e7707a6cccc509a2-8] Khaled, 2006.

[_5ecffabc53aac665-9] Герман, 2012, Об уязвимости системы RSA. Малый секретный ключ., pp. 283-284.

[_5299279c80a5977e-10] ¹ ² Kedmi, 2016.

[_cd2b247c44fdbcbc-11] Герман, 2012, Об уязвимости системы RSA. Малый секретный ключ., p. 284: «Количество же этих дробей есть величина порядка O(ln(n)), то есть число d восстанавливается за линейное время».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]