Протоколы электронной подписи

Схема электронной подписи RSA

 

Криптосистема с открытым ключом RSA часто используется не только для шифрования, но и для построения схемы электронной подписи.

Пусть ЕA (х) = хе mod п - открытая функция зашифрования,

a DA (x) = xd mod n - секретная функция расшифрования.

 

Схема электронной подписи RSA

 

1. Абонент А (претендент) вычисляет хеш-образ h(M) сообщения М.

2. Абонент А зашифровывает полученное значение h(M) на своем секретном ключе d, вычисляя подпись

s=(h(M))d mod n

и отправляет абоненту В пару документ-подпись (М, s).

3. Абонент В (верификатор) расшифровывает s на открытом ключе е отправителя, т.е. вычисляет

se mod n.

4. Абонент В вычисляет хеш-образ h(M) полученного сообщения и проверяет равенство

h(M) = se mod n.

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

В качестве хеш-функции в схеме подписи RSA используются функции семейства MD.

Рис. 7. ЭЦП RSA

Схема электронной подписи Эль Гамаль

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

 

В схеме Эль Гамаль абонент, подпи­сывающий документ, доказывает всем желающим проверить подпись, что знает секретный ключ х — степень, в которую был возведен образующий элемент а, чтобы получить открытый ключ b. Явным образом продемонстри­ровать х, естественно, нельзя, иначе любой другой участник информационно­го обмена начнет подписывать им документы. Поэтому приходится идти на математические уловки — демонстрировать не само число х, а результат не­коей математической формулы с участием х. При проверке само число х ни на каком этапе не раскрывается, но проверяющий на основе этой формулы удостоверяется, что отправитель сообщения действительно знает х.

Базовый вариант ЭЦП по схеме Эль Гамаль выглядит следующим образом. Обозначения для открытого и закрытого ключей, простого числа и обра­зующего элемента такие же, как и в асимметричном шифровании по схеме Эль Гамаль.

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

1. Генерирует случайное число k, уникальное для каждого подписываемого документа, взаимно простое с числом (р — 1).

2. Вычисляет r = (аk mod р).

3. Вычисляет обратный элемент поля к числу k — его обозначают (k-1 mod (р — 1)) или 1/k, в дальнейшем операция "деление на k" равно­значна умножению на 1/k.

4. Вычисляет s = ((h — х × r) / k) mod (р — 1), где h — контрольная сумма подписываемого документа.

Пара чисел (r, s) является цифровой подписью для документа, имеющего контрольную сумму h.

 

На приемной стороне получатель:

1. Вычисляет и = ((b r ×(rs) mod р).

2. Вычисляет v = (ah mod р).

3. Проверяет равенство значений u = v (если равенство выполняется, то подпись верна, в противном случае документ сфальсифицирован).

 

Почему данное равенство является тождеством в случае корректности ЭЦП? Произведем несложные преобразования над u (подразумеваем, что все дей­ствия выполняются по модулю числа р):

Как видим, во-первых, получилось тождество, а во-вторых, ни на одном этапе преобразований (а все они доступны проверяющему) число х не фи­гурировало в открытом виде — его как бы "экранируют" две величины r и k, причем вторая не известна получателю. Схема ЭЦП Эль Гамаль приведена на рис. 8.

Рис. 8. ЭЦП Эль Гамаль

Классификация атак на схемы электронной подписи

 

Стойкость схемы электронной подписи зависит от стойкости используемых криптоалгоритмов и хеш-функций и определяется относительно пары угроза-атака. Приведем классификацию атак на схемы электронной подписи:

· атака на основе известного открытого ключа (key-only attack) - самая слабая из атак, практически всегда доступная противнику;

· атака на основе известных подписанных сообщений (known-message attack) - в распоряжении противника имеется некоторое (полиномиальное от k) число пар (M, s), где М - некоторое сообщение, a s - допустимая подпись для него, при этом противник не может влиять на выбор М;

· простая атака с выбором подписанных сообщений (generic chosen-message attack) - противник имеет возможность выбрать некоторое количество подписанных сообщений, при этом открытый ключ он получает после этого выбора;

· направленная атака с выбором сообщений (directed chosen-message attack) - выбирая подписанные сообщения, противник знает открытый ключ;

· адаптивная атака с выбором сообщений (adaptive chosen-message attack) - противник знает открытый ключ, выбор каждого следующего подписанного сообщения он может делать на основе знания допустимой подписи предыдущего выбранного сообщения.

 

Каждая атака направлена на достижение определенной цели. Можно выделить следующие виды угроз для схем электронной подписи (в порядке возрастания силы):

· экзистенциальная подделка (existential forgery) - создание противником подписи для какого-нибудь, возможно бессмысленного, сообщения М¢, отличного от перехваченного;

· селективная подделка (selective forgery) — создание подписи для заранее выбранного сообщения;

· универсальная подделка (universal forgery) - нахождение эффективного алгоритма формирования подписи, функционально эквивалентного S;

· полное раскрытие (total break) - вычисление секретного ключа, возможно отличного от k(sectert), соответствующего открытому ключучто дает возможность формировать подписи для любых сообщений.

 

Наиболее стойкими являются схемы, стойкие против самой слабой из угроз на основе самой сильной из атак, т.е. против экзистенциальной подделки на основе атаки с выбором подписанных сообщений. Справедливо следующее утверждение. Схемы электронной подписи, стойкие против экзистенциальной подделки на основе атаки с выбором подписанных сообщений, существуют тогда и только тогда, когда существуют односторонние функции.