Русская Википедия:Атака Винера

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

Кратко о RSA

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

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

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

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

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

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

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

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

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

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

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

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

Сначала вычисляется <math> M_p = C^{d_p} \bmod p </math> и <math> M_q = C^{d_q} \bmod q </math>
Используя китайскую теорему об остатках, чтобы вычислить уникальное значение <math> M \in \mathbb{Z_N} </math>, которое удовлетворяет <math> M = M_p \bmod p </math> и <math> M = M_q \bmod q </math>. Результат <math> M </math>удовлетворяет <math> M = C^{d} \bmod N </math> как и требовалось. Дело в том, что атака Винера здесь неприменима, потому что значение <math> d \bmod \varphi(N) </math> может быть большим.

Шаблон:См. также

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

Поскольку

<math> ed = 1 \pmod {\operatorname{lcm}(p-1, q-1))} </math>,

то существует целое <math> K </math> такое, что:

<math> ed = K \times \operatorname{lcm}(p-1, q-1) + 1 </math>.

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

<math> ed = \frac {K}{G}(p-1)(q-1) + 1 </math>.

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

<math> ed = \frac{k}{g}(p-1)(q-1) + 1 </math>.

Разделив обе части уравнения на <math> dpq </math>, выходит что:

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

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

<math> edg = k(p-1)(q-1) + g </math>.

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

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

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

Имея <math> \left \langle N,e\right \rangle </math>, где <math> ed = 1 \bmod \varphi(N) </math>, взломщик может восстановить <math> d </math>.Шаблон:Sfn

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

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

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

<math> \left \vert \frac {e}{\varphi(N)}- \frac {k}{d} \right \vert = \frac{1}{d \varphi(N)} </math>.

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

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

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

<math> \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 </math>

<math> = \left \vert \frac{1-k(N- \varphi(N))}{Nd} \right \vert \le \left \vert \frac{3k \sqrt{N}}{Nd} \right \vert = \frac {3k \sqrt{N}}{\sqrt{N} \sqrt{N}d} = \frac {3k}{d \sqrt{N}} </math>

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

<math> k\varphi(N) < \varphi(N)d </math>

где <math> k < d </math>

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

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

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

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

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

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

Следовательно, алгоритм в итоге найдёт такое <math> \frac{k}{d} </math>Шаблон:Sfn.

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

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

1. Разложить дробь <math> \frac{e}{N} </math> в непрерывную дробь <math> [a_1, a_2...] </math>.

2. Для непрерывной дроби <math> [a_1, a_2...] </math> найти множество всех возможных подходящих дробей <math> \frac{k_n}{d_n} </math>.

3. Исследовать подходящую дробь <math> \frac{k_n}{d_n} </math>:

3.1. Определить возможное значение <math> \varphi(N) </math>, вычислив <math> f_n = \frac{ed_n -1}{k_n} </math>.

3.2. Решив уравнение <math> x^2 - ((N - f_n) + 1)x + N = 0 </math>, получить пару корней <math> (p_n, q_n) </math>.

4. Если для пары корней <math> (p_n, q_n) </math> выполняется равенство <math> N = p_n \cdot q_n </math>, то закрытая экспонента найдена <math> d = d_n </math>.

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

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

Два данных примера Шаблон:Sfn наглядно демонстрируют нахождение закрытой экспоненты <math> d </math>, если известен открытый ключ RSA <math> (e, N) </math>.

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

Таблица: нахождение закрытой экспоненты 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

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

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

Таблица: нахождение закрытой экспоненты 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

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

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

Сложность алгоритма определяется количеством подходящих дробей для непрерывной дроби числа <math> \frac{e}{N} </math>, что есть величина порядка <math> O(log(n)) </math>. То есть число <math> d </math> восстанавливается за линейное время Шаблон:Sfn от длины ключа.

Ссылки

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.