Схема Эль-Гамаля - Работа в режиме подписи

Интернет магазин китайских планшетных компьютеров

Компьютеры - Схема Эль-Гамаля - Работа в режиме подписи

22 января 2011

Оглавление:
1. Схема Эль-Гамаля
2. Работа в режиме шифрования
3. Работа в режиме подписи
4. Криптостойкость и особенности

Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции $~h$ , значения которой лежат в интервале $\left$ .

Подпись сообщений

Для подписи сообщения $~M$ выполняются следующие операции:

Вычисляется дайджест сообщения $~M$ : $~m = h.$
Выбирается случайное число $~1< k < p-1$ взаимно простое с $~p - 1$ и вычисляется $~r = g^k\,\bmod\,p.$
С помощью расширенного алгоритма Евклида вычисляется число $~s$ , удовлетворяющее сравнению:

$~m \equiv xr + ks\pmod{p-1}.$
Подписью сообщения $~M$ является пара $\left$ .

Проверка подписи

Зная открытый ключ $\left$ , подпись $\left$ сообщения $~M$ проверяется следующим образом:

Проверяется выполнимость условий: $~0<r<p$ и $~0<s<p-1$ . Если хотя бы одно из них не выполняется,то подпись считается неверной.
Вычисляется дайджест $~m = h.$
Подпись считается верной, если выполняется сравнение:

$~y^r r^s \equiv g^m \pmod{p}.$

Пример

Подпись сообщения.
1. Допустим,что нужно подписать сообщение $~M=baaqab$ .
2. Произведем генерацию ключей:
  1. Пусть $~p=23$ $~g=5$ переменные, которые известны некоторому сообществу. Секретный ключ $~x=7$ — случайное целое число $~x$ такое, что $~1 < x < p$ .
  2. Вычисляем открытый ключ $~y$ : $~y=g^x\bmod p=5^7 \bmod 23=17$ .
  3. Итак,открытым ключом является тройка $~=$ .
3. Теперь вычисляем хэш-функцию: $~h=h=m=3$ .
4. Выберем случайное число $~k$ такое, что выполняется условие 1 < k < p − 1. Пусть $~k=5$ .
5. Вычисляем $~r=g^k modp=5^5 \bmod 23=20$ .
6. С помощью расширенного алгоритма Евклида находим число $~s$ из уравнения $~3= \bmod 22$ . Такое $~s$ существует, так как НОД=1. Получим что $~s=21$ .
7. Итак, мы подписали сообщение: $~<baaqab,20,21>$ .

Проверка подлинности полученного сообщения.
1. Вычисляем хэш-функцию: $~h=h=m=3$ .
2. Проверяем сравнение $~y^r \cdot r^s\equiv g^m \pmod{p}$ .
3. Вычислим левую часть по модулю 23: $~17^{20} \cdot 20^{21} \bmod 23=16 \cdot 15 \bmod 23=10$ .
4. Вычислим правую часть по модулю 23: $~5^3\bmod 23=10$ .
5. Так как правая и левая части равны, то это означает что подпись верна.

Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле $\mathbb{Z}_p$ . Следует сделать несколько комментариев:

Случайное число $~k$ должно сразу после вычисления подписи уничтожаться,так как если злоумышленник знает случайное число $~k$ и саму подпись, то он легко может найти секретный ключ по формуле: $~x=r^{-1} \bmod$ и полностью подделать подпись.

Число $~k$ должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.

Использование свертки $~m=h$ объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значению подписи. Пример: если выбрать случайные числа $~i,j$ ,удовлетворяющие условиям $~0<i<{p-1} , 0<j<{p-1}$ , НОД=1 и предположить что

$~r=g^i \cdot y^j \bmod p$

$~s=r \cdot j^{-1} \bmod$

$~m=r \cdot i \cdot j^{-1} \bmod$

то легко удостовериться в том,что пара $~$ является верной цифровой подписью для сообщения $~x=M$ .

Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: $~y^A \cdot r^B=g^C$ , в котором тройка $~$ принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при $~A=r$ , $~B=s$ , $~C=m$ .На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS, используется значения $~A=r$ , $~B=-s$ , $~C=m$ , а в Российском стандарте: $~A=-x$ , $~B=-m$ , $~C=s$ .
Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел $~$ на пару чисел $~,где <img class=$ является каким-то простым делителем числа $~$ . При этом сравнение для проверки подписи по модулю $~p$ нужно заменить на новое сравнение по модулю $~q$ : $~ = g^C \pmod{q}$ . Так сделано в американском стандарте DSS.