Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Генерация подписи
Для цифровой подписи сообщения т е Алиса генерирует число
s = Signd(m) <— md(mod N).
Верификация подписи
Допустим, Боб должен удостовериться, что параметры открытого ключа (N, е) действительно принадлежат Алисе. Боб применяет к паре (m, s) следующую процедуру верификации.
Verify(/у)е)(т, s) = True, если m = se(mod N).
(* Примечание: сообщение m должно быть распознаваемым (см. раздел 10.4.3). *)
Очевидно, что процедура цифровой подписи RSA совпадает с алгоритмом шифрования и расшифровки RSA (раздел 8.5), за исключением того обстоятельства, что Алиса сначала шифрует сообщение своим закрытым ключом, а Боб (или кто-либо еще) впоследствии расшифровывает его с помощью открытого ключа Алисы. Верификация подписи основана на тех же самых соображениях, что и алгоритмы шифрования и расшифровки RSA в разделе 8.5.
10.4.3 Неформальное обоснование стойкости цифровой подписи RSA
Если бы схема цифровой подписи RSA была настолько простой, как мы ее описали, ее было бы нетрудно подделать. Например, Боб может извлечь случайное число s 6 "L*N и вычислить величину
m«-se(modA0- (10.4.1)
Разумеется, процедура верификации пары (m,s) вернет результат True. Кроме того, благодаря мультипликативному свойству функции RSA (8.9.1) по существующим парам "сообщение-подпись" (mi,si) и (т2, s2) нетрудно создать новую, фальсифицированную пару {mim2, sis2).
360
Часть III. Основные методы криптографии
Как сказано в замечании 10.1, описанный выше способ фальсификации подписи называется экзистенциальным. Поскольку сообщение, созданное либо процедурой (10.4.1), либо в результате умножения, выглядит совершенно случайным, экзистенциальную фальсификацию можно предотвратить, включив в сообщение т дополнительную распознаваемую информацию так, чтобы сообщение т стало неслучайным или "осмысленным". Простейший способ добавить такую информацию — вставить в сообщение распознаваемую строку, т.е. m = М || I, где М — подписанное сообщение, г I — распознаваемая строка, например, имя автора.
Наиболее часто для включения дополнительной информации сообщение хэ-' шируется с помощью криптографической хэш-функции (10.3.1). Пусть h — функция хэширования, отображающая множество {0,1}* в пространство Л4- Сообщение тле Л4 считается распознаваемым или осмысленным, если существует строка М ? {0,1}*, удовлетворяющая условию
m = h(M).
При таких условиях подделка подписи RSA усложняется. Вычисление сообщения тп, соответствующего подписи s в формуле (10.4.1), уже не приводит к нужному результату, если атакующий не может придать распознаваемому сообщению осмысленный вид, т.е. не имеет в своем распоряжении прообраз сообщения т до применения к нему функции хэширования. Если предположить, что функция хэширования является случайным оракулом, описанным в разделе 10.3.1.2, то "подделка с нуля" цифровой подписи RSA по заданному сообщению по трудности сравнима с решением задачи RSA, т.е. извлечению корня е-й степени числа N по некоторому модулю (определение 8.4 в разделе 8.7).
Следует однако заметить, что в настоящее время не существует ни одного формального доказательства этого факта. Совершенно очевидно, что учебный вариант цифровой подписи RSA не обладает доказуемой стойкостью. Даже для простейших функций хэширования никому не удалось доказать стойкость цифровой подписи RSA к атакам на основе адаптивно подобранных сообщений. Следовательно, описанную выше схему цифровой подписи RSA следует считать учебной.
Более стойкая схема цифровой подписи RSA, использующая функцию хэширования, описана в главе 16. Этот алгоритм является вероятностным, т.е. генерируемые подписи случайным образом распределяются по всему пространству подписей, причем полученное распределение невозможно отличить от равномерного. Благодаря этому свойству данная схема цифровой подписи вполне пригодна для практического применения. Формальное доказательство строгой стойкости цифровой подписи RSA будет изложено в главе 16.
Глава 10. Методы защиты целостности данных
361
10.4.4 Цифровая подпись Рабина (учебный вариант)
Схема цифровой подписи Рабина [240] очень напоминает схему цифровой подписи RSA. Разница между ними заключается лишь в процедуре верификации. В цифровой подписи RSA показатель верификации е представляет собой нечетное число, поскольку должно выполняться условие gcd(e, <{>(N)) = 1, где <{>(N) — четное число, а в схеме Рабина е = 2.
Схема цифровой подписи Рабина описывается алгоритмом 10.2. Заметим, что она носит исключительно учебный характер.
Алгоритм 10.2. Схема цифровой подписи Рабина Генерация ключа
Процедура генерации ключа такая же, как и в криптосистеме RSA (алгоритм 8.1). (* Следовательно, выполняется условие N = pq, pnq — разные нечетные простые числа приблизительно одинаковой величины. Число N — открытый ключ Алисы, а числа р и q — параметры ее закрытого ключа. *)
Генерация подписи
Для цифровой подписи сообщения т е Алиса вычисляет значение
s *— m^^modn).
(* Для того чтобы это вычисление было возможным, необходимо, чтобы выполнялось условие т е QR/v- Из раздела 6.6.2 следует, что если N — модуль алгоритма RSA, то #QR/v = #Z^/4, т.е. четверть элементов группы "L*N принадлежит множеству QR/v- Таким образом, Алиса может использовать подходящий механизм форматирования сообщения так, чтобы выполнялось условие т € QR^. Применив к такому сообщению т алгоритм 6.5, Алиса может вычислить его квадратный корень. *)
