Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
340
Часть III. Основные методы криптографии
числа следующей последовательности.
хо, х\ = xq, ..., Xi = xj_i,... (mod N) (9.3.1)
Как показано в работах [42, 128], не зная начальное значение xq, предсказать младч шие значащие биты в последовательности (9.3.1) так же сложно, как разложит! целое число Блюма N на простые множители.
Примечание 9.1. В работах [13, 295] доказано, что задача одновременного вьи числения log2 log2 N младших значащих битов в зашифрованном тексте Рабина эквивалентна решению задачи о разложении числа N на простые множители. Я
Блюм и Голдвассер (Goldwasser) применили этот результат и предложили эффективную криптосистему, обладающую семантической стойкостью (semantiq security). Эта криптосистема изучается в главе 14.
9.4 Битовая стойкость криптосистемы Эль-Гамаля
Поскольку в криптосистеме Эль-Гамаля пространством исходных сообщений является группа F*, где р — большое простое число (следовательно, нечетное)! к ней также можно применить алгоритм бинарного поиска. Для того чтобы най^ ти исходное сообщение, зашифрованное в виде пары (ci,c2), оракулу четности посылаются запросы, имеющие следующий вид.
(сь2V2) (modp),г =1,2,..., [log2pJ + 1.
Если оракулом четности является человек (что вполне вероятно, см. при мер 9.2), то для того, чтобы снять подозрения, атакующий может замаскировз запросы, представив их следующим образом.
(ffr,cb 2гуг*с2) (modp), где rt € и%р-и г = 1,2,..., [log2p\ + 1,
где пара (д,у) содержит параметры открытого ключа, принадлежащего ораку; лу четности. Хотя эти Llog2 joj + 1 пар зашифрованных сообщений абсолютн независимы друг от друга, они шифруют зависимые сообщения 2lm(modp), гя i = l,2,...,[log2pJ +1.
(gk+Ti,ук+г'2'т) (modp), г = 1,2,..., Llog2pJ + 1.
Отсюда следует, что распознать младший значащий бит в схеме Эль-Гамал так же сложно, как взломать весь блок сообщения. С другой стороны, владеле-открытого ключа должен проявлять осторожность, чтобы не поддаться на уловки описанные в примере 9.2.
Глава 9. Идеальный мир: битовая стойкость.
341
9.5 Битовая стойкость дискретного логарифма
В разделе 8.4 мы выяснили, что проблема вычисления дискретного логарифма в абелевой группе в общем случае весьма сложна: функция дх считается однонаправленной. Однако до сих пор неизвестно, является ли она функцией с секретом. По этой причине определять число х по степени дх — довольно странная идея. Однако для того, чтобы продемонстрировать связь между битовой и блочной стойкостью дискретного логарифма, предположим, что существует оракул, который может сообщать частичную информацию о битах числа х, получая пару (9,9х)-
Если элемент д имеет нечетный порядок ard(g), не являющийся секретом, можно найти число ^(modord^)). (Эта ситуация встречается довольно часто.) В этом случае дискретное логарифмирование с помощью оракула четности, по существу, сводится к побитовому выполнению операции, обратной к возведению в степень по модулю (алгоритм 4.3). Поскольку алгоритм возведения в степень по модулю называется также методом "возведения в квадрат и умножения" ("squaring-and-multiplying"), обратный алгоритм можно назвать методом "извлечения квадратного корня и деления" ("square-rooting-and-dividing").
Алгоритм 9.2. Дискретное логарифмирование с помощью оракула четности ИСХОДНЫЕ ДАННЫЕ:
h): д — элемент группы, имеющий нечетный порядок, h = дх;
¦POdesc(a): оракул четности; POdesc^)(g, h) = loga /i(mod2). РЕЗУЛЬТАТ:
x: целое число.
1. Выполнить присваивание х *— 0, у <— ^(modord(g)).
2. Повторять следующие шаги, пока h^l. {
а) If (POdesc(g){g, h) == l) then h «- h/g; x <- x + 1.
(* Если loga h — нечетное число, выполнить операцию "поделить и прибавить единицу", обратную по отношению к операции "умножить и вычесть единицу" при возведении в степень по модулю. *)
б) h<- h»;x «-2x.
(* Если loga h — четное число, выполнить операцию "извлечь квадратный корень и удвоить", обратную по отношению к операции "возвести в квадрат и поделить пополам" при возведении в степень по модулю. *)
}
3. return (х).
342
Часть III. Основные методы криптографии
Что произойдет, если элемент д имеет четный порядок? Например, если число д — это порождающий элемент группы ?*, где р — простое число, то число ordp(g) = р — 1 является четным и не является взаимно простым с числом 2. Следовательно, числа ^(raodp — 1) не существует. Таким образом, квадратный корень из числа h на шаге 2.2 извлечь невозможно.
Однако, если число д является порождающим элементом группы ?*, квадратный корень из числа h по модулю р можно вычислить с помощью алгоритма 6.4. Для любого квадратичного вычета /i€ QRp алгоритм извлечения квадратного корня возвращает два квадратных корня числа h, которые обозначаются как ±y/h. Поскольку число д является порождающим элементом группы F*, выполняется условие д е QNRp, но h е QRp. Следовательно, число log5 h должно быть четным. Итак, не ограничивая общности, можно утверждать, что дискретные логарифмы двух квадратных корней h по основанию д вычисляются по следующим формулам.
bgs^ = ^,lcgs(-^)=?^i + ^. (9.5..)
