Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Формально говоря, свойство перемешивания, присущее алгоритмам шифрования (раздел 7.1), также играет важную роль в схемах цифровых подписей. Алгоритм Sign должен равномерно распределять цифровые подписи по всему пространству подписей S. Это предотвращает подделку подписей без помощи | соответствующего ключа.
i 10.4.1 Учебные схемы цифровых подписей
Как и алгоритмы шифрования с открытым ключом, рассмотренные в главе 8, описываемые в этой главе схемы цифровой подписи являются очень нестойкими.
Свойство 10.2 (Учебные схемы цифровой подписи). В рамках этой главы рассматривается ограниченное понятие стойкости схем цифровой подписи. Будем говорить, что цифровая подпись является стойкой, если ее фальсификация требует огромных усилий. Иначе говоря, атакующий по заданному открытому ключу и описанию схемы цифровой подписи не в состоянии создать пару "сообщение-подпись", которая была бы приписана законному владельцу открытого ключа Атакующий не способен адаптироваться, т.е. он не стремится облегчить процесс фальсификации цифровой подписи, используя доступные ему пары "сообщение-подпись" или взаимодействуя с законным автором сообщения.
Следует заметить, что это понятие стойкости совершенно не пригодно для практического применения, поскольку основано на предположении, что атакующий неестественно слаб и находится в агрессивном окружении. На самом деле атакующий может легко получить в свое распоряжение пары "сообщение-подпись" вместе с открытым ключом и описание цифровой подписи, поскольку это не является секретной информацией. Кроме того, как правило, атакующий имеет возможность обращаться к источнику с просьбой подписать сообщение по своему выбору. Такой атакующий умеет адаптироваться, поскольку он выбирает сообщения по своему усмотрению. В ходе атаки на основе адаптивно подобранного сообщения (adaptive chosen-message attack) атакующий получает целевое сообщение (target message), подбирает на его основе подходящие сообщения (возможно, выполняя алгебраические преобразования исходного сообщения) и посылает их автору на подпись. Все это выглядит так, будто автор обучает злоумышленни-I ка подделывать свою подпись. Задачей атакующего является подделка подписи [в целевом сообщении. Как указано в разделе 8.6 при обсуждении эффективности адаптивных атак на криптосистемы, атака на основе адаптивно подобранного
358
Часть III. Основные методы криптографии
сообщения не только намного эффективнее обычных атак, но и вполне реальна. Таким образом, ей следует уделить особое внимание.
Напомним, что до сих пор мы рассматривали теоретическую стойкость учебных алгоритмов шифрования с открытым ключом. Мы несколько раз предупреждали, что владелец открытого ключа не должен предоставлять атакующей услуги оракула. Такой уровень бдительности можно обеспечить только в tcJ случае, если владелец ключа достаточно опытен. Следовательно, для предотвря щения адаптивных атак не следует полагаться на квалификацию пользователе^ При описании схем цифровых подписей мы не будем требовать от пользовате^ не предоставлять услуги оракула, поскольку этого иногда невозможно избежали во многих приложениях подпись присланных сообщений считается вполне ест^ ственной.
Строгое понятие стойкости схем цифровой подписи, которое можно назвать стойкостью к атакам на основе адаптивно подобранного сообщения (adaptive chosen-message attack), будет сформулировано в главе 16. Оно является аналоге! понятия практической стойкости криптосистем к атакам ССА2 (определение 8.1 в разделе 8.6).
Отметим простой, но вполне невинный вид подделки подписи.
Примечание ЮЛ (Экзистенциальная подделка). Алгоритмы (Signsfc, Verifyp 1 образуют пару однонаправленных функций с секретом. Алгоритм Verifypfc прет ставляет собой однонаправленный компонент пары, a Signsfc — функцию с секра том. Как правило, функция Verifypfc(s, т) вычисляется в направлении от s к ттм Следовательно, многие схемы цифровой подписи, основанные на однонаправлеш ных функциях с секретом, позволяют эффективно подделывать правильные парщ "сообщение-подпись", применяя функцию Verifypfc в направлении от s к т. Ос нако благодаря свойству перемешивания, которым обладает функция VerifypJ "сообщение", порожденное на основе "подписи" с помощью функции Verify^ выглядит случайным и бессмысленным. Такой способ подделки цифровых подпш сей называется экзистенциальным (existential forgery). Схемы цифровой подписи основанные на применении однонаправленных функций с секретом, как правился допускают экзистенциальную подделку. Предотвратить такие подделки можно с помощью включения в сообщение избыточной информации, позволяющей верификатору выявить неслучайное распределение сообщений. с
Рассмотрим несколько схем цифровой подписи.
10.4.2 Цифровая подпись RSA (учебный вариант)
Схема подписи RSA впервые была предложена Диффи и Хеллманом, а затем реализована Ривестом, Шамиром и Адлеманом [246].
Глава 10. Методы защиты целостности данных
359
Алгоритм 10.1. Схема цифровой подписи RSA Генерация ключа
Процедура генерации ключа такая же, как и в криптосистеме RSA (алгоритм 8.1). (* Следовательно, параметрами ключа Алисы является пара (N, е), где N = pq, р и q — большие простые числа приблизительно одинаковой величины, е — целое число, удовлетворяющее условию gcd(e, (}>{N)) = 1. Алиса также определяет целое число d, удовлетворяющее условию ed = l(mod<^(Ar)). Целое число d является закрытым ключом Алисы. *)
