Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
m(mod2) «- PON{me{modN)).
В доказательстве теоремы 9.1 обозначим через ж? (а, Ъ) целое число х, принадлежащее интервалу (а, Ъ), где числа а и/или Ь не обязательно целые. Поскольку х — целое число, из условия х ? (а, Ь) следует, что оно принадлежит отрезку
И, LbJl-
Основной проблемой в доказательстве является метод бинарного поиска (binary search). Его применение обеспечивается следующим утверждением.
Лемма 9.1. Пусть N — нечетное целое число ux€(0, N). Тогда число 2rc(modN) является четным, если и только если a;(modiV) € (О, N/2).
Доказательство. Для всех чисел х ? (О, N/2) умножение 2a;(mod N) не требует выполнения операций по модулю, и, следовательно, результатом является число 2х — четное число из интервала (0,iV). И наоборот, если число 2:c(mod АГ) является четным, оно нацело делится на 2, причем для этого не требуется выполнять никаких операций по модулю. Следовательно, х ? (О, N/2). ?
Поскольку все целые числа из интервала (О, N/2) образуют ровно половину целых чисел из интервала (0,АГ), из леммы 9.1 следует, что число 2aj(modAT) является нечетным тогда и только тогда, когда х ? (N/2, N).
Перейдем к доказательству теоремы 9.1.
Доказательство. Необходимо показать, что П => I. Доказательство этого факта носит конструктивный характер. Построим алгоритм бинарного поиска, использующий надежный оракул РОгя и определяющий число т по тексту с = me(mod N), зашифрованному с помощью алгоритма RSA. Поиск осуществляется в интервале (а, о), который называется текущим и обозначается как CI (current interval). Первоначальным текущим интервалом является интервал (а, Ъ) = (О, N). В ходе бинарного поиска выполняются следующие инвариантные условия.
336
Часть III. Основные методы криптографа
• На каждой итерации интервал CI делится пополам.
• Искомый исходный текст по-прежнему принадлежит интервалу CI. Для простоты выполним только две итерации этого алгоритма.
Итерация Известно, что исходный текст принадлежит интервалу (а, Ь) = (0, АГя Передадим оракулу POn число 2ec(modiV). Заметим, что 2ес= (2m)e(mod ATI Тогда из ответа оракула РОдг(2ес) и леммы 9.1 следует, что либо те (О, АГ — АГ/21 либо тЕ (АГ/2, N). Таким образом, возникает новый текущий интервал, содержав щий исходный текст и имеющий вдвое меньшую длину. Итак, на вход итераци* поступил интервал (а, Ь) = (О, N), а на выходе получается один из двух интерва^ лов: (а, Ь) = (О, АГ/2) или (a, b) = (АГ/2, N).
Итерация Рассмотрим случай (о, Ь) = (АГ/2, АГ). Передадим оракулу число 22ес^ = (22m)e(mod АГ). Если РОдг(22ес) = 0, то исходный текст 22m = 4m(mod Ai является четным числом. По лемме 9.1 получаем, что 2m(modAT) б (О, АГ/2). Вспомним условие 2m < 2АГ. Следовательно, неравенство 2m(modAT) < АГ/2 возможно, только если 2m < 2АГ — АГ/2 = 3N/2. Итак, m < ЗАГ/4. Итак, m 6 (АГ/2, ЗАГ/4). Обновим текущий интервал, выполнив преобразование (о, Ь) <— (а, Ъ — I?)- Таким образом, инвариантные условия выполняются.
Читатели могут самостоятельно проверить два основных варианта преобразования текущего интервала.
• Если оракул POjv возвращает нуль, исходный текст принадлежит левой половине текущего интервала CI — (а, Ь), а число Ь следует уменьшить на величину |С/|/2.
• В противном случае исходный текст принадлежит правой половине теку-1 щего интервала CI = (о, Ь), и число а необходимо увеличить на значений \С1\/2.
Очевидно, что после г = [log2 N\ +1 шагов поиска длина текущего интервала] станет меньше единицы: \С1\ = Ь — а < 1. В этом случае алгоритм прекращает работу и выдает число т = Ь. Теорема 9.1 доказана. ?
Описание бинарного поиска исходного сообщения суммируется алгоритмом 9.1.
Пример 9.1. Допустим, что открытым ключом алгоритма RSA является пара (АГ, е) = (15,3), а шифрованный текст — с = 13. Зададим оракулу четыре вопроса и попробуем восстановить секретный текст т. Передадим оракулу следующие запросы:
(23 х 13,43 х 13,83 х 13,163 х 13) = (14,7,11,13)(modl5).
Глава 9. Идеальный мир: битовая стойкость.
337
Алгоритм 9.1. Бинарный поиск исходного текста, зашифрованного алгоритмом
RSA, с помощью оракула четности
ИСХОДНЫЕ ДАННЫЕ:
(N, е): параметры открытого ключа алгоритма RSA; с = me(mod N): текст, зашифрованный алгоритмом RSA; РО^: оракул четности, получающий текст, зашифрованный алгоритмом RSA, и возвращающий младший значащий бит соответствующего исходного текста.
РЕЗУЛЬТАТ:
т: исходный текст.
1. Выполнить инициализацию (а,Ь) «— (О, N).
(* Пока выполняется условие т е (а, Ь), длина текущего интервала CI = = (а, Ь) на каждой итерации делится пополам. *)
2. for г = 1,2,..., |k>g2Arj + 1 do {
(* Длина отрезка (а, Ъ) никогда не превышает число ^рг- *)
а) If (PON(2iec) = 0) then b*-b-§.
(* Число m лежит в левой половине интервала (а, Ь). *)
б) Else а <— а + ^;
(* Число т лежит в правой половине интервала (а,Ъ). *)
}
3. return (|bj)
Ответы оракула: 0, 1, 1, 1. На их основе можно сделать следующие выводы.
Первый ответ: 0 т ? (0,15 - 15/2) = (0,15/2), т.е. т ? [1,7].
Второй ответ: 1 => т ? (0 + 15/4,15/2) = (15/4,15/2), т.е. т ? [4,7].
Третий ответ: 1=>те (15/4 + 15/8,15/2) = (45/8,15/2), т.е. т ? [6,7].
