Лабораторная работа 3.2 по криптографии. Лабораторная работа 2 Изучение системы цифровой подписи ЭльГамаля
 Скачать 466.45 Kb.
|
|
Лабораторная работа № 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, равенство не выполнено значит подпись фальшивая. |