Система с открытым ключом Диффи-Хелмана. Шифрование по алгоритму Шамира и Эль-Гамаля

Система с открытым ключом Диффи-Хелмана. Шифрование по алгоритму Шамира и Эль-Гамаля

Некоммерческое акционерное общество

«АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ»

Факультет аэрокосмических и информационных технологий

Кафедра компьютерной и инфокоммуникационной безопасности

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА №2

По дисциплине: «Информационная безопасность и защита информации»

По теме: «Система с открытым ключом Диффи-Хелмана. Шифрование по алгоритму Шамира и Эль-Гамаля»

Выполнил: Телқожа А.Н.

Группа: Инф-13

Принял: ст.преп. Якубов Б.М.

Алматы 2016

Содержание

Введение

Задание 1.Система с открытым ключом Диффи-Хелмана

Задание 2. Шифрование по алгоритму Шамира

Задание 3.Шифрование по алгоритму Эль-Гамаля

Заключение

Список литературы

Введение

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

Протокол Ди́ффи-Хе́ллмана (англ.DiffieHellman, DH) - криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.

Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии - проблему распределения ключей.

В чистом виде алгоритм Диффи-Хеллмана уязвим для модификации данных в канале связи, в том числе для атаки «Человек посередине», поэтому схемы с его использованием применяют дополнительные методы односторонней или двусторонней аутентификации.

Схема Эль-Гамаля (Elgamal) - криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США(DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1985 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Задание 1. Система с открытым ключом Диффи-Хелмана

защита информация телекоммуникационный криптография

Рисунок 1 - схема обмена ключами в системе Диффи-Хелмана

Сгенерировать секретные ключи для пяти абонентов A, B, C, D и Е по методу Диффи-Хеллмана (DH). Так как последние цифры студенческого билета 58, то i=5 и j=8. Значит по варианту исходные данные

Число р выбирается таким образом, чтобы выполнялось равенство

р=2q+1 (где q- также простое число)

и были справедливы неравенства

<g< р - 1 и g^qmod р 1.

q=15401

p=2*15401=30803

Проверим:

2¹⁵⁴⁰¹mod30803= 30802

1<2<30803- 1

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

_A = 29; Y_A = g^X_A mod p = 2²⁹ mod 30803= 5425_B =39; Y_B = g^X_B mod p = 2³⁹ mod 30803= 10660_C = 41; Y_C = g^X_C mod p = 2⁴¹ mod 30803= 11837_D = 7; Y_D = g^X_D mod p = 2⁷ mod 30803= 128_E = 11; Y_E = g^X_E mod p = 2⁷ mod 30803= 2048

Вычисляем закрытый ключ.

Абонент А:

Z_AB = (Y_B)^Х_A mod p = 10660²⁹mod 30803= 23625_AC = (Y_C)^Х_A mod p = 11837²⁹mod 30803= 944_AD = (Y_D)^Х_А mod p = 128 ²⁹mod 30803=28169_AE = (Y_E)^Х_А mod p = 2048²⁹mod 30803= 24631

Абонент B:

Z_BA = (Y_A)^Х_B mod p = 5425³⁹mod 30803= 944_BC = (Y_C)^Х_B mod p = 11837³⁹mod 30803= 4851_BD = (Y_D)^Х_B mod p = 128³⁹mod 30803= 12633_BE = (Y_E)^Х_Bmod p = 2048³⁹ mod 30803=3525

Абонент C:

Z_CA = (Y_A)^Х_C mod p = 5425⁴¹mod 30803= 21377_CB = (Y_B)^Х_C mod p = 10660⁴¹mod 30803= 4851_CD = (Y_D)^Х_C mod p = 128⁴¹ mod 30803=13715_CE = (Y_E)^Х_C mod p = 2048 ⁴¹mod 30803= 5251

Абонент D:

Z_DA = (Y_A)^Х_D mod p = 5425⁷mod 30803 = 28169_DB = (Y_B)^Х_D mod p = 10660⁷mod 30803= 12633_DC = (Y_C)^Х_D mod p = 11837⁷mod 30803= 13715_DE = (Y_E)^Х_D mod p = 2048⁷mod 30803= 17068

Абонент E:

Z_EA = (Y_A)^Х_E mod p = 5425¹¹mod 30803= 24631_EB = (Y_B)^Х_E mod p = 10660¹¹mod 30803=3525_EC = (Y_C)^Х_E mod p = 11837¹¹mod 30803= 5251_ED = (Y_D)^Х_E mod p = 128¹¹mod 30803= 17068

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

Задание 2. Шифрование по алгоритму Шамира

Рисунок 2 - схема обмена ключами в системе Шамира

Зашифровать сообщение по алгоритму Шамира, взяв значение сообщения m и значение p по варианту.

m_A = 22, p = 53

Пусть А хочет передать В сообщение m_A = 22. А выбирает p = 53, c_A = 11 и вычисляет d_A = 19. Аналогично, В выбирает параметры с_B = 17 и d_B= 49.

Секретные числа c_A,d_A,с_B,d_B должны быть выбраны таким образом, чтобы выполнялось равенство

c_A*d_Amod (p - 1) = 1_B*d_Bmod (p - 1) = 1

c_A,с_B выбираем так, чтобы они были взаимно простые с (р - 1), а d_A,d_Bвычисляем по формуле.

Проверим выбранные нами c_A,d_A,с_B,d_B

*19mod (53-1) = 1

*49mod (53-1 )= 1

Переходим к протоколу Шамира

Шаг 1. X₁ = 22¹¹mod53 = 26

Шаг 2. X₂ = 26¹⁷mod53 = 35

Шаг 3. X₃ = 35¹⁹mod53 = 14

Шаг 4. X₄ = 14⁴⁹mod53 = 22

. Пусть B хочет передать сообщение m_B = 24. B выбирает p = 53, с_B = 17 и вычисляет d_B= 49. Аналогично, C выбирает параметры с_C = 23 и d_C=43.

Секретные числа c_B,d_B,с_C,d_C должны быть выбраны таким образом, чтобы выполнялось равенство

c_B*d_B mod (p - 1) = 1_C*d_Cmod (p - 1) = 1

c_B,с_C выбираем так, чтобы они были взаимно простые с (р - 1), а d_B,d_Cвычисляем по формуле.

Проверим выбранные нами с_B,d_B,с_C,d_C

*49 mod (53-1) = 1

*43mod(53-1) = 1

Переходим к протоколу Шамира

Шаг 1. X₁ = 24¹⁷mod53 = 49

Шаг 2. X₂ = 49²³mod53 = 24

Шаг 3. X₃ = 24⁴⁹mod53 = 47

Шаг 4. X₄ = 47⁴³mod53 = 24

3. Пусть C хочет передать сообщение m_C = 26. C выбирает p = 53, с_C = 23 и вычисляет d_C= 43. Аналогично, A выбирает параметры с_A = 11 и d_A=19.

Переходим к протоколу Шамира

Шаг 1. X₁ = 26²³mod53 = 8

Шаг 2. X₂ = 8¹¹mod53 = 31

Шаг 3. X₃ = 31⁴³mod53 = 14

Шаг 4. X₄ = 14¹⁹mod53 = 26

Задание 3. Шифрование по методу Эль-Гамаля

Рисунок 3 - схема обмена ключами в системе Эль-Гамаля

По варианту выбрать числа p и g и провести шифрование по методу Эль-Гамаля для 5 абонентов.

p = 173, g = 2, m1=3, m2=15, m3=11, m4=15, m5=13.

Каждый абонент группы выбирает свое секретное число c_i, 1<c_i<p-1 и вычисляет соответствующее ему открытое число d_i

d_i= g ^ci mod p_A=47, d_A= 2 ⁴⁷ mod 73 = 4_B=51, d_B = 2 ⁵¹ mod 73 =64_C=29, d_C= 2 ²⁹ mod 73 = 4_D=11, d_D= 2 ¹¹ mod 73 = 4_E=13, d_E= 2 ¹³ mod 73 = 16

1)      Сообщение m1 = 3.

k = 3= g^kmod p = 2³ mod 73 = 8= m*d_A^k mod p = 3*4³ mod 73 = 46

и передает пару чисел (r,e) абоненту В.

Шаг 2. В, получив (r,e) вычисляет

m’ = e*r^p-1-c_A mod p = 46*8^73-1-47 mod 73 = 3.

2)      Сообщение m2 = 15.

Шаг 1. Сообщение m2 = 15. B формирует случайное число к, 1≤ к ≤ р-2, вычисляет числа

k = 3= g^kmod p = 2³ mod 73 = 8= m*d_b^k mod p = 15*64³ mod 73 = 15

и передает пару чисел (r,e) абоненту C.

Шаг 2.C, получив (r,e) вычисляет

m’ = e*r^p-1-c_b mod p = 15*8^73-1-51 mod 73 = 15

3)      Сообщение m3 = 11.

Шаг 1. Сообщение m3 = 11. C формирует случайное число к, 1≤ к ≤ р-2, вычисляет числа

k = 3= g^kmod p = 2³ mod 73 = 8= m*d_c^k mod p = 11*4³ mod 73 = 47

и передает пару чисел (r,e) абоненту D.

Шаг 2.D, получив (r,e) вычисляет

m’ = e*r^p-1-c_c mod p = 47*8^73-1-29 mod 73 = 11

4)      Сообщение m4 = 15.

Шаг 1. Сообщение m4 = 15. D формирует случайное число к, 1≤ к ≤ р-2, вычисляет числа

r = g^kmod p = 2³ mod 73 = 8= m*d_d^k mod p = 15*4³ mod 73 = 11

и передает пару чисел (r,e) абоненту E.

Шаг 2.E, получив (r,e) вычисляет

m’ = e*r^p-1-c_d mod p = 11*8^73-1-11 mod 73 = 15

5)      Сообщение m5 = 13.

Шаг 1. Сообщение m5 = 13. E формирует случайное число к, 1≤ к ≤ р-2, вычисляет числа

r = g^kmod p = 2³ mod 73 = 8= m*d_e^k mod p = 13*16³ mod 73 = 31

и передает пару чисел (r,e) абоненту A.

Шаг 2.A, получив (r,e) вычисляет

m’ = e*r^p-1-c_e mod p = 31*8^73-1-13 mod 73 = 13

Заключение

Протокол Ди́ффи-Хе́ллмана анализируется как криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.

Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии - проблему распределения ключей.

Использование системы Диффи - Хеллмана облегчает снабжение большого количества абонентов секретными ключами.

В чистом виде алгоритм Диффи-Хеллмана уязвим для модификации данных в канале связи, в том числе для атаки «Человек посередине», поэтому схемы с его использованием применяют дополнительные методы односторонней или двусторонней аутентификации

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

Список литературы

1. Якубов Б.М, Информационная безопасность и защита информации Конспект лекций.-АУЭС, Алматы, 2015г.

. Якубов Б.М, Информационная безопасность и защита информации. Методические указания к выполнению расчетно-графических работ АУЭС, Алматы, 2015 г.

3. Рябко Б. Я., Фионов А.Н. Криптографические методы защиты информации. -М: Горячая линия- Телеком, 2005.

4. Петраков А.В. Основы практической защиты информации. 2-е издание Учебн. Пособие. - М: Радио и связь 2008

5. Романец Ю. В. Защита информации в компьютерных системах и сетях.  /Под ред. В.Ф. Шаньгина. - М: 1999