Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Заметим: из-за того, что сложение в формуле (9.5.1) выполняется по модулю р — 1, только одна из этих величин меньше а другая должна быть больше или равной этому числу. Очевидно, что квадратный корень, имеющий меньший дискретный логарифм по основанию д, является искомым. Однако проблема заключается в том, что по числам yfh и —у/h невозможно определить, какой из этих квадратных корней имеет меньший дискретный логарифм по основанию д\
Несмотря на это, если существует другой "битовый оракул", который по трой-ке (,9, У, —у) определяет, какое из чисел у и —у имеет меньший дискретный логарифм по основанию д (подобный оракул называется "половинчатым" ("half-order oracle")), его можно применить для определения искомого квадратного корня. Функционирование такого "половинчатого" оракула описывается алгоритмом 9.3.
Поскольку проверка символа Лежандра и вычисление квадратных корней по модулю простого числа допускают эффективную реализацию, алгоритм 9.3 означает, что проверка неравенства log5 h < ordW для заданной пары (д, h) эквивалентна вычислению величины logg h по заданной паре (д, К).
Алгоритм 9.3 носит более общий характер, чем алгоритм 9.2. Он сохраняет работоспособность, даже если число д имеет нечетный порядок. Рассмотрим небольшой числовой пример.
Пример 9.3. Допустим, мы имеем доступ к половинчатому оракулу. Рассмотрим группу Z23, порождающий элемент д = 5 и элемент h = 9. Вычислим величину х = log5 9(raod22), вызывая "половинчатый" оракул.
Алгоритм 9.3, на вход которого поступает тройка (5,9,23), работает так, как показано на рисунке. Каждая двойная стрелка означает "извлечение квадратного
Глава 9. Идеальный мир: битовая стойкость.
343
Алгоритм 9.3. Дискретное логарифмирование с помощью "половинчатого" оракула
ИСХОДНЫЕ ДАННЫЕ:
(fifi h,p) : д — порождающий элемент группы F*, р — простое число, h = ^(modp), РО(рЭ): "половинчатый оракул".
РО(р,э)(^У,-у) =
{-
если log^y <logff(-y), у в противном случае.
РЕЗУЛЬТАТ:
х: целое число.
1. Выполнить присваивание х «— 0.
2. Повторять следующие шаги, пока h^l. {
а) If (h е QNRp) then h «- h/g; ж «- ж + 1.
(* Если h 6 QNRp, то logff h — нечетное число. В этом можно убедиться,
проверив символ Лежандра = —1. *)
б) h <— POfag) (д, y/h, —yflij ; х <— 2х. (* Извлечение квадратного корня выполняется без труда, но для этого необходим оракул, сообщающий нам, который из корней является
л, log„/l 4.
искомым, т.е. имеет меньший дискретный логарифм —^—. *)
}
3. return (ж).
корня", причем горизонтальные двойные стрелки (=s>) обозначают выбор "половинчатого" оракула. Каждая одинарная стрелка (—») означает "деление числа д", где д = 5. Все вычисления производятся по модулю 23.
9=>20->4=>2=>5->1=>1
3 21 18 22
В начале алгоритма переменная х инициализируется нулем (шаг 1), для каждой двойной стрелки =^ выполняется операция х «— 2х (шаг 2.2), а для каждой одинарной стрелки —> — операция х <— х +1 (шаг 2.1). По завершении алгоритма заключительное значение переменной х равно 10. Действительно, 9 = 510(mod23). о
344
Часть III. Основные методы криптографии
Эти результаты показывают, что распознать отдельный бит дискретного логарифма так же сложно, как и расшифровать весь блок. Теперь можно утверждагы| что если порождающий элемент группы является квадратичным вычетом, то вст биты дискретного логарифма, включая младший значащий бит, являются стой! кими. Это обеспечивает семантическую стойкость криптосистемы Эль-Гамаля| которая будет описана в главе 14.
9.6 Резюме
Исследование битовой стойкости основных криптосистем с открытым ключом неизменно приводит к утешительным выводам: каждый отдельный бит исходив го текста, скрытый такими функциями, распознать так же сложно, как и вел блок. Если исходное сообщение является случайным, то извлечь информацию об исходном тексте так же трудно, как вычислить обратную функцию шифрования!
Многие исследователи использовали этот факт для создания более стойких| криптосистем с открытым ключом без применения основных примитивов. Иде! этих криптосистем заключается в рандомизации исходных сообщений. В части V будет описана общая методология под названием модель случайного оракул! (random oracle model), позволяющая создавать криптосистемы с открытым клю! чом (а также схемы цифровой подписи), стойкость которых является сильно!| и доказуемой.
Изучая основные криптографические функции с открытым ключом, мы убедились, что все они уязвимы для активных атак. Общая методология создания алг! ритмов шифрования с открытым ключом, рассмотренная в части V, также предщ сматривает создание механизмов, позволяющих предотвратить активные атаки
Упражнения
9.1. Решите еще три варианта задачи о двух итерациях, описанной в теореме 9.\
а) (а,Ь) = (N/21N)1PON(22ec) = 1.
б) (а, Ь) = (О, N/2), PON(22ec) = 0.
в) (а,Ь) = (0,N/2),PON(22ec) = 1.
9.2. При каких условиях алгоритм шифрования RSA обладает свойством битовой стойкости?
Подсказка: может ли алгоритм шифрования обладать свойством битовой стойкости, если исходный текст содержит верифицируемую частичную и^ формацию?
