Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Верификация подписи
Допустим, Боб должен удостовериться, что открытый ключ N действительно принадлежит Алисе. Боб применяет к паре (m, s) следующую процедуру верификации.
Verify^(m, s) = True, если т = s2(modi?). (* Примечание: сообщение т должно быть распознаваемым (см. раздел 10.4.3). *)
Схема цифровой подписи Рабина имеет ряд преимуществ по сравнению со схемой RSA. Во-первых, доказано, что подделка подписи так же сложна, как и разложение целого числа на простые множители (формальное доказательство этого факта будет приведено позднее). Во-вторых, верификация в схеме Рабина выполняется быстрее и вполне пригодна для приложений, в которых верификация
362 Часть III. Основные методы криптографии1
подписей выполняется небольшими вычислительными устройствами, например, портативными.
Обратите внимание на то, что согласно замечанию 10.1, если сообщение т не является распознаваемым, то фальсификация цифровой подписи Рабина становится тривиальной. Эта подделка является экзистенциальной. Для ее предотвращения необходимо хэшировать сообщение, как показано в разделе 10.4.3, так, чтобы сообщение стало распознаваемым.
10.4.5 Парадоксальная стойкость цифровой подписи Рабина
Используя идею, заложенную в теореме 8.2 (раздел 8.11), можно показать, что если существует алгоритм фальсификации цифровой подписи Рабина, то его можно использовать для факторизации составных модулей, использованных в схеме. Это хорошее свойство, поскольку оно позволяет свести задачу о фальсификации цифровой подписи к общеизвестной трудноразрешимой задаче (разложению целого числа на простые множители).
Однако это свойство сильной стойкости также означает, что схема цифровой подписи Рабина является фатально нестойкой к адаптивным атакам, в ходе которых атакующий может обращаться к автору с просьбой подписать специально подобранные сообщения. Например, атакующий может сгенерировать произвольное число s ? и представить сообщение т = s2(mod N) на подпись Алисе. Ответ Алисы, например, сообщение s', представляет собой один из четырех квадратных корней числа т. Если s' ± s(mod N), то в ходе адаптивной атаки Злоумышленник может разложить ее модуль на множители.
Следовательно, цифровая схема Рабина, описанная алгоритмом 10.2, абсолютно неприменима в реальных приложениях, в которых невозможно избежать адаптивных атак. Схема цифровой подписи Рабина в реальных приложениях не должна позволять атакующему получать два разных квадратных корня одного сообщения.
Более практичной является цифровая схема Рабина с использованием функции хэширования, описанная в главе 16. Этот алгоритм является вероятностным. Он гарантирует, что многочисленные образцы подписи одного и того же сообщения будут рандомизированы, так что атакующий не сможет вычислить два разных квадратных корня одного сообщения. Следовательно, такую схему цифровой подписи можно применять в реальных приложениях. Формальное доказательство стойкости схемы цифровой подписи Рабина в рамках строгого подхода будет приведено в главе 16.
Подведем парадоксальные итоги, касающиеся стойкости схемы цифровой подписи Рабина.
Глава 10. Методы защиты целостности данных
363
С одной стороны, используя идею теоремы 8.2 (из раздела 8.11), мы показали, что цифровую подпись Рабина в учебном варианте невозможно подделать, так как эта задача по сложности эквивалентна разложению целого числа на простые множители. Данный результат является не только очень сильным (поскольку имеет формальное доказательство), но и крайне желательным, так как сводит фальсификацию цифровой подписи к трудноразрешимой задаче: факторизации целого числа.
С другой стороны, учебный вариант цифровой подписи Рабина безнадежно слаб и абсолютно непригоден для реальных приложений, которые регулярно подвергаются адаптивным атакам. Такие атаки полностью разрушают учебную схему цифровой подписи Рабина. Следовательно, необходимо разработать прикладную схему цифровой подписи Рабина (см. главу 16). К сожалению, как мы убедимся, формальное доказательство стойкости не связано с задачей разложения целого числа на простые множители.
10.4.6 Цифровая подпись Эль-Гамаля
Кроме элегантной криптосистемы с открытым ключом, описанной в разделе 8.12, Эль-Гамаль разработал оригинальную схему цифровой подписи. Как и криптосистема, схема цифровой подписи Эль-Гамаля дала толчок многочисленным исследованиям и породила целое семейство схем цифровой подписи (некоторые из них будут рассмотрены в разделе 10.4.8 и главе 16).
Схема цифровой подписи Эль-Гамаля представлена в алгоритме 10.3.
10.4.7 Неформальное обоснование стойкости схемы цифровой подписи Эль-Гамаля
Оценим стойкость схемы цифровой подписи Эль-Гамаля.
10.4.7.1 Предостережения
Следует сделать несколько предостережений, касающихся схемы цифровой подписи Эль-Гамаля.
Предостережение 1
Во-первых, при верификации цифровой подписи необходимо проверить неравенство г < р. Если г > р, возможна атака, изобретенная Блайхенбахером (В1е-ichenbacher) [41]. Пусть (r,s) — подпись сообщения т. Злоумышленник может подделать новую подпись произвольного сообщения т! следующим образом.
