Атака Винера, названная в честь криптолога Майкла Дж. Винера, является типом криптографической атаки против алгоритма 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 :
+ Таблица: нахождение закрытой экспоненты de/N = [0, 1, 7, 3, 31, 5, 2, 12, 1, 28, 13, 2, 1, 2, 3]nkn / dnphinpnqnpn qn00/1---- 11/11073780832--- 27/81227178094---322/25122020549230763396671220275921
Получается, что . В этом примере можно заметить, что условие малости выполняется .
Для открытого ключа RSA :
+ Таблица: нахождение закрытой экспоненты de/N = [0, 1, 1, 1, 2, 1, 340, 2, 1, 1, 3, 2, 3, 1, 21, 188]nkn / dnfnpnqnpn qn00/1----11/11779399042--- 21/23558798085---32/32669098564--- 45/82847038468---57/11279619849647129593332796304957
Получается, что . В этом примере так же можно заметить, что условие малости выполняется .
Сложность алгоритма
Сложность алгоритма определяется количеством подходящих дробей для непрерывной дроби числа , что есть величина порядка . То есть число восстанавливается за линейное время от длины ключа.
Ссылки
Литература
Категория:Атаки и эксплойты Категория:Криптографические атаки Категория:Информационная безопасность