Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Очевидно, что если для параметров открытого ключа (N, е) выполняется условие т < Nxle, то шифрование сообщения с = me(mod N) не использует операции приведения по модулю, и, следовательно, значение т можно эффективно вычислить, извлекая корень е-й степени из целых чисел. Это одна из причин, по которой не следует выбирать вариант е = 3. В противном случае, если сообщение т зашифровано с помощью трех разных модулей: ci = т3(mod. Ni), где г = 1,2,3, то, поскольку модули являются попарно взаимно простыми числами, можно применить китайскую теорему об остатках (алгоритм 6.1) и вычислить значение С — m3(modA^iA^A^3). Теперь, поскольку т < (Л^Л^А/з)1/3, возведение в степень выполняется точно так же, как и в пространстве целых чисел. Итак, расшифровка сообщения С сводится к извлечению кубического корня из целых чисел и может быть эффективно реализована (см. подсказку в упражнению 8.8).
Куперсмит (Coopersmith) [82] распространил этот тривиальный случай на более сложный: для т? = m + t, где число т известно, а число t — нет, но при этом выполняется неравенство t < N*le, значение t можно эффективно вычислить по заданному числу с = m'e(modN). Поскольку в приложениях часто встречаются ситуации, в которых часть исходного текста является известной (см. главу 15), считается, что при шифровании с помощью алгоритма RSA не следует применять очень маленькие показатели степени е. Как правило, в качестве показателя степени при шифровании используется величина е = 216 +1 = 65537, которая является простым числом. Этот показатель гарантирует достаточную эффективность шифрования и предотвращает атаки, использующие малые показатели степени.
Если показатель степени d, использующийся при расшифровке, невелик, алгоритм RSA устойчив к атакам на основе подобранного открытого текста. Винер (Wiener) изобрел метод, основанный на представлении числа e/N в виде непрерывной дроби. Этот алгоритм позволяет найти число d, если d < N1/4 [298]. В дальнейшем этот результат был улучшен для чисел d < N0,292 [50].
310
Часть III. Основные методы криптографии
8.8 Разложение целых чисел на простые множители
Разрешимость задачи RSA зависит от сложности разложения целого числа на простые множители (integer factorization problem — IF-problem).
Определение 8.5 (Разложение целого числа на простые множители).
ИСХОДНЫЕ ДАННЫЕ:
N: нечетное составное целое число, имеющее по меньшей мере два
разных простых множителя. РЕЗУЛЬТАТ:
Простое число р, удовлетворяющее условию р \ N.
Предположение 8.4 (Условие неразрешимости задачи о разложении целого числа на простые множители). Алгоритмом решения задачи о разложении це-i лого числа на простые множители называется вероятностный полиномиальный алгоритм Л с преимуществом е > 0:
е = Prob [A(N) является делителем числа N и 1 < A(N) < N],
где входные данные алгоритма А указаны в определении 8.5.
Пусть TQ — генератор целых чисел, получающий на вход число lk, время работы которого является полиномом от параметра к, а результатом — 2Щ битовый модуль N = pq, где р и q — два равномерно распределенных случайнь простых нечетных числа, состоящих из к бит.
Будем говорить, что генератор TQ удовлетворяет условиям неразрешимости задачи о разложении целого числа на простые множители, если для вариантШ TQ(lk) не существует алгоритма решения с преимуществом е > 0, которое не является пренебрежимо малым по отношению ко всем достаточно большим числам к.
Очевидно, что алгоритм решения задачи о разложении целого числа на простые множители одновременно является алгоритмом решения задачи RSA, по! скольку Алиса расшифровывает текст, зашифрованный с помощью алгоритм! RSA, вычисляя значение d = e_1(mod(p — l)(q — 1)), т.е. используя информа! цию о факторизации числа N. Как и в задачах дискретного логарифмирование и Диффи-Хеллмана, обратное утверждение является недоказанным: выполняю» ся ли условия неразрешимости задачи о разложении целого числа на множители если условия неразрешимости задачи RSA не выполняются?
Как и в задаче Диффи-Хеллмана, слабым местом задачи о разложении цельщ чисел на простые множители являются гладкие простые числа N. Один из такия вариантов был продемонстрирован Поллардом, предложившим алгоритм эффек| тивной факторизации под названием (р — 1)-алгоритм Полларда [237]. В erJ
Глава 8. Шифрование — асимметричные методы
311
основе лежат следующие рассуждения. Пусть р — простой множитель числа N, а наибольший простой множитель числа р — 1 ограничен величиной В — Poly(fc), где к = \N\, a Poly(fc) — полином, зависящий от аргумента к. (Число В называется границей гладкости числа р — 1.) Сконструируем число
А= Yl rLiogW/iogrj_
простые числа г < В
Условие р — 1 | А выполняется автоматически, поэтому из малой теоремы Ферма (теорема 6.10) следует, что aA = l(modp) для любого целого числа а, удовлетворяющего условию gcd(a, р) = 1. Если существует простой множитель q числа N, не равный множителю р и такой что a)(l=\(modq), то существует целое число Ч, не кратное числу q, такое что аА — l(modAr) = Пр. Следовательно, число gcd(aA — l(mod N),N) должно быть собственным простым множителем числа N. Если N = pq, это число должно равняться числу р. Осталось показать, что размер числа А полиномиально зависит от числа к, а значит, число aA(modN) можно найти за полиномиальное время.
