Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 142

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 136 137 138 139 140 141 < 142 > 143 144 145 146 147 148 .. 311 >> Следующая

10.4.7.2 Предотвращение экзистенциальной подделки
Экзистенциальную подделку, описанную в замечании 10.1, можно применить и к схеме цифровой подписи Эль-Гамаля, если сообщение не содержит необ-| ходимой распознаваемой избыточности. Иначе говоря, нетрудно подделать пару "сообщение-подпись", созданную по схеме Эль-Гамаля, где сообщение не является распознаваемым.
Например, пусть ukv — любые целые числа, которые меньше р — 1 и удовлетворяют условию gcd(?j, р — 1) = 1. Выполним следующие операции.
г «- 9иУА (modP).
s *--ru_1(modp — 1),
m <--rm>_1(modp — 1).
Глава 10. Методы защиты целостности данных
367
Пара (m, (г, s)) представляет собой законную подпись, созданную по схеме Эль-Гамаля с помощью открытого ключа Алисы ул.
= Уа9-™~1Уаг=
— g—mV-1-—
= gm(modp).
Однако, поскольку возведение в степень по модулю обладает свойством перемешивания, подделанное сообщение т не распознается.
Механизм форматирования сообщения предотвращает фальсификацию. В простейшем случае достаточно, чтобы сообщение т одержало распознаваемую часть, т.е. представляло собой конкатенацию т = М \\ I, где М — подписываемое сообщение, а I — распознаваемая строка, например, имя автора.
Наиболее часто для форматирования сообщений применяется хэширование. В качестве примера рассмотрим сообщение
т = Н(М,г),
где Н — криптографическая функция хэширования, а М — битовая строка, представляющая сообщение. Теперь подписью является само сообщение М. Этап верификации включает в себя верификацию сообщения т = Н(М,г). Поскольку функции хэширования являются однонаправленными, экзистенциальная атака становится невозможной.
Если предположить, что функция хэширования Н является случайным оракулом (см. раздел 10.3.1.2), то доказательство стойкости схемы цифровой подписи Эль-Гамаля сводится к доказательству эквивалентности между задачей дискретного логарифмирования (которая, как известно, является трудноразрешимой) и фальсификацией подписи. Формальное доказательство этого факта будет приведено в главе 16. В этой же главе содержатся формальные доказательства других схем цифровой подписи, принадлежащих семейству Эль-Гамаля.
10.4.8 Семейство схем цифровой подписи Эль-Гамаля
После опубликования оригинальной работы Эль-Гамаля появилось несколько вариаций на эту тему. Наиболее значительными из них являются схема цифровой подписи Шнорра (Schnorr) [256, 257] и стандарт цифровой подписи DSS (Digital Signature Standard) [215, 216].
368
Часть III. Основные методы криптографии
10.4.8.1 Схема цифровой подписи Шнорра
Схема цифровой подписи Шнорра является вариантом схемы цифровой подписи Эль-Гамаля. Однако она обладает свойством, делающим ее весьма ценной для криптографии с открытым ключом: поле простых элементов в этой схеме представлено намного компактнее, чем в схеме Эль-Гамаля, однако это не приводит к уменьшению сложности решения задачи, лежащей в ее основе (например, задачи дискретного логарифмирования). Впоследствии эту идею применили к конечным полям более общего вида, что привело к появлению новой криптосистемы с открытым ключом: XTR [175].
Более компактное представление достигается с помощью конструирования поля Fp, содержащего намного меньшую подгруппу простого порядка q. Заметим, что в настоящее время в криптосистемах семейства Эль-Гамаля выбирается параметр р га 21024. Кроме того, с появлением более мощных средств, позволяющих решать задачу дискретного логарифмирования, размер числа р должен увеличиваться. Однако после появления работы Шнорра стало общепринятой практикой устанавливать параметр q равным приблизительно 2160. Вполне возможно, что эта величина не зависит от роста числа р, поскольку информация о подгруппе не играет значительной роли при вычислении дискретного логарифма в поле Fp, даже если известно, что искомый элемент принадлежит данной подгруппе. Величина
2160
диктуется исключительно требованием стойкости к атаке по методу! квадратного корня (см. раздел 3.6).
Схема цифровой подписи Шнорра описывается алгоритмом 10.4.
Отметим, что при вычислении открытых параметров порождающий элемент д< может определяться быстро, поскольку q || р — 1.
Prob [gcd(ord(/),<7) = 1 I / е uZp] < 1/q,
p-i
т.е. вероятность найти случайное число /, удовлетворяющее условию д <— / « = = l(modp), пренебрежимо мала. Из малой теоремы Ферма (теорема 6.10 из раздела 6.4) следует, что
дч = l(modp).
Таким образом, элемент д действительно порождает подгруппу, состоящую из q элементов.
Верификация подписи работает правильно, если пара (тп, (s, е)) представляет собой правильную пару "сообщение-подпись", созданную Алисой. Тогда
г' = gsye = дхе+еуе = У~е9?уе = 9* = r(modp).
Как указывалось ранее, применение подгруппы порядка q группы Fp позволяет сделать цифровую подпись в схеме Шнорра намного короче, чем подпись в схеме Эль-Гамаля: для передачи подписи Шнорра достаточно 2\q\ бит, в то
Глава 10. Методы защиты целостности данных
369
Алгоритм 10.4. Схема цифровой подписи Шнорра Установка системных параметров
1. Выбрать два простых числа р, удовлетворяющих условию q \ р — 1.
Предыдущая << 1 .. 136 137 138 139 140 141 < 142 > 143 144 145 146 147 148 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed