Схемы открытого шифрования Эль Гамаля

С точки зрения криптографии ведутся поиски более эффективных систем открытого шифрования. В 1985 году Т.ЭльГамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P.

Задается большое простое число P и целое число A, 1<A<P . Сообщения представляются целыми числами M из интервала 1<M<P. Протокол передачи сообщения M выглядит следующим образом:

Абоненты	I	J
Знают	A, P
генерируют случайные числа	K; 1<K<P	X; 1<X<P
вычисляют
получатель передает по каналу связи		-------------------------B
отправитель шифрует и передает сообщение	, -------------->
получатель расшифровывает сообщение		,

В этой системе ОШ та же степень защиты, что для алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако в таком варианте открытого шифрования нет подтверждения подлинности сообщений (Видимо по тому (т.е. это моё мнение О.Ф.), что передача сообщения происходит в виде диалога, а подпись это так скажем односторонний процесс, типа подписал, а потом кому надо будет, проверят).

Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения подлинности отправителя Т.ЭльГамаль предложил следующий протокол передачи подписанного сообщения M.

Абоненты	отправитель I	получатель J
знают	A, P
генерирует и хранит в секрете	X: 1<X<P
вычисляет и передает	----------->
для сообщения	M: 1<M<P
формирует подпись
а) выбирает	K случайное: 1<K<P: (K, P-1)=1
б) вычисляет
в) решает относительно S
Пеpедает подписанное сообщение	[M, R, S] ------------>
Получатель проверяет правильность подписи

В этой системе секретным ключом для подписывания сообщений является число X, а открытым ключом для проверки достоверности подписи число B. Пpоцедуpа проверки подписи служит также и для проверки правильности pасшифpования, если сообщения шифруются.

Схемы подмиси .Эль-Гамаля, DSA и Schnorr – примеры общей схемы цифровой подписи, использующей проблемму дискретных логорифмов (модификаций несколько тысяч).

Схемы цифровой подписи с использованием дискретных логарифмов

Схемы подписи ElGamal, Schnorr (см. раздел 21.3) и DSA очень похожи. По сути, все они являются тремя примерами общей схемы цифровой подписи, использующей проблему дискретных логарифмов. Вместе с тысячами других схем подписей они являются частью одного и того же семейства.

Выберем p, большое простое число, и q, равное либо p-1, либо большому простому множителю p-1. Затем выберем g, число между 1 и p, для которого g^q  1 (mod p). Все эти числа открыты, и могут быть совместно использованы группой пользователей. Закрытым ключом является x, меньшее q. Открытым ключом служит y =g^x mod q.

Чтобы подписать сообщение m, сначала выберем случайное значение k, меньшее q и взаимно простое с ним. Если q тоже простое число, то будет работать любое k, меньшее q. Сначала вычислим

r = g^k mod p

Обобщенное уравнение подписи примет вид

ak = b + cx mod q

Коэффициенты a, b и c могут принимать различные значения. Каждая строка предоставляет шесть возможностей. Проверяя подпись, получатель должен убедиться, что

r^a = g^by^c mod p

Это уравнение называется уравнением проверки.

Возможные перестановки a, b и c (r'= r mod q)

 r'	 s	M
 r' m	 s	1
 r' m	 ms	1
 m r'	 r' s	1
 ms	 r' s	1

Перечислены возможные варианты подписи и проверки, полученные только из первой строки возможных значений a, b и c без учета эффектов ±.