Атака Винера

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Кратко о RSA[править | править код]

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

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

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

История алгоритма[править | править код]

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

Малый закрытый ключ[править | править код]

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

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

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

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

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

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

Как работает атака Винера[править | править код]

Поскольку

,

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

.

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

.

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

.

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

, где .

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

.

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

Теорема Винера[править | править код]

Пусть , где . Пусть .

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

Доказательство теоремы Винера[править | править код]

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

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

.

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

and , мы имеем: и

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

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

где

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

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

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

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

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

Описание алгоритма[править | править код]

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

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

Пример работы алгоритма[править | править код]

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

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

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

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

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

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

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

Сложность алгоритма[править | править код]

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

Ссылки[править | править код]

  1. 1 2 Rivest, 1978.
  2. Boneh, 1999, Introduction, p. 1.
  3. Coppersmith, 1996.
  4. Wiener, 1990.
  5. Wiener, 1990, Combatting the Continued Fraction Attack on RSA., p. 557.
  6. Render, 2007.
  7. Boneh, 1999.
  8. Khaled, 2006.
  9. Герман, 2012, Об уязвимости системы RSA. Малый секретный ключ., pp. 283-284.
  10. 1 2 Kedmi, 2016.
  11. Герман, 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.