Защита Информации в ТКС

 

 

 

 

 

 

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

М9	11110000
Å
Н8	00010000
Н8 Å М9	11100000= 22410
[(H8Å M9)2] (mod 33)	2242 mod 33 = 26
Н9	00011010

 

 

 

 

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

М10	11111110
Å
Н9	00011010
Н9 Å М10	11100100= 22810
[(H9Å M10)2] (mod 33)	2282 mod 33 = 30
Н10	00011110

 

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

М11	11110001
Å
Н10	00011110
Н10 Å М11	11101111= 23910
[(H10Å M11)2] (mod33)	2392 mod 33 = 8
Н11	00001000

 

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

М12	11111101
Å
Н11	00001000
Н11 Å М12	11110101= 24510
[(H11Å M12)2] (mod33)	2452 mod 33 = 14
Н12	00001110

 

Таким образом, исходное сообщение КОРЕНЬ имеет  хеш – код m=14.

 

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

 

S=m^d (mod n) = 14³ mod 33 = 5

 

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

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

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

 

m’=S^e (mod n) =5⁷ mod 33 = 14

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

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

2 Задание 2

 

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

 

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

 

Таблица 1.1 Исходные данные для числа g:

i	0	1	2	3	4	5	6	7	8	9
g	1	3	5	11	23	29	41	101	113	179

 

 

Таблица 1.2  Исходные данные для чисел X_A, X_B, X_C, X_D, X_E:

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

 

Исходные данные:

i	7
g	101

j	3
Xa	17
Xb	19
Xc	29
Xd	31
Xe	37

 

Решение:

p=2q+1=1001 q=500

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

Ya = g^Xa mod р = 101¹⁷mod 1001 = 810

Yb = g^Xb mod р = 101¹⁹ mod 1001 = 556

Yc = g^Xc mod р = 101²⁹mod 1001 = 446

Yd = g^Xd mod р = 101³¹ mod 1001 = 101

Ye = g^Xe mod р = 101³⁷mod 1001 = 920

 

 

 

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

Абонент	Секретный ключ	Открытый ключ
A B C D E	17 19 29 31 37	810         556         446         101         920

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

Z_AB = (Y_B)^XAmodp = (556)¹⁷ mod 1001 = 173                                                                                             

Z_BA = (Y_A)^XBmodp = (810)¹⁹ mod 1001 = 173

Z = Zab=Zва

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

                                                                                       

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

 

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

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

i	7	8	9
Сообщение	26	28	30
j	3	3	3
p	41	41	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₃). Тогда алгоритм записывается следующим образом.

 

Обобщенный алгоритм Евклида

 

ВХОД: Положительные целые числа a, b, .

ВЫХОД:   gcd(a,b), x, y, удовлетворяющие (1).

1.  .

2.    WHILE u₁ 0 DO

3.           u₁ div v₁;

4.            T ( u₁ mod v₂, u₂-qu₂, u₃-qv₃);

5.            U V, V T.

6.    RETURN U= (gcd(a,b), x, y).

 

Результат содержится в строке U.

Операция  div в алгоритме – это целочисленное деление

a div b=[a/b].

 

Произведем расчет с_А d_A с_В d_В с_С d_С.

Дано:

Ma=26  Mb=28  Mc=30

P=41    P=41   P=41

Ca=7   Cb=11          Cc=33

 

Здесь Ма, Mb, Mc сообщения, Р простое число, Сa, Cb, Cc секретные ключи.  Вычислить Da, Db, Dc с помощью обобщенного алгоритма Евклида. Находим Da. Делается это с помощью обобщенного алгоритма Евклида, описанного выше в приложении. Для начала мы вычислим n=p-1 и Ca. Они должны быть взаимно простые. Затем пользуясь алгоритмом Евклида вычислить секретный ключ Da.

Здесь n=p-1=41-1=40  Ca=7 

 

U                    40   -      0

V   U              7  -      1

T   V   U          5   -     -5 q=5

     T    V   U    2    -      6 q=1

 T    V    1    -   -17  q=2

                                       V       0  -   -40  q=2                                     

Da=23.     

 

 

Произведем проверку, правильно  ли мы вычислили Da. Для того проверим верность следующего уравнения:

Сa*Da mod (p-1)=1  7*23 mod (40)=1

Наши расчеты оказались верны.

 

 

 

Вычислим Db, применяя описанные выше операции.

 

n=(p-1)=40  Cb=11 

U                       40   -      0

V   U                11   -      1

T   V   U             7    -     -3  q=3

     T    V  U        4    -      4   q=1

 T    V       3    -    -7     q=1

                                 T    V    1    -     11 q=1

                                        V    0    -     -40  q=3

           

   

Db=11

Произведем проверку, правильно  ли мы вычислили Db. Для того проверим верность следующего уравнения:

Сb*Db mod (p-1)=1  11*11 mod (40)=1

Наши расчеты оказались верны.

Вычислим Dc, применяя описанные выше операции.

n=(p-1)=40  Cc=33 

 

U                    40   -      0

V   U              33   -      1

T   V   U          7   -      -1  q=1

                           T   V        5   -      5    q=4