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

Размещено на http://www.allbest.ru/

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

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

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

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

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА №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. Значит по варианту исходные данные

	g=2
i=5	XA =29
j=8	XB=39
j=9	XC=41
j=0	XD=7
j=1	XE=11

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

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

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

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

q=15401

p=2*15401=30803

Проверим:

2¹⁵⁴⁰¹mod30803= 30802

1<2<30803- 1

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

X_A = 29; Y_A = g^X_A mod p = 2²⁹ mod 30803= 5425

X_B =39; Y_B = g^X_B mod p = 2³⁹ mod 30803= 10660

X_C = 41; Y_C = g^X_C mod p = 2⁴¹ mod 30803= 11837

X_D = 7; Y_D = g^X_D mod p = 2⁷ mod 30803= 128

X_E = 11; Y_E = g^X_E mod p = 2⁷ mod 30803= 2048

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

Абонент А:

Z_AB = (Y_B)^Х_A mod p = 10660²⁹mod 30803= 23625

Z_AC = (Y_C)^Х_A mod p = 11837²⁹mod 30803= 944

Z_AD = (Y_D)^Х_А mod p = 128 ²⁹mod 30803=28169

Z_AE = (Y_E)^Х_А mod p = 2048²⁹mod 30803= 24631

Абонент B:

Z_BA = (Y_A)^Х_B mod p = 5425³⁹mod 30803= 944

Z_BC = (Y_C)^Х_B mod p = 11837³⁹mod 30803= 4851

Z_BD = (Y_D)^Х_B mod p = 128³⁹mod 30803= 12633

Z_BE = (Y_E)^Х_Bmod p = 2048³⁹ mod 30803=3525



Абонент C:

Z_CA = (Y_A)^Х_C mod p = 5425⁴¹mod 30803= 21377

Z_CB = (Y_B)^Х_C mod p = 10660⁴¹mod 30803= 4851

Z_CD = (Y_D)^Х_C mod p = 128⁴¹ mod 30803=13715

Z_CE = (Y_E)^Х_C mod p = 2048 ⁴¹mod 30803= 5251

Абонент D:

Z_DA = (Y_A)^Х_D mod p = 5425⁷mod 30803 = 28169

Z_DB = (Y_B)^Х_D mod p = 10660⁷mod 30803= 12633

Z_DC = (Y_C)^Х_D mod p = 11837⁷mod 30803= 13715

Z_DE = (Y_E)^Х_D mod p = 2048⁷mod 30803= 17068

Абонент E:

Z_EA = (Y_A)^Х_E mod p = 5425¹¹mod 30803= 24631

Z_EB = (Y_B)^Х_E mod p = 10660¹¹mod 30803=3525

Z_EC = (Y_C)^Х_E mod p = 11837¹¹mod 30803= 5251

Z_ED = (Y_D)^Х_E mod p = 128¹¹mod 30803= 17068

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

Абонент	Секретное число	Открытый ключ	Закрытый ключ
A B C D E	XA XB XC XD XE	YA YB YC YD YE	ZAB, ZAC, ZAD ZAE ZBA, ZBC, ZBD, ZBE ZCA, ZCB, ZCD, ZCE ZDA, ZDB, ZDC, ZDE ZEA, ZEB, ZEC, ZED
Абонент	Секретное число	Открытый ключ	Закрытый ключ
A B C D E	29 39 41 7 11	5425 10660 11837 128 2048	23625, 944, 28169, 24631 944, 4851, 12633, 3525 21377, 4851, 13715, 5251 28169, 12633, 13715, 17068 24631, 3525, 5251, 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

c_B*d_Bmod (p - 1) = 1



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

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

11*19mod (53-1) = 1

17*49mod (53-1 )= 1

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

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

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

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

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

2. Пусть 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_C*d_Cmod (p - 1) = 1

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

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

17*49 mod (53-1) = 1

23*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

c_A=47, d_A= 2 ⁴⁷ mod 73 = 4

c_B=51, d_B = 2 ⁵¹ mod 73 =64

c_C=29, d_C= 2 ²⁹ mod 73 = 4

c_D=11, d_D= 2 ¹¹ mod 73 = 4

c_E=13, d_E= 2 ¹³ mod 73 = 16

Абонент	Секретный ключ	Открытый ключ
A=3	cA=47	dA= 4
B=15	cB=51	dB = 64
C=11	cC=29	dC= 4
D=15	cD=11	dD= 4
E=13	cE=13	dE= 16

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

Шаг 1. А формирует случайное число к, 1? к ? р-2, вычисляет числа

k = 3

r = g^kmod p = 2³ mod 73 = 8

e = 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

r = g^kmod p = 2³ mod 73 = 8

e = 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

r = g^kmod p = 2³ mod 73 = 8

e = 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

e = 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

e = 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г.

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

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

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

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

Размещено на Allbest.ru