Защита информации в телекоммуникационных системах

 

Третья интерация

М3	11110001
Å
Н2	00010011
Н2 Å М3	11100010=22610
[(H2Å M3)2] (mod 91)	226 mod 77 = 72
Н3	01001000

 

Четвертая интерация

М4	11110001
Å
Н3	01001000
Н3 Å М4	10111001=18510
[(H3Å M4)2] (mod 91)	185 mod 77 = 31
Н4	00011111

 

Пятая интерация

М5	11110000
Å
Н4	00011111
Н4 Å М5	11101111=23910
[(H4Å M5)2] (mod 91)	239 mod 77 = 8
Н5	00001000

 

Шестая интерация

М6	11111001
Å
Н5	00001000
Н5 Å М6	11110001=24110
[(H5Å M6)2] (mod 91)	241 mod 77 = 10
Н6	00001010

 

Седьмая интерация

М7	11110000
Å
Н6	00001010
Н6 Å М7	11111010 = 25010
[(H6Å M7)2] (mod 91)	250 mod 77 = 19
Н7	00010011

 

Восьмая интерация

М8	11111110
Å
Н7	00010011
Н7 Å М8	11101101 = 23710
[(H7Å M8)2] (mod 91)	237 mod 77 = 6
Н8	00000110

 

Девятая интерация

М9	11110001
Å
Н8	00000110
Н8 Å М9	11110111 = 24710
[(H8Å M9)2] (mod 91)	247 mod 77 = 16
Н9	00010000

 

Десятая интерация

М10	11110011
Å
Н9	00010000
Н9 Å М10	11100011= 22710
[(H9Å M10)2] (mod 91)	227 mod 77 = 73
Н10	01001001

 

Одиннадцатая интерация

М11	11110110
Å
Н10	01001001
Н10 Å М11	10110111 = 18310
[(H10Å M11)2] (mod 91)	183 mod 77 = 29
Н11	00011101

 

Двенадцатая интерация

М12	11110001
Å
Н11	00011101
Н11 Å М12	11101100 = 23610
[(H11Å M12)2] (mod 91)	236 mod 77 = 5
Н12	00000101

 

 

 

Тринадцатая интерация

М13	11110001
Å
Н12	00000101
Н12 Å М13	11110100 = 24410
[(H12Å M13)2] (mod 91)	244 mod 77 = 13
Н13	01001101

 

Четырнадцатая интерация

М14	11110001
Å
Н13	01001101
Н13 Å М14	10111100= 18810
[(H13Å M14)2] (mod 91)	188 mod 77 = 34
Н14	00100010

 

 

Таким образом, исходное сообщение ПРИНТЕР имеет хеш – код m=34.

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

S=m^d (mod n) = 34²⁹ mod 77 = 34

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

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

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

m’=S^e (mod n) =34⁵ mod 77 = 34

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

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

 

 

 

 

 

Задание  №2

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

 

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

Номер зачетной книжки:

№****00

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

I		0	1	2	3	4
X		7	11	13	17	19
I	5		6	7	8	9
X	29		31	37	39	41

 

Xa=7

Xb=7

Xc=11

Xd=13

Xe=17

Так как g=2, пусть q=15401, тогда p=30803.

Проверим выполнение условий  данных: 

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

1<2<30802  и 2¹⁵⁴⁰¹ mod 30803=30802

Необходимые условия выполняются, значит, такое р подходит.

 

 

 

Решение:

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

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

Yb = g^Xb mod р = 2⁷mod 30803 = 128

Yc = g^Xc mod р = 2¹¹mod 30803 = 2048

Yd = g^Xd mod р= 2¹³mod 30803 = 8192

Ye = g^Xe mod р = 2¹⁷mod 30803 = 7860

 

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

 

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

 

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

Z_AC = (Y_C)^XAmodp = (2048)⁷ mod 30803 = 17068                                                                                               

Z_CA = (Y_A)^XCmodp = (128)¹¹ mod 30803 = 17068

Z = Zab=Zва

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

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

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

Последние цифры номера зачетной книжки – (00). Выбираем для трех абонентов (сообщение, p) -  (12,29), (14,31), (16,37).

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

I	0	1	2
Сообщение	14	16	18
J	0	1	2
p	31	37	41

 

 

 

 

 

 

 

Перейдем к описанию системы. Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение 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₃). Тогда алгоритм записывается следующим образом.