Атака Винера

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

Кратко о RSA

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

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

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

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

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

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

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

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

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

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

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

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

1. Сначала вычисляется $M_p=C^{d_p}modp$ и $M_q=C^{d_q}modq$
2. Используя китайскую теорему об остатках, чтобы вычислить уникальное значение $M\in {\mathbb{Z}}_{\mathbb{\mathbb{N}}}$, которое удовлетворяет $M=M_{p}modp$ и $M=M_{q}modq$. Результат $M$удовлетворяет $M=C^{d}modN$ как и требовалось. Дело в том, что атака Винера здесь неприменима, потому что значение $dmod\phi (N)$ может быть большим.

Встречается также вариант написания: RSA#Использование китайской теоремы об остатках для ускорения расшифрования.

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

Поскольку

$ed=1(\mathrm{mod}\mathrm{lcm}(p-1,q-1)))$,

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

$ed=K\times \mathrm{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$.

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

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

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

Имея $⟨N,e⟩$, где $ed=1mod\phi (N)$, взломщик может восстановить $d$.

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

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

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

$|\frac{e}{\phi (N)}-\frac{k}{d}|=\frac{1}{d\phi (N)}$.

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

$\phi (N)=N-p-q+1$ and $p+q-1<3\sqrt{N}$, мы имеем: $|p+q-1|<3\sqrt{N}$ и $|N+1-\phi (N)-1|<3\sqrt{N}$

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

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

$=\left|\frac{1-k(N-\phi (N))}{Nd}\right|\le \left|\frac{3k\sqrt{N}}{Nd}\right|=\frac{3k\sqrt{N}}{\sqrt{N}\sqrt{N}d}=\frac{3k}{d\sqrt{N}}$

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

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

где $k<d$

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

$(1)|\frac{e}{N}-\frac{k}{d}|<\frac{1}{d{N}^{\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), можно заключить, что:

$|\frac{e}{N}-\frac{k}{d}|<\frac{3k}{d\sqrt{N}}<\frac{1}{d\cdot 2d}=\frac{1}{2d^2}$

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

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

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

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

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. Определить возможное значение $\phi (N)$, вычислив $f_n=\frac{e{d}_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.

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

Два данных примера наглядно демонстрируют нахождение закрытой экспоненты $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	kn / dn	phin	pn	qn	pn qn
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	kn / dn	fn	pn	qn	pn qn
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$ восстанавливается за линейное время от длины ключа.

Литература

• 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.