Курсовая работа по «Защите информации в телекоммуникационных системах»

 

Таким образом, исходное сообщение  ПЛЮС имеет хеш – код m=46.

 

Для вычисления цифровой подписи  используем следующую формулу:

 

S=m^d (mod n) = 46⁴³ mod 77 = 74

 

Пара (M, S) передается получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа d.

Получив пару (M, S), получатель вычисляет хеш – код сообщения М двумя способами:

1) Восстанавливает хеш  – код m’, применяя криптографическое преобразование подписи S с использованием открытого ключа e:

 

m’=S^e (mod n) =74⁷ mod 77 = 46

 

2) Находит результат хеширования  принятого сообщения с помощью  той же хеш – функции: m=H(M) =46.

При равенстве вычисленных  значений m’ и m получатель признает пару (M, S) подлинной.

 

Контрольные вопросы

1. Какими преимуществами  перед другими алгоритмами с  закрытым ключом обладает система  Диффи-Хеллмана?

2. Дайте краткую характеристику  системы Диффи-Хеллмана.

3. Объясните, почему число  р, необходимое при вычислении  секретных ключей, следует выбирать  большим?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание №2

 

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

 

Сгенерировать секретные  ключи для пяти абонентов по методу  Диффи-Хеллмана (DH). Для этого взять значение секретного ключа x из таблицы 1. Соответствующие значения открытого ключа вычислить и результаты внести в таблицу. Вариант задания определяется по номеру i (предпоследняя цифра) и j (последняя цифра зачетной книжки)– требуемая для реализации этого алгоритма число x . Число j – начальный номер для второго абонента при выборе числа x. Для выбора x для связи с пятью абонентами необходимо по циклической процедуре выбрать x по последней цифре зачетки.

Значения согласно варианту:

i	j
23	7

Xa=7

Xb=11

Xc=13

Xd=17

Xe=19

 

Так как g=23, пусть q=1783, тогда p=3566.

Проверим выполнение условий  данных в методических указаниях: 

1<g<p-1  и g^qmodp≠1

1<23<3566  и  23¹⁷⁸³ mod 3567=605

 

 

 

 

Решение:

 

Вычислим открытые числа  Y для пяти абонентов по следующей формуле:

Ya = g^Xa mod р = 2⁷mod 3567 = 128

Yb = g^Xb mod р = 2¹¹mod 3567 = 2048

Yc = g^Xc mod р = 2¹³mod 3567 = 1058

Yd = g^Xd mod р= 2¹⁷mod 3567 = 2660

Ye = g^Xe mod р = 2¹⁹mod 3567 = 3506

 

 

Таблица1.3  Ключи пользователей  в системе Диффи-Хеллмана

Абонент	Секретный ключ	Открытый ключ
A	7	128
B	11	2048
C	13	1058
D	17	2660
E	19	3506

 

Приведем пример работы алгоритма  Диффи-Хеллмана. Покажем как абонент  A и B смогут вычислить секретные ключи, благодаря открытым числам Ya и Yb. Вычислим следующие величины:

Z_AB = (Y_B)^XAmodp = (2048)⁷ mod 3567 = 1061                                                                                               

Z_BA = (Y_A)^XBmodp = (128)¹¹ mod 3567 = 1061

Z = Zab=Zва

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

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

 

Зашифровать сообщение по алгоритму Шамира для трех абонентов,  взяв значение сообщения m и значение p из таблицы 2. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j – требуемые для реализации этого алгоритма число р. Выбор данных для других абонентов произвести циклически согласно процедуре (i + 1) и (g + 1).

Таблица 2  Исходные данные для выбора сообщений (m)

i	4	5	6
Сообщение	20	22	24
j	0	1	2
p	29	31	37

 

Решение:

Перейдем к описанию системы. Пусть есть два абонента Аи В, соединенные  линией связи. А хочет передать сообщение m абоненту Б так, чтобы никто не узнал его содержание. А выбирает случайное большое простое число р и открыто передает его В. Затем А выбирает два числа с_{А и} d_A , такие, что

с_Аd_A mod (р - 1) = 1.                                         (2.1)

Эти числа А держит в секрете и передавать не будет. В тоже выбирает два числа с_в    d_в, такие, что

с_в<d_в mod (p - 1) = 1,                                        (2.2)

и держит их в секрете.

После этого А передает свое сообщение m, используя трехступенчатый протокол. Если m < р (m рассматривается как число), то сообщение т передается сразу , если же      т р, то сообщение представляется в виде m₁, m₂,..., m_t, где все m_i < р, и затем передаются последовательно m₁, m₂,..., m_t. При этом для кодирования каждого m_i лучше выбирать случайно новые пары (c_A,d_A) и (c_B,d_B) — в противном случае надежность системы понижается. В настоящее время такой шифр, как правило, используется для передачи чисел, например, секретных ключей, значения которых меньше р. Таким образом, мы будем рассматривать только случай m < р.

 

 

Описание протокола.

Шаг 1.  А вычисляет число: Х₁ =m^СА modp  (2.3),                                              где m — исходное сообщение, и пересылает х₁ к В.

Шаг 2.   В, получив х₁, вычисляет число: X₂ = х₁^CB mod p (2.4),                                                                                                          

и передает х₂ к А.

Шаг 3.  А вычисляет число: X₃ = х₂^dA mod p (2.5),                                                                                       

и передает его В.

Шаг 4.   В, получив х₃, вычисляет число X₄ = x₃^dB mod p (2.6).      

                                                                               

Утверждение  (свойства протокола Шамира).

1)   х₄ = m, т.е. в результате реализации протокола от А к В действительно передается исходное сообщение;

2)   злоумышленник не может, узнать, какое сообщение было передано.

Доказательство. Вначале  заметим, что любое целое число  е  0 может быть представлено в виде е = k(р-1)+r, где r = е mod (p-1). Поэтому на основании теоремы Ферма:     (2.7).                                        

Справедливость первого  пункта утверждения вытекает из следующей цепочки равенств:

(предпоследнее равенство  следует из (2.7), а последнее выполняется  в силу (2.1) и (2.2)).

Доказательство второго  пункта утверждения основано на предположении, что для злоумышленника, пытающегося определить m, не существует стратегии более эффективной, чем следующая. Вначале он вычисляет C_B из (2.4), затем находит d_B и, наконец, вычисляет Х₄ = m по (2.6). Но для осуществления этой стратегии злоумышленник должен решить задачу дискретного логарифмирования (2.4), что практически невозможно при больших р.           

Опишем метод нахождения пар c_A,d_A и с_B,d_B, удовлетворяющих (2.1) и (2.2). Достаточно описать только действия для абонента А. так как действия для В совершенно аналогичны. Число с_A выбираем случайно так, чтобы оно было взаимно простым с р-1 (поиск целесообразно вести среди нечетных чисел, так как р - 1 четно), Затем вычисляем d_A с помощью обобщенного алгоритма Евклида.

Теорема  Пусть a и b – два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа x и y, такие, что

 

ax + by = gcd(a, b).     (1)

 

Обобщенный алгоритм Евклида  служит для отыскания gcd(a,b) и x,y, удовлетворяющих (1). Введем три строки U=(u₁, u₂, u₃), V=(v₁, v₂, v₃) и Т=(t₁, t₂, t₃). Тогда алгоритм записывается следующим образом.

 

Решение:

Пусть А хочет передать В сообщение m = 20. А выбирает р = 29,

с_Аd_A mod (р - 1) = 1.                                        

с_А = 5 , d_A = 17.

Аналогично,  В выбирает параметры

с_вd_в mod (p - 1) = 1

c_B = 3 и d_B = 19. Переходим к протоколу Шамира.

Шаг 1. x₁ = 20⁵mod 29 =24.

Шаг 2. х₂ = 24³ mod 29 = 20.

ШагЗ.  x₃= 20¹⁷ mod 29 = 25.

Шаг 4. х₄ = 25¹⁹ mod 29 = 20.

Таким образом, В получил  передаваемое сообщение m = 20.      

Пусть B хочет передать C сообщение m = 22. B выбирает р = 31,

С_Bd_B mod (р - 1) = 1.                                        

С_B = 7 , d_B = 13.

Аналогично. C выбирает параметры

С_cd_c mod (p - 1) = 1

C_c = 11 и d_c = 11. Переходим к протоколу Шамира.

Шаг 1. x₁ = 22⁷mod 31 =21.

Шаг 2. х₂ = 21¹¹ mod 31 = 12.

ШагЗ.  x₃= 12¹³ mod 31 =17.

Шаг 4. х₄ = 17¹¹ mod 31 =22.

Таким образом, C получил передаваемое сообщение m = 22.      

1. Пусть R хочет передать A сообщение m = 24. C выбирает р = 37,

С_Rd_R mod (р - 1) = 1.                                        

С_R = 5 , d_R = 29.

Аналогично. В выбирает параметры

С_Ad_A mod (p - 1) = 1

C_A = 7 и d_A = 31. Переходим к протоколу Шамира.

Шаг 1. x₁ = 24⁵mod 37 =2.

Шаг 2. х₂ = 2⁷ mod 37 = 17

ШагЗ.  x₃= 17²⁹ mod 37 = 5.

Шаг 4. х₄ = 5³¹ mod 37 =24.

Таким образом, A получил передаваемое сообщение m = 24.      

 

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

 

По таблице 3 выбрать сообщение  m и секретный ключ x  и провести шифрование по методу Эль-Гамаля для пяти абонентов. Вариант задания определяется последними цифрами номера студенческого билета. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j (последняя цифра) – требуемые для реализации этого алгоритма секретный ключ x. Исходные данные для других четырех секретных ключей x выбираются циклически по процедуре (i+1) и (j+1).

 

Таблица 4 Исходные данные для  выбора сообщений и числа х.

i	4	5	6	7	8
Сообщение	13	3	15	11	15
j	0	1	2	3	4
х	29	11	13	7	19

 

 

Решение:

 

Пусть имеются абоненты А, В, С, D, которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищенных каналов связи. Шифр Эль – Гамаля  решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку сообщения. Фактически здесь используется схема Диффи – Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего сообщения секретный ключ вычисляется заново.

Для всей группы абонентов  выбираются некоторое большое простое число р и число g, такие, что различные степени g суть различные числа по модулю р. Числа р и g передаются абонентам в открытом виде (они могут использоваться всеми абонентами сети).

Нам необходимо выбрать числа  p и g так, чтобы они отвечали следующим требованиям:

g^q mod p

1,

где p=2q+1.

Возьмем p=29 и g=11.

2q+1=29  q=14

Проверим соотношение:

11¹⁴ mod 29= 28

1 – выполняется.

Затем каждый абонент группы выбирает свое секретное число c_i:

                                     1 < C_i < р – 1

(см. таблицу 5.1), и вычисляет соответствующее ему открытое число d_i:

                                                     d_i=g^ci mod p        (3.1)

 

 

 

Т а б л и ц а 5.1 – Ключи пользователей в системе  Эль – Гамаля

Абонент	Секретный ключ	Открытый ключ
A	3	26
B	5	14
C	7	12
D	11	10