Лабораторная работа №13. Изучение электронной цифровой подписи Эль-Гамаля

Появление криптографии с открытым ключом позволило решать задачи, которые ранее считались неразрешимыми. К таким задачам относится использование цифрового аналога собственноручной подписи абонента – электронной цифровой подписи (ЭЦП).

Электронная цифровая подпись обеспечивает те же свойства, что и собственноручная подпись автора сообщения, то есть гарантирует выполнение следующих свойств:

• Подлинность подписи можно проверить;

• Подпись нельзя подделать (данную подпись может поставить только ее обладатель и никто другой);

• Подпись является неотъемлемой частью документа и не может быть перенесена в другой документ.

• Подписанный документ не подлежит никаким изменениям.

• Автор подписи не может от нее отказаться.

Электронная цифровая подпись для сообщения является числом, зависящим от самого сообщения и от секретного ключа, известного только подписывающему субъекту. При этом подпись должна легко проверяться без знания секретного ключа.

Наиболее распространена технология ЭЦП, основанная на совместном применении алгоритмов хеширования и шифрования с открытым ключом (RSA или Эль-Гамаля).

Для подтверждения авторства, шифрование проводится личным ключом абонента, расшифровку (и, таким образом, проверку подлинности автора) может произвести любой пользователь открытым ключом абонента (рис.59).

Рис.59. Подтверждение авторства с помощью криптографии с открытым ключом

Как правило, шифруется не само сообщение, а его «дайджест» – значение фиксированной длины, зависящее от подписываемого сообщения. Для формирования дайджеста и используется алгоритм хеширования (хеш-функция), ставящий в соответствие тексту произвольной длины некоторое число фиксированной длины.

Рассмотрим алгоритм подписи Эль-Гамаля, который лежит в основе стандартов ЭЦП.

Сначала выбираются параметры системы Эль-Гамаля, общие для всех абонентов группы: простое число p и число g, 1< g < p-1; для обеспечения стойкости системы числа p и g выбираются специальным образом.

Затем, каждый абонент группы выбирает свой личный ключ – случайное число x, 1 < x < p-1, которое держится в секрете. Затем вычисляется открытый ключ y по формуле: y = g^x mod p. Абонент публикует свой открытый ключ, чтобы каждый мог проверить его подпись.

Алгоритм формирования подписи выглядит следующим образом:

1. Пусть M – подписываемое сообщение. Отправитель вычисляет хеш-значение подписываемого сообщения h = h(M). Значение h должно удовлетворять неравенству 0 < h < p.

2. Далее отправитель выбирает случайное число k, 0 < k < p-1, взаимно простое с p-1, и вычисляет числа:

r = g^k mod p,

u = (h-xr) mod (p-1),

s = k^-1u mod (p-1)

k^-1 – число, обратное k по модулю p-1, k^-1 существует, так как k и p-1 – взаимно просты.

3. Подпись (r, s) добавляется к сообщению, и тройка (M, r, s) передается получателю.

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

4. Получатель заново вычисляет хеш-значение присланного сообщения h(M) и проверяет подпись, используя равенство:

y^r r^s = g^h (mod p).

Если подпись верна, то это равенство выполняется.

Отметим, что число k выбирается заново для каждого нового подписания сообщения и должно держаться в секрете.

Используемые на практике алгоритмы хеширования достаточно сложны, поэтому будем использовать учебный алгоритм формирования хеш-значения h(M). Будем считать, что сообщение M представлено в числовом виде, M_i, i=1,…,n – цифры, представляющие сообщение M.

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

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

2. Для каждого символа сообщения вычисляется значение h_i = (M_i + h_i-1)² mod (p-1), i=1,…,n.

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

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

Задание

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

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

Задание. 1. Известны значения общих параметров системы Эль-Гамаля: p=59, g=14, личный ключ абонента x и случайное число k, выбранное для формирования подписи сообщения. Для заданного в числовом представлении сообщения M сгенерировать цифровую электронную подпись по алгоритму Эль-Гамаля. Хеш-значение сообщение вычисляется с помощью учебного алгоритма, начальное значение h₀ принимается равным числу десятичных разрядов в числовом представлении M.

1. Выбрать параметры x и k системы цифровой подписи и подписываемый текст M в соответствии с номером варианта (табл.20, выбор осуществляется по порядковому номеру в официальном списке группы).

Таблица 20. Варианты задания

Вариант	x	k	M
1	5	31	5211
2	12	47	3825
3	28	7	2412
4	7	21	1234
5	8	33	9461
6	17	11	7231
7	22	9	5184
8	10	15	4251
9	4	41	4629
10	19	35	3122
11	33	39	6236
12	25	17	2971
13	55	19	3616
14	6	27	7222
15	21	5	3845
16	13	23	1197
17	11	55	4225
18	48	13	3163
19	37	25	2617
20	9	15	1831
21	15	7	2528
22	52	45	4911
23	24	3	5269
24	18	37	2120
25	44	51	1712

Сформировать цифровую подпись для сообщения M по аналогии с рассмотренным далее примером.

Пример: x = 34; k = 43; M = 1111.

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

• Для рассматриваемого примера h₀=4, p=59, M_i=1, i=1,…,4.

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

Рис.60. Пример расчета хеш-значения

В рассматриваемом примере получили h(M)=23 (рис.61).

Рис.61. Результаты расчета хеш-значения

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

• На новом листе в ячейку A1 внести номер шага: 1, в ячейку B1 – значение g (число 14).

• В ячейку А2 внести номер шага: 2, в ячейку B2 – итерационную формулу для вычисления остатка от деления по модулю p, формула примет вид:

=ОСТАТ(14*B1; 59)

• Выделить диапазон ячеек A1:A2 и растянуть вниз, заполнив ячейки столбца А рядом данных до значения k (в примере = 43) включительно.

• Выделить ячейку В2 и растянуть вниз (скопировать ее) в диапазон ячеек столбца B строки с номером k включительно (в примере – до ячейки В43). Результат вычисления находится в последней заполненной ячейке столбца B.

Для рассматриваемого примера получили:

r =14⁴³ mod 59 = 32.

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

В примере получили: u = (23-34*32) mod (59-1) = 37.

5. Рассчитать значение k^-1 по модулю p-1 с помощью расширенного алгоритма Евклида (описание алгоритма приведено в предыдущей лабораторной работе):

• Сформировать первую строку расширенного алгоритма Евклида: на новом листе в ячейку A1 занести значение p-1 – 58, в ячейку B1 – 0.

• Сформировать вторую строку расширенного алгоритма Евклида: в ячейку A2 занести значение k (в примере – 43), в ячейку B2 – 1.

• Сформировать третью строку: в ячейку C3 занести значение, вычисленное по формуле: =ЧАСТНОЕ(A1,A2), в ячейку A3 занести формулу: =ОСТАТ(A1,A2), в ячейку B3 – формулу: =B1-B2*C3 (рис.62).

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

• Выделить диапазон ячеек A3:C3 и растянуть (скопировать) на несколько строк вниз, пока в столбце A не будет получено нулевое значение (рис.63).

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

• Значение k^-1 находится в предпоследней строке в столбце B, то есть, в строке, предшествующей строке, начинающейся с 0. Строка с результатом должна начинаться с 1.

Для рассматриваемого примера значение k^-1 содержится в ячейке B6, k^-1=27.

ПРИМЕЧАНИЕ: Если полученное значение k^-1 – отрицательное, следует взять его по модулю p-1. Для этого можно использовать функцию ОСТАТ() или просто сложить k^-1 со значением p-1.

6. Вычислить число s по формуле s = k^-1u mod (p-1). Для вычисления можно воспользоваться функцией ОСТАТ().

В примере s = 27*37 mod (59-1) = 13.

7. Сформировать цифровую подпись сообщения M – пару чисел (r, s).

Цифровая подпись сообщения M: (32, 13).

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

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

• Для вычисления значения y в среде MS Excel может быть использован итерационный алгоритм, описанный в пункте 3.

Для рассматриваемого примера y = 14³⁴ mod 59 = 20.

9. Аналогичным образом вычислить значения y^r mod p и r^s mod p, а затем их произведение по модулю p.

В примере получаем:

y^r mod p = 20³² mod 59 = 35,

r^s mod p = 32¹³ mod 59 = 10,

y^r r^s mod p = 35*10 mod 59 = 55.

10. Вычислить значение g^h mod p, значение h было получено в пункте 2.

В примере g^h mod p = 14²³ mod 59 = 55.

11. Проверить выполнение равенства y^r r^s mod p = g^h mod p, если равенство выполняется – подпись подлинная, то есть она была вычислена правильно.

В примере получили 55=55, равенство выполняется, значит подпись сгенерирована правильно.

12. Продемонстрировать результаты выполнения заданий 1-2 лабораторной работы преподавателю.

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

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

Таблица 21. Варианты задания

Вариант	Открытый ключ отправителя y	Полученное сообщение M	Цифровая подпись
			r	s
1	9	8723	23	43
2	25	3361	37	29
3	7	8722	11	34
4	35	7005	34	47
5	6	9054	39	56
6	37	2401	24	48
7	24	5524	33	9
8	48	4382	47	40
9	50	6525	44	31
10	2	7993	50	14
11	39	7865	40	49
12	12	3217	10	6
13	3	8593	30	42
14	54	6620	2	39
15	43	1229	54	32
16	15	1333	31	9
17	10	2301	42	29
18	52	6543	13	48
19	21	9922	33	8
20	4	2211	18	11
21	42	1122	43	54
22	46	1211	24	12
23	49	5421	52	25
24	23	5241	55	16
25	33	6540	6	26

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

Пример: y = 20; M = 7569; r = 32; s = 46.

14. Вычислить значения y^r mod p и r^s mod p, а затем их произведение по модулю p:

• Для вычисления значения степени по модулю в среде MS Excel может быть использован итерационный алгоритм, описанный в пункте 3.

В рассматриваемом примере получаем:

y^r mod p = 20³² mod 59 = 35,

r^s mod p = 32⁴⁶ mod 59 = 15,

y^r r^s mod p = 35*15 mod 59 = 53.

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

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

Получили: h=6.

16. Вычислить значение g^h mod p.

В примере g^h mod p = 14⁶ mod 59 = 15.

Рис.64.Пример вычисления хеш-значения

17. Проверить выполнение равенства y^r r^s mod p = g^h mod p, если равенство выполняется – подпись подлинная, в противном случае – фальшивая.

В примере получили 5315, равенство не выполняется, значит подпись фальшивая.

18. Продемонстрировать результаты выполнения задания 3 преподавателю.

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

1. Какой ключ должен использовать отправитель сообщения для создания подписи в асимметричных криптосистемах?

(Свой личный ключ)

2. Какой ключ должен использовать получатель сообщения для проверки подписи в асимметричных криптосистемах?

(Открытый ключ отправителя)

3. Что представляет собой цифровая подпись сообщения по алгоритму Эль-Гамаля?

(Подпись представляет собой пару чисел r и s)

4. Какая информация необходима для генерации цифровой подписи в алгоритме Эль-Гамаля?

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

5. Какую функцию в алгоритме Эль-Гамаля выполняет случайное число k?

(Использование случайного числа k позволяет сделать цифровую подпись рандомизированной, то есть для одного и того же сообщения с использованием одного и того же закрытого ключа при каждом подписывании создаются разные подписи, что повышает стойкость системы)

6. Следует ли знать случайное число k для проверки подписи сообщения?

(Для проверки подписи знания случайного числа k не требуется, это число держится отправителем в секрете).

7. Какая информация необходима для проверки цифровой подписи в алгоритме Эль-Гамаля?

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