X-PDF

Дистанционные курсы для педагогов

Поделиться статьей

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

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

 

Задание

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

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

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

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

 

h0=(Mi+hi-1)2 mod(p-1), i=1,…n, n=|M|.

3.     Вычисленное для последнего символа значение hn, увеличенное на единицу,является хэш-значением сообщения: h(M)=hn+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) по итерационной формуле h0= n, h1=(Mi+hi-1)2 mod(p-1), i=1,…,n, h(M)=hn+1, где n – число десятичных знаков вчисловом представлении сообщения M; Mi – i-й знак числа M:

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

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

4.     Вычислить число r по формуле r=gk 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)

Представленная информация была полезной?
ДА
59.35%
НЕТ
40.65%
Проголосовало: 1139

 

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

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

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

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

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

11.  Проверитьвыполнение равенства yrrs mod p=gh 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.  Вычислитьзначение yr mod p и rs mod p, а затем ихпроизведение по модулю p. Для вычисления значений степени по модулю всреде MS Excel может быть использован итерационный алгоритм, описанный в п.4задания 1. Для рассматриваемого примера получено: yr mod p=51,rs mod p=67, yr rs mod p=14.

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

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

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

 

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

16.  Проверитьвыполнение равенства yr rs mod p = ghmod p. Если оно выполнено – подпись подлинная в противном случае –фальшивая. В примере получено 14 неравно 62, равенство не выполнено значитподпись фальшивая.


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
59.35%
НЕТ
40.65%
Проголосовало: 1139

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

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


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

Поделиться статьейВключает 30 родов, около 1000 видов. Распространение: горные и умеренные области Северного полушария . многие виды произрастают в горах


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

Поделиться статьейЦенообразование является важнейшим рычагом экономического управления. Цена как экономическая категория отражает общественно необходимые затраты на производство и реализацию туристского


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет