Схема цифровой подписи Эль-Гамаля

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 07:47, 26 мая 2016.

Принцип работы схемы

Данная схема стала наиболее известной схемой ЦП, из которой вышли некоторые стандарты ЦП. Состав:

  • Алгоритм выработки параметров
  • Алгоритм подписи
  • Алгоритм проверки подписи

Параметры: - большое простое число, - нумератор, - документ (на самом деле - хеш от большого текста, поэтому это не является ограничением), - секретный долговременный ключ ЦП - открытый ключ проверки ЦП.

подписывает документ:

  1. - разовый секретный ключ ЦП, при этом нужно, чтобы (для существования )
  2. вычислим
  3. вычислим
2 операция - самая трудоемкая, - трудоемкость вычисления ЦП. 2,3 операции - ЦП: , порядка .
-проверяющий.

проверяет подлинность:

Дано:
Проверка:
Доказательство корректности:

Атаки на алгоритм цифровой подписи Эль Гамаля

Атака на плохо выбранные разовые ключи

При рассмотрении стойкости необходимо соотношение . Тот, кто наблюдает за подписывающим, видит серию подписанных документов:

Неизвестными являются . Получили систему уравнений от неизвестных, т.е. неопределенная система уравнений. Если знаем хоть один разовый ключ, то система становится определенной и решается - значит, все ключи должны быть случайными, секретными и разными.

Была схема, где . Но если противнику известен закон распределения, то количество неизвестных сокращается и появляется возможность атаки. Поэтому не должно быть.

Атака Bleichenbucker'а

Предложена на EC'96, атака на плохую реализацию алгоритма ЦП.

Дело в том, что при проверке нужно еще проверять, чтобы . Представим, что в схеме реализации это не учтено.

Пусть - некая ЦП по Эль Гамалю, - подписываемый текст. Цель атакующего: имея корректно подписанный документ, построить корректную ЦП под нужным ему документом.

, где - значение, которое хотят подписать, - значение хеш-функции для известного текста.

Тогда

Нужно, чтобы - если найдем такие значения , то построим корректную подпись для произвольного документа.

Эта система уравнений решается с помощью КТО, трудоемкость решения - полиномиальна.

Атака "по корректной тройке"

Так же связана с построением ЦП по известной корректной тройке

Если взять параметры такими, что , то можно построить целую серию документов, удовлетворяющих соотношению проверки.

Покажем это:

Создав таким образом множество документов, можно организовать DDOS-атаку на проверяющего. Защита: - случайное значение, - значит, ЦП для Гамаля должна применяться совместно с хеш-функцией.

Замечание: еще пара слов про атаку Bleichenbucker'а. Мы строим - ложную подпись по шагам этих соотношений, порядка . Эту лазейку можно применить, регламентировав размер , но это не всегда делается.

Атака на слабый генератор

TemplateTheoremIcon.svg Теорема Теорема
Пусть и является -гладким; если существует и целое известное , тогда существует (можно найти) корректную подпись к желаемому значению без знания секретных ключей.
Доказательство
Покажем, что может быть решено относительно

Найти - задача дискретного логарифмирования. На подгруппы , порожденные генератором, имеет порядок . Тогда методом Полига-Хеллмана находим . Тогда - корректная подпись. Проверим это:

Итого, получим соотношение


TemplateTheoremIcon.svg Теорема Следствие
Если -гладкая и - можно сгенерировать корректную подпись к тексту
Доказательство
Пусть , тогда


Следствие (из следствия): - особенно плохой генератор, т.к. - всегда.

Теорема Чебышева - случай, когда является генератором - это просто, поэтому брать генератором просто.

Модификации схемы ЦП Эль Гамаля

FIPS PUB 186

ГОСТ Р 34.10-94

или

ЦП Шнорра (Shnorr)

Алгоритм впервые предложен на конференции CR'90. Первоначально в качестве параметров алгоритма выступали и .

Входные данные:

- хеш-функция
- генератор

Алгоритм подписи

  1. - долговременный ключ
  2. - долговременный открытый ключ проверки ЦП
  3. - разовый секретный ключ
  4. ЦП

Проверка

ЦП Harn'а

Входные данные

Алгоритм подписи

Проверка

Примечание

Статья на Википедии

Литература

  • Введение в теоретико-числовые методы криптографии: учебное пособие /М.М. Глухов, И.А. Круглов, А.Б. Пичкур, А.В. Черемушкин. – Москва: Изд-во Лань, 2011. - 400с. -ISBN 978-5-8114-1116-0