Лабораторная работа № 3.2

Изучение системы цифровой подписи Эль-Гамаля

 

Задание

Выполнить вычисление ипроверку электронной подписи сообщения по алгоритму ЭльГамаля.

Учебный алгоритм хэширования

1.     Выбирается число h0– вектор инициализации. Число h0может быть выбрано случайно или получено неслучайным образом, например, какдлина сообщения в символах.

2.     Для каждого символа сообщения вычисляется значение

 

h₀=(M_i+h_i-1)² mod(p-1), i=1,…n, n=|M|.

3.     Вычисленное для последнего символа значение hn, увеличенное на единицу,является хэш-значением сообщения: h(M)=h_n+1.

Следуетотметить, что вычисленное по этому алгоритму хэш-значение зависит от всехсимволов сообщения M.

Технология выполнения задания

Задание 1.Для сообщения M (в числовом представлении) сгенерировать электронную подпись поалгоритму Эль-Гамаля при заданных значениях общих параметров p=83 и g=15.Хэш-значение сообщения вычисляется с помощью учебного алгоритма, начальноезначение h0принимается равным числу десятичных разрядов в числовом представлении M. 1. Выбрать параметры x и k системыцифровой подписи и подписываемый текст M из таблицы 1 в соответствии с номеромварианта (от 1 до 5). Сформировать цифровую подпись для сообщения M по аналогиис рассмотренным далее примером

Таблица 1

Варианты задания

Номер варианта	x	k	M
1	15	21	521 182
2	42	47	2825
3	81	17	74121
4	7	25	107234
5	70	33	9263

 

Пример

Абонент используетобщие параметры системы Эль-Гамаля p=83, g=15 и личный ключ x=30, для подписисообщения M=93551 им выбрано случайное число k=55, НОД(55;82)=1.

2.     Занести на лист MS Excel заданные параметры системы Эль-Гамаля всообщение с соответствующими надписями.

3.     Вычислить хэш-значение H(M) по итерационной формуле h₀= n, h₁=(M_i+h_i-1)² mod(p-1), i=1,…,n, h(M)=h_n+1, где n – число десятичных знаков вчисловом представлении сообщения M; M_i – i-й знак числа M:

 Вычисления можно производить втабличном процессоре MS Excel. Получение h0 производится текстовой функцией ДЛСТР, i-госимвола сообщения M – текстовой функцией ПСТР, вычисление hi – функцией ОСТАТ

Длярассматриваемого примера получены следующие значения h0=5, h1=32, h₂=77, h₃=0,h₄=25, h₅=20, H(M)=21.

4.     Вычислить число r по формуле r=g^k mod p.Для вычислений можно использовать реализацию быстрого алгоритма возведения встепень по модулю в табличном процессоре MS Excel аналогично п.4 лабораторнойработы 3.1

Рисунок 1. Вычисление хэш-функции по учебномуалгоритму

 

•      впервую ячейку следующего столбца занести ссылку на значение g (=B2), вовторую ячейку – формулу для умножения по модулю p предыдущего значения на g.Например, если ряд значений формируется в столбце I, то формула примет вид =ОСТАТ(I1*$B$2;$A$2),ссылки на ячейки со значениями g и p должны быть абсолютными;

•      выделитьячейку с формулой и растянуть вниз (скопировать ее) на диапазон ячеек столбцадо строки с номером k включительно (в примере до строки с номером 55).Результат вычисления находится в последней заполненной ячейке столбца. Длярассматриваемого примера получили r=71.

5.      Вычислитьчисло u по формуле u = (h-xr) mod (p-1), для вычислений всреде табличного процессора MS Excel используется функция ОСТАТ(=ОСТАТ(B11C2*G2;A2-1)). В рассматриваемом примере u=23.

6.     Рассчитать значение k^-1 по модулю p-1 с помощьюрасширенного алгоритма Евклида

Рисунок 2. Реализация расширенного алгоритма Евклида

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

 

Для рассматриваемого примераполучено значение k^-1 = 3.

7.     Вычислить число s по формуле s=k^-1u mod (p-1).Для вычисления можно воспользоваться функцией ОСТАТ (=ОСТАТ(A14*J2;A2-1)). Впримере получено s = 69. Цифровая подпись сообщения M = 93551 является парачисел (r,s) т.е (71, 69)

 

Задание 2. Проверитьправильность вычисления сгенерированной цифровой подписи.

8.      Проверкаправильности вычисления полученной цифровой подписи производится с помощьюоткрытого ключа абонента. Сформировать открытый ключ y абонента по формуле y=g^xmod p.

 Для вычисления значения y всреде MS Excel может быть использован итерационный алгоритм, описанный в п.4задание 1. Можно применить вычисления сделанные ранее при расчете значения r(если x>k, следует скопировать формулу в столбце расчетов для нужнойстроки), результат вычисления y находится в строке с номером х(для рассматриваемого примера-в 30-й строке). Для рассматриваемого примераполучено y=30.

9.     Аналогично п.4 задания 1 вычислить значения y^r mod pи r^s mod p, а затем их произведение по модулю p.В примере получено: y^r mod p = 78, r^s mod p=18,y^rr^s mod p=20

10.  Аналогичноп.8 получить значение g^h mod p (можно воспользоваться столбцом сранее сделанными вычислениями r, взяв значение из строки h), значение h=H(M)получено в п.3 задания 1 (в примере H(M)=21). Получено g^h mod p=20.

11.  Проверитьвыполнение равенства y^rr^s mod p=g^h modp. Если равенство верное – подпись подлинная, т.е она была вычислена правильно.В примере получено 20 = 20, равенство выполнено, значит, подпись сгенерированаправильно.

Задание 3. Используетсякриптосистема Эль-Гамаля с теми же параметрами, что и в предыдущих заданиях. Отабонента с открытым ключом y получено сообщение M (в числовомпредставлении), снабженное цифровой подписью (r, s). Проверитьподлинность цифровой подписи. Хэш-значение сообщение вычисляется с помощьюучебного алгоритма, начальное значение h0 принимается равным числу десятичных разрядов вчисловом представлении M.

12.  Выбратьоткрытый ключ отправителя y, сообщение M и значения цифровой подписи (r,s) из таблицы 2 в соответствии с номером варианта (от 1 до 5). Проверитьподлинность цифровой подписи для полученного сообщения M по аналогии срассмотренным ниже примером

Таблица 2

Номер варианта	Открытый ключ отправителя y	Сообщение M	Цифровая подпись
			r	s
1	76	6752	45	4
2	45	11926	51	12
3	69	7298	50	11
4	41	63211	32	43
5	16	776503	46	41

 

Пример

y=rs=15

13.  Вычислитьзначение y^r mod p и r^s mod p, а затем ихпроизведение по модулю p. Для вычисления значений степени по модулю всреде MS Excel может быть использован итерационный алгоритм, описанный в п.4задания 1. Для рассматриваемого примера получено: y^r mod p=51,r^s mod p=67, y^r r^s mod p=14.

14.  Дляполученного сообщения M вычислить хэш-значение h(M) аналогично п.3

задания1. Результаты вычислений для примера приведены

Рисунок 5. Пример вычисления хэш-значения поучебному алгоритму

 

15.  Аналогичноп.8 задания 2 вычислить значение g^h mod p (можновоспользоваться ранее сделанными вычислениями степени g по модулю p, выбраврезультат из строки h). Для рассматриваемого примера получено получено g^hmod p = 62.

16.  Проверитьвыполнение равенства y^r r^s mod p = g^hmod p. Если оно выполнено – подпись подлинная в противном случае –фальшивая. В примере получено 14 неравно 62, равенство не выполнено значитподпись фальшивая.