Применение NP-полных задач в ассиметрично-ключевой криптографии (стр. 4 из 6)

Рис. 6 Шифрование и дешифрование в примере 5

7. Атаки RSA

До настоящего момента не было обнаружено никаких разрушительных атак RSА. Несколько атак были предсказаны. Они основаны на слабом исходном тексте, слабом выборе параметра или несоответствующей реализации. Рис.7 http://www.intuit.ru/department/security/mathcryptet/14/4.html - image.14.8 показывает категории потенциальных атак.

Рис. 7 Диаграмма возможных атак на RSA

· Атака разложения на множители

Безопасность RSА базируется на следующей идее: модуль настолько большой, что разложение на множители в разумное время неосуществимо. Боб выбирает p и q и вычисляет

. Число n общедоступно, p и q являются секретными. Если Ева сможет разложить на множители n и получить p и q, то она может вычислить . Затем Ева тогда может вычислить , потому что e общедоступен. Секретный ключ d – лазейка, которую Ева может использовать, чтобы расшифровать зашифрованное сообщение.

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

· Атака с выборкой зашифрованного текста

Потенциальная атака RSА базируется на мультипликативном свойстве RSA. Предположим, Алиса создает зашифрованный текст C = P^e mod n и передает C Бобу. Также предположим, что Боб расшифрует произвольный зашифрованный текст для Евы – С₁, отличный от C. Ева перехватывает C и использует следующие шаги, чтобы найти P:

а. Ева выбирает случайное целое число X в Z_n*.

б. Ева вычисляет

.

в. Ева передает Y Бобу для дешифрования и получает Z = Y^d mod n; это шаг атаки выборкой зашифрованного текста.

г. Ева может легко найти P, потому что

Z = Y^d mod n = (C × X^e)^d mod n = (C^d × X^ed) mod n = (C^d × X) mod n = (P × X) mod n

Z = (P × X) mod n

P=Z × X^-1 mod n

Ева использует расширенный евклидов алгоритм для того, чтобы найти мультипликативную инверсию X, и в конечном счете значение P.

· Атаки на показатель степени шифрования

Чтобы уменьшить время шифрования, можно попытаться использовать короткий ключ шифрования – малое значение числа e, например, значение для e, такое как e = 3 (второе простое число). Однако есть некоторые потенциальные атаки на показатель при его малом значении степени шифрования, которые мы здесь кратко обсуждаем. Эти атаки вообще не кончаются вскрытием системы, но они все-таки должны быть предотвращены. Для того чтобы сорвать эти виды атак, рекомендуется использовать e = 2¹⁶ + 1 = 65537 (или простое число, близкое к этому значению).

· Атака теоремы Куперcмита (Coppersmith) может быть главной для атаки малого показателя степени на ключ шифрования. Основное положение этой теоремы: для полинома f(x) степени e по модулю n, чтобы найти корни, если один из корней является меньшим чем n^1/e, можно использовать алгоритм сложности, log n. Эта теорема может быть применена к RSA-криптосистеме C = f(P) = P^e mod n. Если e = 3 и известны хотя бы две трети битов в исходном тексте P, алгоритм может найти все биты в исходном тексте.

· Атака широковещательной передачи может быть начата, если один объект передает одно и то же сообщение группе получателей с тем же самым ключом шифрования. Например, предположим следующий сценарий: Алиса хочет передать одно и то же сообщение трем получателям с тем же самым общедоступным ключом e = 3 и модулями n₁, n₂ и n₃.

C₁ = P³ mod n₁

C₂ = P³ mod n₂

C₃ = P³ mod n₃

Применяя китайскую теорему об остатках к этим трем уравнениям, Ева может найти уравнение формы C’ = P³ mod n₁n₂n₃. Это означает, что P³ < n₁n₂n₃ и что C’ = P³ решается с помощью обычной арифметики (не модульной). Ева может найти значение C’ = P^1/3.

· Атака связанных между собой сообщений была обнаружена Франклином Рейтером (Franklin Reiter). Она может быть кратко описана следующим образом. Алиса зашифровала два исходных текста, P₁ и P₂, с помощью e = 3 и передает C₁ и C₂ Бобу. Если P₁ связан с P₂ линейной функцией, то Ева может восстановить P₁ и P₂ в выполнимое время вычисления.

· Атака короткого списка, обнаруженная Куперсмитом, может быть кратко описана следующим образом. Алиса имеет сообщение М для передачи Бобу. Она записывает сообщение и зашифровывает его как сообщение r₁, а результат записывает как C₁ и передает C₁ (Бобу). Ева перехватывает C₁ и удаляет его. Боб сообщает Алисе, что он не получил сообщение, так что Алиса заполняет сообщение, снова зашифровывает как сообщение r₂ и передает это Бобу. Ева также перехватывает и это сообщение. Ева теперь имеет C₁ и C₂, и она знает, что оба зашифрованных текста принадлежат одному и тому же исходному тексту. Куперсмит доказал, что если r₁ и r₂ короткие, то Ева способна восстановить первоначальное сообщение М.

· Атаки показателя степени дешифрации

Две формы атак могут быть проведены на показатель степени дешифрации: атака раскрытой степени дешифрации и атака малого показателя степени дешифровации. Они обсуждаются ниже.

· Атака раскрытого показателя степени дешифрации. Очевидно, что если Ева может найти показатель степени дешифрации, d, она сможет расшифровать текущее зашифрованное сообщение. Однако на этом атака не останавливается. Если Ева знает значение d, она может использовать вероятностный алгоритм (не обсуждаемый здесь) к числу n и найти значения p и q. Следовательно, если Боб изменит только угрожающий безопасности показатель степени дешифрования, но сохранит тот же самый модуль n, Ева сможет расшифровать будущие сообщения, потому что она сможет разложить на множители n. Поэтому если Боб узнает, что показатель степени скомпрометирован, он должен выбрать новое значение для p и q, вычислить n и создать полностью новые секретный и открытый ключи доступа.

В RSA, если показатель степени d скомпрометирован, тогда p, q, n, e и d должны быть сгенерированы заново.

· Атака малого значения показателя степени дешифрации. Боб может подумать, что использование малого значения степени секретного ключа d приводит к более быстрой работе алгоритма дешифрации. Винер показал, что в случае d < 1/3n^1/4 возможен специальный тип атаки, основанной на цепной дроби, – тема, которая рассматривается в теории чисел. Этот тип атаки может подвергнуть риску безопасность RSА. Для того чтобы это произошло, должно выполняться условие, что q < p < 2q; если эти два условия существуют, Ева может разложить n на сомножители в полиномиальное время.

В RSA рекомендовано, что d должно иметь величину d > 1/3 n^1/4, чтобы предотвратить атаку малого значения ключа дешифрации.

· Атаки исходного текста

Исходный текст и зашифрованный текст в RSA – это перестановки друг друга, потому что это целые числа в том же самом интервале (от 0 до n – 1). Другими словами, Ева уже знает кое-что об исходном тексте. Эти характеристики могут позволить некоторые атаки исходного текста. Три атаки были уже упомянуты в литературе: атака короткого сообщения, атака циклического повторения и явная атака.

· Атака короткого сообщения. В атаке короткого сообщения, если Ева знает множество возможных исходных текстов, то ей известна еще одна информация и дополнительный факт, что зашифрованный текст – перестановка исходного текста. Ева может зашифровать все возможные сообщения, пока результат не будет совпадать с перехваченным зашифрованным текстом. Например, если известно, что Алиса посылает число с четырьмя цифрами Бобу, Ева может легко испытать числа исходного текста 0000 к 9999, чтобы найти исходный текст. По этой причине короткие сообщения должны быть дополнены случайными битами в начале и конце, чтобы сорвать этот тип атаки. Настоятельно рекомендуется заполнять исходный текст случайными битами прежде начала шифрования. Здесь используется метод, называемый OAEP, который будет позже обсужден в этой лекции.

· Атака циклического повторения построена на факте, что если переставлять зашифрованный текст (перестановка исходного текста), то непрерывное шифрование зашифрованного текста в конечном счете кончится исходным текстом. Другими словами, если Ева непрерывно шифрует перехваченный зашифрованный текст C, она в итоге получит исходный текст. Однако сама Ева не знает, каков исходный текст, так что ей неизвестно, когда пора остановиться. Она должна пройти один шаг далее. Когда она получает зашифрованный текст C снова, она возвращается на один шаг, чтобы найти исходный текст.