Файл: Лабораторная работа 2 Изучение системы цифровой подписи ЭльГамаля.pdf

Лабораторная работа № 3.2
Изучение системы цифровой подписи Эль-Гамаля
Задание
Выполнить вычисление и проверку электронной подписи сообщения по алгоритму Эль-
Гамаля.
Учебный алгоритм хэширования
1. Выбирается число h
0
– вектор инициализации. Число h
0
может быть выбрано случайно или получено неслучайным образом, например, как длина сообщения в символах.
2. Для каждого символа сообщения вычисляется значение h
0
=(M
i
+h i-1
)
2
mod (p-1), i=1,…n, n=|M|.
3. Вычисленное для последнего символа значение h n
, увеличенное на единицу, является хэш-значением сообщения: h(M)=h
n
+1.
Следует отметить, что вычисленное по этому алгоритму хэш-значение зависит от всех символов сообщения M.
Технология выполнения задания
Задание 1. Для сообщения M (в числовом представлении) сгенерировать электронную подпись по алгоритму Эль-Гамаля при заданных значениях общих параметров p=83 и g=15.
Хэш-значение сообщения вычисляется с помощью учебного алгоритма, начальное значение h
0
принимается равным числу десятичных разрядов в числовом представлении 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
0
= n, h
1
=(M
i
+h i-1
)
2
mod
(p-1), i=1,…,n, h(M)=h n
+1, где n – число десятичных знаков в числовом представлении сообщения M; M
i
– i-й знак числа M:

Вычисления можно производить в табличном процессоре MS Excel.
Получение h
0
производится текстовой функцией ДЛСТР, i-го символа сообщения M – текстовой функцией ПСТР, вычисление h i
– функцией
ОСТАТ
Для рассматриваемого примера получены следующие значения h
0
=5, h
1
=32,
h
2
=77, h
3
=0, h
4
=25, h
5
=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 используется функция ОСТАТ (=ОСТАТ(B11-
C2*G2;A2-1)). В рассматриваемом примере u=23.
6. Рассчитать значение k
-1
по модулю p-1 с помощью расширенного алгоритма Евклида
Рисунок 2. Реализация расширенного алгоритма Евклида
Рисунок 3. Пример вычислений по расширенному алгоритму Евклида
Для рассматриваемого примера получено значение k
-1
= 3.
7. Вычислить число s по формуле s=k
-1
u mod (p-1). Для вычисления можно воспользоваться функцией ОСТАТ (=ОСТАТ(A14*J2;A2-1)). В примере получено s = 69. Цифровая подпись сообщения M = 93551 является пара чисел (r,s) т.е (71, 69)

Рисунок 4. Результирующий результат s
Задание 2. Проверить правильность вычисления сгенерированной цифровой подписи.
8. Проверка правильности вычисления полученной цифровой подписи производится с помощью открытого ключа абонента. Сформировать открытый ключ y абонента по формуле y=g x
mod 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 r
r 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 r
r s
mod p=g h
mod p. Если равенство верное – подпись подлинная, т.е она была вычислена правильно. В примере получено 20 = 20, равенство выполнено, значит, подпись сгенерирована правильно.
Задание 3. Используется криптосистема Эль-Гамаля с теми же параметрами, что и в предыдущих заданиях. От абонента с открытым ключом y получено сообщение M (в числовом представлении), снабженное цифровой подписью (r, s). Проверить подлинность цифровой подписи. Хэш-значение сообщение вычисляется с помощью учебного алгоритма, начальное значение h
0
принимается равным числу десятичных разрядов в числовом представлении 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=34; M=8749; r=8; s=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 h
mod p = 62.
16. Проверить выполнение равенства y r
r s
mod p = g h
mod p. Если оно выполнено – подпись подлинная в противном случае – фальшивая. В примере получено 14 неравно 62, равенство не выполнено значит подпись фальшивая.