2.3. Цифровая подпись в схеме Эль-Гамаль

В отличие от криптосистемы RSA, построенной на сложности задачи факторизации больших чисел, профессор Стэнфордского университета (США) Тахер Эль-Гамаль (Taher ElGamal) разработал в 1985 г. асимметричную криптосистему, основанную на сложности задачи дискретного логарифмирования [9].

Данная криптосистема (названная его именем), так же как и RSA, является универсальной, т.е. может использоваться как для шифрования данных, так и для цифровой подписи сообщений.

Для генерации пары ключей выбирается простое числои два случайных числаи, меньших:

	,	(3.1)
	.	(3.2)

Затем вычисляется значение из выражения

.

(3.3)

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

Для подписания сообщения , сначала выбирается случайное число, такое что

.

(3.4)

Значение в дальнейшем сохраняется в секрете. Затем вычисляется значениеиз выражения

(3.5)

Далее с помощью расширенного метода Евклида для нахождения решается следующее уравнение

.

(3.6)

Подписью является пара чисел . Для проверки подписи необходимо проверить справедливость равенства:

.

(3.7)

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

Известны модификации данного алгоритма для доказательства идентичности, аутентификации и обмена ключами [1].

2.4. Обмен информацией с использованием протокола Шамира

Использование асимметричных криптосистем позволяет успешно решать новые, неизвестные ранее криптографические задачи. Одной из таких задач является задача обмена секретной информацией (например, секретными ключами для дальнейшего использования симметричных криптосистем) по общедоступному каналу связи.

Данная задача может быть решена с использованием т.н. «трехпроходного протокола», разработанного в 1991 г. одним из разработчиков RSA Ади Шамиром [1].

Протокол Шамира позволяет абонентам безопасно обмениваться информацией, не используя предварительного обмена ни секретными, ни открытыми ключами.

Протокол подразумевает использование коммутативного симметричного шифра, для которого выполняется условие

Здесь и- секретные ключи абонентовисоответственно.

Пусть требуется передать сообщение от абонентаабоненту. Тогда абонентиспользует следующий протокол:

Шаг 1. Абонент вычисляет значениепо формуле 4.1 и пересылает его абоненту

(4.1)

Шаг 2. Абонент , получив значение, вычисляет значениеиз выражения 4.2 и посылает его абоненту.

(4.2)

Шаг 3. Абонент , получив значение, вычисляет значениеиз выражения 4.3 и посылает его абоненту.

(4.3)

Шаг 4. Абонент , получив значение, дешифрует его своим ключом, получая:

.

(4.4)

Практическая реализация данного протокола требует выбора алгоритмов симметричной криптосистемы для использования в качестве и.

Широкоизвестный шифр «одноразовые блокноты Вернама» обладает свойством коммутативности и является абсолютно стойким против действий пассивного противника [2,3]. Однако в рамках данной схемы криптосистема «одноразовые блокноты Вернама» не применима в связи с транзитивностью операции XOR (исключающее ИЛИ) [1]. Ади Шамир разработал и описал криптосистему, схожую с RSA, обладающую свойством коммутативности и применимую в рамках данного протокола [1].

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

.

(4.5)

С помощью расширенного метода Евклида вычисляется значение из условия

.

(4.6)

Или, иначе говоря

.

(4.7)

Для шифрования сообщения используется выражение

.

(4.8)

Для дешифрования шифртекста используется выражение

.

(4.9)

Стойкость данной криптосистемы основывается на сложности задачи дискретного логарифмирования.

Помимо описанной криптосистемы в данном протоколе могут быть использованы другие симметричные криптосистемы, например криптосистема Вильямса [1].