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

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

1. Проверяется выполнимость условий: и . Если хотя бы одно из них не выполняется, то подпись считается неверной.

2. Вычисляется дайджест

3. Подпись считается верной, если выполняется сравнение:

Пример

- Подпись сообщения.

1. Допустим, что нужно подписать сообщение .

2. Произведем генерацию ключей:

1. Пусть переменные, которые известны некоторому сообществу. Секретный ключ — случайное целое число такое, что .

2. Вычисляем открытый ключ : .

3. Итак, открытым ключом является тройка .

3. Теперь вычисляем хэш-функцию: .

4. Выберем случайное число такое, что выполняется условие 1 < k < p − 1. Пусть .

5. Вычисляем .

6. С помощью расширенного алгоритма Евклида находим число из уравнения . Такое существует, так как НОД(k, p -1)=1. Получим что .

7. Итак, мы подписали сообщение: .

- Проверка подлинности полученного сообщения.

1. Вычисляем хэш-функцию: .

2. Проверяем сравнение .

3. Вычислим левую часть по модулю 23: .

4. Вычислим правую часть по модулю 23: .

5. Так как правая и левая части равны, то это означает что подпись верна.

 

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

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

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

- Использование свертки объясняется тем, что это защищает подпись от перебора сообщений по известным злоумышленнику значению подписи. Пример: если выбрать случайные числа , удовлетворяющие условиям , НОД(j, p-1)=1 и предположить что

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

- Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: , в котором тройка принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при , , .На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (DigitalSignatureStandard), используется значения , , , а в Российском стандарте: , , .

- Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел на пару чисел ), где является каким-то простым делителем числа . При этом сравнение для проверки подписи по модулю нужно заменить на новое сравнение по модулю : . Так сделано в американском стандарте DSS (DigitalSignatureStandard).

В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:

ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.

 

Алгоритм	Ключ	Назначение	Криптостойкость, MIPS	Примечания
RSA	До 4096 бит	Шифрование и подпись	2, 7•1028 для ключа 1300 бит	Основан на трудности задачи факторизации больших чисел; один из первых асимметричных алгоритмов. Включен во многие стандарты
ElGamal	До 4096 бит	Шифрование и подпись	При одинаковой длине ключа криптостойкость равная RSA, т.е. 2, 7•1028 для ключа 1300 бит	Основан на трудной задаче вычисления дискретных логарифмов в конечном поле; позволяет быстро генерировать ключи без снижения стойкости. Используется в алгоритме цифровой подписи DSA-стандарта DSS
DSA	До 1024 бит	Только подписание		Основан на трудности задачи дискретного логарифмирования в конечном поле; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ.
ECDSA	До 4096 бит	Шифрование и подпись	Криптостойкость и скорость работы выше, чем у RSA	Современное направление. Разрабатывается многими ведущими математиками

3. Вопросы к домашним заданиям.

1. Определение криптосистемы с открытым ключем (асимметричной криптосистемы).

2. Обобщенная схема асимметричной криптосистемы с открытым ключом.

3. Характерные особенности асимметричных криптосистем.

4. Требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы.

5. Определение однонаправленной функции.

6. Перечислите шифрсистемы с открытым ключом.

7. На чем основана стойкость шифрсистемыRSA?

8. На чем основана стойкость шифрсистемы Эль гамаля?