Атака Винера

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

Кратко о RSA 

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

Для шифрования сообщений по схеме RSA используется открытый ключ - пара чисел , для расшифрования - закрытый ключ . Числа  называются открытой и закрытой экспонентой соответственно, число  - модулем. Mодуль , где  и  - два простых числа. Связь между закрытой, открытой экспонентой и модулем задаётся, как , где  функция Эйлера.

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

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

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

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

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

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

1. Выбор большого открытого ключа :
  Заменить  на , где  для некоторого большого . Когда  достаточно велик, то есть , то атака Винера неприменима независимо от того, насколько мал .

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

 Сначала вычисляется  и 
 Используя китайскую теорему об остатках, чтобы вычислить уникальное значение , которое удовлетворяет  и . Результат удовлетворяет  как и требовалось. Дело в том, что атака Винера здесь неприменима, потому что значение  может быть большим.

Как работает атака Винера 
Поскольку
 ,
то существует целое  такое, что:
 .

Стоит определить  и подставить в предыдущее уравнение:
 .

Если обозначить  и , то подстановка в предыдущее уравнение даст:
 .

Разделив обе части уравнения на , выходит что:
 , где .

В итоге,  немного меньше, чем , причём первая дробь состоит целиком из публичной информации. Тем не менее, метод проверки такого предположения всё ещё необходим. Принимая во внимание, что  последнее уравнение может быть записано как:
 .

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

Теорема Винера 
Пусть , где . Пусть .

Имея , где , взломщик может восстановить .

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

Поскольку , то существует  при котором . Следовательно:
 .

Значит,  - это приближение . Несмотря на то что взломщик не знает , он может использовать  чтобы его приблизить. Действительно, поскольку:

 and , мы имеем:  и 

Используя  вместо , получим:
 
 

Теперь, , значит . Поскольку , значит , и в итоге получается:
 
 где 

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

Поскольку , то , и исходя из этого , значит:
 

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

Смысл теоремы заключается в том, что если условие выше удовлетворено, то  появляется среди подходящих дробей для непрерывной дроби числа .

Следовательно, алгоритм в итоге найдёт такое .

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

Рассматривается открытый RSA ключ , по которому необходимо определить закрытую экспоненту .
Если известно, что , то это возможно сделать по следующему алгоритму :

 1. Разложить дробь  в непрерывную дробь .

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

 3. Исследовать подходящую дробь :
 3.1. Определить возможное значение , вычислив .
 3.2. Решив уравнение , получить пару корней .

 4. Если для пары корней  выполняется равенство , то закрытая экспонента найдена .
 Если условие не выполняется или не удалось найти пару корней , то необходимо исследовать следующую подходящую дробь , вернувшись к шагу 3.

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

Два данных примера  наглядно демонстрируют нахождение закрытой экспоненты , если известен открытый ключ RSA .

Для открытого ключа RSA  :

Получается, что .
В этом примере можно заметить, что условие малости выполняется .

Для открытого ключа RSA :

Получается, что .
В этом примере так же можно заметить, что условие малости выполняется .

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

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

Ссылки

Литература 
 
 
 
 
 
 
 
 
 
 
 
 

Атаки и эксплойты
Криптографические атаки
Информационная безопасность