Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
614
Часть V. Методы формального доказательства стойкости
запросы можно возвращать старые ответы. Возможно, для доказательства стойкости схемы DSS ее следует представить в виде тройной схемы Эль-Гамаля, хэшировав фиксирующее значение.
• Пойнтшеваль и Штерн [235] предложили доказательство стойкости схемы цифровой подписи Фиата (Fiat) и Шамира (Shamir) [109]. В доказательстве использовался тот факт, что схема Фиата и Шамира, по существу, является тройной. Эта схема цифровой подписи представляет собой модификацию схемы идентификации с нулевым разглашением, описанной в следующей главе.
16.3.3 Метод "тяжелых строк"
Существует еще один метод доказательства неуязвимости схем цифровой подписи Эль-Гамаля. Он называется методом "тяжелых строк" (heavy row technique) и предложен Фейджем (Feige), Фиатом и Шамиром [106] для доказательства стойкости схемы идентификации с нулевым разглашением Фиата и Шамира [109]. (Свойства этого протокола с нулевым разглашением будут изучены в разделе 18.2.2.) Поскольку этот протокол идентификации легко преобразовать в тройную схему Фиата-Шамира (хотя и не Эль-Гамаля), метод "тяжелых строк" непосредственно распространяется на тройные схемы Эль-Гамаля. Этот факт доказан в работе [222]. Рассмотрим краткое описание метода "тяжелых строк" для доказательства стойкости тройных схем цифровой подписи из семейства Эль-Гамаля.
Предположим, что Злоумышленник фальсифицирует подпись с преимуществом Adv. Тогда количество вызовов Злоумышленника, которые должен сделать Саймон, прямо пропорционально величине 1/ Adv (оно равно 3/ Adv).
Представим себе гигантскую бинарную матрицу Н, состоящую из д строк и д столбцов. Строки соответствуют всем возможным случайным выборам первого элемента тройки в схеме цифровой подписи Эль-Гамаля, а столбцы — второго элемента. Элемент hij матрицы Н равен 1, если тройка s) является корректной подписью, и 0 — в противном случае. Строка называется "тяжелой", если она содержит по крайней мере две единицы.
Лемма 16.1 (Лемма о "тяжелых строках"). Вероятность появления единицы в матрице И и в "тяжелых" строках равна по крайней мере 1/2. ?
Эта лемма верна, поскольку "тяжелые" строки содержат больше единиц, чем остальные.
Поскольку Злоумышленник может фальсифицировать подпись в тройной схеме с преимуществом Adv, в матрице Н есть Adv -§2 единиц. Выполняя свой алгоритм 1/ Adv раз, Злоумышленник должен создать корректную подделку (i,j,s). По лемме о "тяжелых строках" вероятность того, что г-я строка окажется "тяжелой", равна по крайней мере 1/2. Теперь, выполняя свой алгоритм еще 2/ Adv раз
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
615
при фиксированном числе г, Злоумышленник успешно создает еще одну корректную подпись (г,/, s'), где f ф j.
Как мы уже знаем, эти подписи позволяют вычислить дискретный логарифм, т.е. приводят к противоречию.
Представленное выше описание метода "тяжелых строк" является интуитивным. Мы не стали упоминать о парадоксе дней рождения, который может привести к увеличению вероятности. Точное описание метода содержится в работе [222].
16.4 Прикладные варианты схем цифровой подписи RSA и Рабина
Функции RSA и Рабина являются однонаправленными перестановками с секретом (OWTP). В результате учебные варианты этих схем цифровой подписи (см. разделы 10.4.2 и 10.4.4) являются детерминированными алгоритмами. Это означает, что подпись сообщения М однозначно определяется заданными ключом (sk,pk) и сообщением М.
В криптографии детерминированность нежелательна. В учебной схеме цифровой подписи Рабина детерминированность открывает возможность для разрушительной атаки, продемонстрированной в разделе 10.4.5. Атака на основе адаптивно подобранных сообщений позволяет Злоумышленнику вычислить два разных квадратных корня выбранного сообщения и разложить модуль на множители. Следовательно, прикладные варианты схем RSA и Рабина должны быть вероятностными.
16.4.1 Подпись с помощью рандомизированного заполнения
Вероятностные варианты схем RSA и Рабина были разработаны Белларе и Роджуэем [26]. Они назвали свой метод вероятностной схемой цифровой подписи (probabilistic signature scheme — PSS). Эта схема представляет собой модификацию функций RSA (и Рабина) с помощью рандомизированного заполнения. Для простоты рассмотрим лишь вариант схемы Рабина.
Как и схема заполнения ОАЕР (см. рис. 15.1), схема заполнения PSS основана на функциях хэширования. В схеме RSA-OAEP процедура шифрования представляет собой преобразование, использующее однонаправленную функцию RSA. В схеме RSA-PSS процедура подписания — это преобразование, использующее секрет функции RSA, поскольку автор подписи владеет закрытым ключом.
616
Часть V. Методы формального доказательства стойкости
Рис. 16.3. Заполнение PSS
16.4.2 Вероятностная схема цифровой подписи — PSS
Рассмотрим алгоритм для функции RSA. Для схемы Рабина рассуждения проводятся аналогично.
Процедура заполнения по схеме PSS продемонстрирована на рис. 16.3, а схема цифровой подписи описывается алгоритмом 16.1.
Алгоритмы подписи и верификации используют две функции хэширования. Первая функция, Н : {0,1}* ¦—> {0, l}fel, называется компрессором (compressor), а вторая функция, G : {0, l}fel ¦—> {0, \)k~kl~l _ генератором (generator). При анализе стойкости эти функции хэширования имитируют случайных оракулов.
