Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
619
М\\г
г\\М
М
Н
н
е
-е
Исходный вариант схемы PSS-R Белларе-Роджуэя
Вариант Корона и др.
Рис. 16.4. Заполнение PSS-R
16.4.4 Универсальная схема заполнения PSS-R для подписи и шифрования
На рис. 16.4 показаны два вида заполнения PSS-R: слева изображена схема Белларе-Роджуэя [26], а справа — схема Корона и его соавторов [83]. Универсальная схема заполнения для подписи и шифрования описана в виде алгоритма 16.4.4.1.
В универсальной схеме заполнения RSA процедура подписания и шифрования называется PSS-R-Padding. Она получает на вход сообщение М е {0, \}к~к^~ко^ а также показатель степени и модуль функции RSA. Показатель степени функции RSA играет роль параметра d при генерации подписи и параметра е — при шифровании. Отметим, что в отличие от схемы подписи PSS, в которой сообщение могло иметь неограниченную длину, теперь длина сообщения равна к — кг — — ко. Процедура верификации подписи и расшифровки с проверкой целостности данных называется PSS-R-UnPadding. На ее вход поступает число U < N и компоненты ключа RSA, а результатом ее работы является элемент множества {True, False}U{0, iyk~kl~k°m Если первым компонентом вывода является значение True, остальная битовая строка представляет собой восстановленное сообщение, в противном случае остальная часть — это нулевая строка NULL.
16.4.4.1 Доказательство стойкости
Доказательство стойкости схемы шифрования и цифровой подписи RSA-PSS-R имеет много общего с доказательствами стойкости как схемы шифрования RSA-OAEP (первая часть), так и схемы цифровой подписи RSA-PSS (вторая часть). Следовательно, повторять его не имеет смысла. Детали можно найти в работе [83].
620
Часть V. Методы формального доказательства стойкости
Алгоритм 16.2. Универсальная схема заполнения RSA для подписи и шифрования Параметры ключа
Пусть (AT, е, d, G, Н, ко, к\) *—и Gen(lfe), где тройка (AT, е, d) — компоненты ключа RSA, причем пара (АГ, е) — открытый компонент, а число d = е-1 (mod $(ЛГ)) ~ закрытый компонент; к = \N\ = ко + к\ такие, что числа 2~к° и 2~kl являются пренебрежимо малыми; G и Н — функции хэширования, удовлетворяющие условиям
G : {0, l}fel ¦-> {0, l}*-*1"1, Н : {0, l}^"1 _» {0, l}fcl .
Генерация подписи PSS-R-Padding(M,x, N) =
1. г 4-гу {0, l}fe° ; w ЩМ || г); s <- G(w) Ф (М || г); у 4- (w || s);
2. if(y^AT)gotol;
3. return(ya:(mod AT)).
Верификация подписи
PSS-R-UnPadding([/,'c,Ar) = у<- Ux(moAN); Представить строку у в виде w || s.
(* Иначе говоря, w — первые к\ бит, as — остальные к — к\ бит. *) Представить строку G(w) © s в виде М || г.
(* Иначе говоря, М — первые к — fcj — ко 6т, а г — остальные /со бит. *) if (Я(М || г) = w) гешгп (True || М) else return(False || Null).
16.4.4.2 Выводы
• Для того чтобы длина результата заполнения в схеме PSS-R-Padding была меньше числа АГ, применяется метод проб и ошибок. Вероятность ошибки при повторении проверки г раз равна 2~\ Как альтернативу в качестве заполнителя можно применить ведущий нуль.
• При шифровании по схеме PSS-R-Padding проверка целостности данных сводится к проверке значения функции хэширования. Этот метод отличается от схемы заполнения ОАЕР, в которой проверке подвергалась строка избыточных нулей.
• Анализ стойкости схемы шифрования PSS-R-Padding к атаке IND-CCA2, по существу, совпадает с доказательством стойкости схема RSA-OAEP. Он осуществляется с помощью редукции атаки к частичному инвертированию функции RSA, когда величина w известна. Иначе говоря, если Злоумышленник может взломать систему с преимуществом Adv, то в ходе атакующей игры с Саймоном-имитатором Злоумышленник должен посылать запросы
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
621
к оракулу G приблизительно с тем же преимуществом. Поскольку реализация атакующего алгоритма приводит к частичному инвертированию, чтобы выполнить полное инвертирование, его необходимо провести несколько раз. Как показано в разделе 15.2.4, для того, чтобы получить противоречие, алгоритм Злоумышленника нельзя выполнять больше двух раз (т.е. сложность редукции представляет собой полиномиальный алгоритм степени 2).
• Даже если алгоритм Злоумышленника выполняется всего два раза, редукция оказывается не очень точной. Последствия этого факта указаны в разделе 15.2.5. Для того чтобы получить необходимое противоречие, модуль функции RSA в схеме RSA-PSS-R должен состоять как минимум из 2048 бит.
• Для того чтобы выполнялось условие |ги| > Щ^-, алгоритм Злоумышленника
необходимо реализовать не меньше двух раз. Следовательно, \М| |r| ^ Итак, схема заполнения RSA-PSS-R имеет довольно узкую полосу пропускания для восстановления сообщений: размер восстанавливаемого сообщения не должен превышать половину размера модуля. Как правило, выбирая параметры А; = \N\ = 2048 и ко = 160, можно получить максимум \М\ = = ^ — fco = 1024 — 160 = 862, т.е. модуль \М\ составляет приблизительно 42% от величины |АГ|.
• По причинам, указанным в разделе 16.4.2.1, процесс редукции в доказательстве стойкости схемы цифровой подписи RSA-PSS-R к атаке на основе адаптивно подобранных сообщений является неполным. Это объясняется тем, что успешная фальсификация подписи может привести к полному инвертированию функции RSA. Таким образом, в отличие от доказательства, рассмотренного в предыдущем абзаце, для стойкости схемы условие |гу| > ЦР- не является обязательным. Достаточно установить параметры ко и fc] так, чтобы величины 2~к° и 2~kl стали пренебрежимо малыми. На практике часто выбирают ко = к\ = 160. Таким образом, величина \М\ = = к — ki — ко может быть довольно большой. В наиболее типичном случае, когда к = \N\ — 2048 и к0 = ki = 160, выполняется условие \М\ = 2048 — — 320 = 1728, т.е. величина \М\ составляет 84% от величины |АГ|.
