Контрольная работа по "Информатике"

 

4 интерация:

M4	11111110
H3	01000000
	10111110=19010
	1902 mod77=6410
H4	6410 = 010000002

 

5 интерация:

M5	11110000
H4	01000000
	10110000=17610
	1762 mod77=22
H5	2210 = 00010110

 

 

6 интерация:

M6	11111001
H5	00010110
	11101111=23910
	2392 mod77=6410
H6	6410 = 010000002

 

7 интерация:

M7	11110000
H6	01000000
	10110000=17610
	1762 mod77=22
H7	2210=00010110

 

8 интерация:

M8	11110110
H7	00010110
	11100000=22410
	2242 mod77=39
H8	4910 =00110001

 

9 интерация:

M9	1111 0000
H8	00110001
	11000001=19310
	1932 mod77=58
H9	5810 = 00111010

 

10 интерация:

M10	11110001
H9	00111010
	11001011=20310
	2032 mod91=14
H10	1410 = 00001110

 

 

 

 

 

Вывод:

Таким образом, исходное сообщение «Каримова» имеет хеш – код m=14

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

56

 

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

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

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

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

Последние цифры номера зачетной книжки – (17). Выбираем для  трех абонентов (сообщение, p) -  (14,51), (16,53), (18,57).

Таблица 2.3 – Исходные данные

I	0	1	2	3	4
Сообщение	12	14	16	18	20
G	0	1	2	3	4
p	29	31	37	41	43

I	5	6	7	8	9
Сообщение	22	24	26	28	30
G	5	6	7	8	9
p	47	49	51	53	57

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

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

с_А = 3, d_A = 19.

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

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

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

Шаг 1. x₁ = 26³mod 29 =2.

Шаг 2. х₂ = 2¹¹ mod 29 = 18.

ШагЗ.  x₃= 18¹⁹ mod 29 =288.

Шаг 4. х₄ = 288²³ mod 29 = 26.

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

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

С_Bd_B mod (р - 1) = 1.                                        

С_B = 13, d_B = 7.

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

С_cd_c mod (p - 1) = 1

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

Шаг 1. x₁ = 28¹³mod 31 =21.

Шаг 2. х₂ = 21⁷ mod 31 = 11.

ШагЗ.  x₃= 11⁷ mod 31 =13.

Шаг 4. х₄ = 13⁹ mod 31 =28.

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

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

С_Rd_R mod (р - 1) = 1.                                        

С_R = 7 , d_R = 31.

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

С_Ad_A mod (p - 1) = 1

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

Шаг 1. x₁ = 30⁷mod 37 =3.

Шаг 2. х₂ = 3¹⁷ mod 37 = 25.

ШагЗ.  x₃= 25³¹ mod 37 = 13.

Шаг 4. х₄ = 13⁷ mod 37 =30.

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

 

 

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

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

I	0	1	2	3	4
Сообщение	5	7	9	11	13
G	0	1	2	3	4
X	29	11	13	7	19

I	5	6	7	8	9
Сообщение	3	15	11	15	13
G	5	6	7	8	9
X	31	37	43	47	51

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

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

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

g^q mod p

1,

где p=2q+1.

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

2q+1=71  q=35

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

7³⁵ mod 61= 60

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

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

                                     1 < C_i < р – 1

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

                                                     d_i=g^Сi mod p        (3.1)

 

 

 

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

Абонент	Секретный ключ	Открытый ключ
A	43	50
B	47	50
C	51	50
D	29	11
E	11	50