Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Какую роль играет ведущий нуль? Зная длины функций хэширования и случайного ввода, можно определить, что в результате заполнения возникают к — 1 бит. Итак, добавление ведущего нуля приводит к созданию fc-битовой строки, которую можно интерпретировать как целое число, которое меньше числа N. Это необходимо для правильного возведения в степень по модулю. Другим способом, гарантирующим, что в результате заполнения длина строки будет меньше числа N, является заполнение /с-битовой строки с последующей проверкой. Этот метод включен в описание алгоритма заполнения RSA-OAEP (алгоритм 10.6), который незначительно отличается от исходного вариата, описанного в работе [24].
16.4.2.1 Доказательство стойкости
Формальное доказательство стойкости схемы RSA-PSS основано на методе редукции, использующем модель случайного оракула [26]. Оно снова сводится
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
617
Алгоритм 16.1. Вероятностная схема цифровой подписи (PSS) Параметры ключа
Пусть (AT, е, d, G, Н, ко, к\) <—у Gen(lk), где тройка (AT, е, d) — параметры ключа RSA, причем пара (АГ,е) — открытый компонент, а число d = e-1(mod</>(AT)) — закрытый компонент; к = \N\ = ко + к\ такие, что числа 2~к° и 2-fcl являются пренебрежимо малыми; G и Н — функции хэширования, удовлетворяющие условиям
G : {О, I}*1 ~ {О, I}*"**"1, Я : {0,1}* ь-> {0, l}fcl .
(* Битовая строка, являющаяся результатом функции G, разбивается на две подстроки — строку G\, состоящую из ко старших битов, и строку Gi, состоящую из остальных к — к\ — ко — 1 бит. *)
Генерация подписи
SignPSS(A/,d,AO =
г <-и {0, l}fco ; w <- Н{М || г); г* Gi(w) в г;
1/.-0||Ш||г*|| G2(w);
return(yd(mod AT)).
Верификация подписи
VerifyPSS(Af,U,e,N) = y+- t/e(modAT);
Представить строку у в виде 6 || w || г* || у.
(* Иначе говоря, 6 — первый бит строки y,w — следующие ki бит,
г* — следующие к0 бит, 7 — остальные биты. *) г *- г* в Gi(w);
if (#(Af К г) = w Л G2(i<;) = 7 Л 6 = 0) return(True) else return(False).
к противоречию: успешная подделка приводит к инвертированию функции RSA, т.е. к решению трудноразрешимой задачи. Процесс редукции очень похож на процесс редукции алгоритма заполнения RSA в схеме шифрования (например, см. раздел 15.2).
¦ В частности, редукция в доказательстве стойкости схемы RSA-PSS также представляет собой преобразование процесса фальсификации в частичное инвертирование функции RSA (см. раздел 15.2.3.4, в котором атака IND-CCA2 приводит к раскрытию числа s*, являющегося корнем е-й степени зашифрованного оклика с*). Несмотря на это доказать стойкость схемы цифровой подписи легче, чем доказать неуязвимость схемы шифрования: частичное инвертирование функции RSA может непосредственно привести к ее полному инвертированию без повторного выполнения алгоритма Злоумышленника, как к схеме шифрования. Это возмож-
618
Часть V. Методы формального доказательства стойкости
но благодаря вычислительной природе процесса фальсификации подписи: при успешной фальсификации Злоумышленник должен передать Саймону пару сообщение-подпись, которую можно верифицировать с помощью однонаправленной функции (в частности, с помощью функции RSA). В противоположность этому при успешной атаке IND-CCA2 Злоумышленник предоставляет Саймону намного меньше информации, просто угадывая один бит. По этой причине Саймон не имеет ни одной однонаправленной функции, чтобы установить связь между угаданным исходным текстом и зашифрованным окликом. В результате инверсия оказывается частичной. Итак, при шифровании редукция означает повторное выполнение алгоритма Злоумышленника путем сдвига позиции частичной инверсии, что приводит к полной инверсии функции.
Непосредственным итогом полной инверсии является эффективная редукция: преимущество Adv, с которым Злоумышленник фальсифицирует подпись, почти точно преобразуется в преимущество Саймона Adv', т.е. Adv'«Adv. Белларе и Роджуэй назвали результат такой редукции точной стойкостью (exact security) схемы цифровой подписи, основанной на алгоритме заполнения RSA.
Поскольку доказательство стойкости схемы цифровой подписи RSA-PSS до- • вольно сложно и очень похоже на доказательство стойкости схемы шифрования RSA-OAEP, мы не приводим его. Заинтересованные читатели могут найти его полное описание в работе [26].
16.4.3 Схема PSS-R с восстановлением сообщения
Поскольку схема шифрования RSA-OAEP позволяет владельцу закрытого ключа восстановить зашифрованное сообщение, можно представить себе противоположную ситуацию: схема цифровой подписи, основанная на заполнении с возможностью восстановления сообщения, также может разрешить любому лицу, владеющему корректным открытым ключом, восстановить подписанное сообщение. Именно этим свойством обладает схема PSS-R (Probabilistic Signature Scheme with Message Recovery). Белларе и Роджуэй распространили эту схему заполнения на функции RSA и Рабина [26].
Мы опишем вариант исходной схемы заполнения PSS-R, разработанной Белларе и Роджуэем. Этот вариант предложен Короном (Согоп) и его соавторами [83]. Мы выбрали его, поскольку авторы доказали не только стойкость для ситуации, когда подпись создана с помощью секрета функции RSA, но и стойкость шифрования, когда зашифрованный текст создан с помощью однонаправленной части функции RSA. Таким образом, описанная схема цифровой подписи является стойкой к атаке на основе адаптивно подобранных сообщений, а соответствующая схема шифрования — стойкой к атаке IND-CCA2.
