top of page
                                    Лабораторная работа №10
Тема: Изучение алгоритма электронной цифровой подписи Эль-Гамаля
Цель Работы: Ознакомиться со схемами цифровой подписи и получить навыки создания  и проверки подлинности ЦП.

ПРИМЕР (алгоритм Эль-Гамаля)

1)Пусть общие параметры для некоторого сообщества пользователей p=23 и g=5.

Пусть секретный ключ x=7. Вычислим открытый ключ y:

2)

​

Пусть нужно поставить подпись на сообщение m=baaqab

Перейдем к вычислению подписи по алгоритму.

3)Прежде всего, вычисляется хеш-функция. Пусть её значение h(m)=h(baaqab)=M=3.

4)Затем генерируется случайное число k, например k=5. Вычисляем по формулам

5)

​

И по расширенному алгоритму Евклида находим b 

6)3=(7*20+5*b) mod 22

Такое b существует, т.к. НОД(k,p-1)=1. Получили b=21.

7)Получили подписанное сообщение в виде <baaqab,20,21>

Подписанное сообщение передается.

 Полученное сообщение проверим на подлинность.

1)Прежде всего, вычисляется хеш-функция h(baaqab)=M=3.

2)Затем вычисляем левую часть

​

​

​

3)и после этого правую

Теоретическая часть:

Для генерации пары ключей сначала выбирается простое число p и два случайных числа g и x. Оба эти числа должны быть меньше p.

Чтобы подписать сообщение М, сначала выбирается случайное число k, взаимно простое с p-1. Затем вычисляется: 

​

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

Подписью является пара чисел: a и b. Случайное значение k должно храниться в секрете. Для проверки подписи нужно убедиться, что:

Так как левая часть совпала с правой, то можно сделать вывод, что подпись верна.

Абоненты некоторой сети применяют подпись Эль-Гамаля с общими параметрами p=23, g=5. Для указанных секретных параметров абонентов найти открытый ключ (y) и построить подпись для сообщения m:

  1. x=11, k=3, m=15

  2. x=10, k=15, m=5

  3. x=3, k=13, m=8

  4. x=18, k=7, m=5

  5. x=9, k=19, m=15

                          Во всех вариантах будем предполагать, что h(m)=m для всех значений m.

                                                                           Контрольные вопросы

  1. Для чего нужна цифровая подпись?

  2. Какая схема самая распространенная? Почему?

  3. Как осуществляется подпись Эль-Гамаля?

  4. Как осуществляется проверка на подлинность подписи Эль-Гамаля?

bottom of page