Электронно-цифровая подпись

Практический  алгоритм реализации цифровой подписи

Алгоритм Эль Гамаля

Это криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1984 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

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

Алгоритм:

1) Генерация ключей

• Генерируется  случайное простое число p  длины n  битов.
• Выбирается случайный примитивный элемент g поля Z .
• Выбирается случайное целое число x такое, что 1<x<p-1.
• Вычисляется y=g^x mod p.
• Открытым ключом является тройка (p,g,y), закрытым ключом — число x.

2) Подпись сообщения

• Вычисляется дайджест сообщения m=h(M)
• Выбирается случайное число 1<k<p-1 взаимно простое с p-1 и вычисляется r=g^k mod p
• Вычисляется число s=(m-rx)k^(-1) mod(p-1).
• Подписью сообщения  является пара (r,s).

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

Зная открытый ключ (p,g,y),  подпись (r,s) сообщения M проверяется следующим образом:

• Проверяется выполнимость условий:  0<r<p и 0<s<p-1 . Если хотя бы одно из них не выполняется, то подпись считается неверной.
• Вычисляется дайджест m=h(M)
• Подпись считается верной, если верно: (y^r)(r^s) mod p=g^m mod p

 

 

Алгоритм Шнорре

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

Алгоритм:

1) Параметры системы

• Выбирается простое p и простое q, такое, что (q|p-1 )
• Выбирается элемент β, такой, что B^q mod p=1
• Параметры (p,q,β) свободно публикуются
• Выбирается параметр t>=40, 2^t<q

2)  Выбор параметров доказывающей стороны

Пусть каждая доказывающая сторона A выбирает секрет a (закрытый ключ), такой, что 1<=a<=q-1 и вычисляет v=B^a mod p , где v-открытый ключ

3)  Создание и проверка правильности подписи

Пусть сторона A хочет отправить сообщение М стороне B; причем B должен убедиться в том, что сообщение пришло именно от A. Тогда:

• A выбирает случайное r (1<=r<=q-1), вычисляет x=B^r mod p
• Пусть имеется однонаправленная хеш-функция h(M). Сторона А объединяет M с x и хеширует результат e=h(M,x)
• Далее A вычисляет y=(ae+r) mod q. Значения e и y являются цифровой подписью и отсылаются B.
• B вычисляет z=(B^y)(v^e)mod p. Затем z и полученное сообщение M' пропускаются через хеш-функцию: e’=h(M’,z). Если e=e’, то подпись считается верной.

 

Список  литературы

1) http://cyberfotum.ru электронный портал об алгоритмизации

2) http://protect.htmlweb.ru/ электронный портал о криптографии

3) http://crypto-r.narod.ru электронный портал о криптографии

4)http://habrahabr.ru электронный журнал

5)http://Wikipedia.ru электронная библиотека

6) http://crypto-blog.ru/ блог о криптографических системах

7) http://www.mathforum.ru/ математический форум

8) http://www.des-crypto.ru электронный портал о криптографии

9) http://www.askdev.ru сайт об алгоритмизации

10)http://www.rsdn.ru  электронный портал

11) Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В Основы  криптографии.

12) Шнайер Б. Прикладная криптография. Протоколы и алгоритмы.