Шифрование по алгоритму Шамира

Рисунок 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 хочет передать сообщение mB = 24. B выбирает p = 53, сB = 17 и вычисляет dB= 49. Аналогично, C выбирает параметры сC = 23 и dC=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 хочет передать сообщение mC = 26. C выбирает p = 53, сC = 23 и вычисляет dC= 43. Аналогично, A выбирает параметры сA = 11 и dA=19.

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

Шаг 1. X₁ = 26²³mod53 = 8

Шаг 2. X₂ = 8¹¹mod53 = 31

Шаг 3. X₃ = 31⁴³mod53 = 14

Шаг 4. X₄ = 14¹⁹mod53 = 26

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

Рисунок 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

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