Задача Несимметричное шифрование дешифрование

Теорема Пусть 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 = 22. А выбирает р = 53,

с_Аd_A mod (р - 1) = 1.
с_А = 101 , d_A = 173.
Аналогично, В выбирает параметры
с_вd_в mod (p - 1) = 1
c_B = 127 и d_B = 199 . Переходим к протоколу Шамира.
Шаг 1. x₁ = 22¹⁰¹mod 53 =21.
Шаг 2. х₂ = 21¹²⁷ mod 53 = 19.
ШагЗ. x₃= 19¹⁷³ mod 53 = 32.
Шаг 4. х₄ = 32¹⁹⁹ mod 53 = 22.
Таким образом, В получил передаваемое сообщение m = 22.
Пусть B хочет передать C сообщение m = 24. B выбирает р = 57,
С_Bd_B mod (р - 1) = 1.
С_B =13, d_B = 13.
Аналогично. C выбирает параметры
С_cd_c mod (p - 1) = 1
C_c = 101 и d_c = 173. Переходим к протоколу Шамира.
Шаг 1. x₁ = 24¹³mod 57 = 36.
Шаг 2. х₂ = 36¹⁰¹ mod 57 = 42.
ШагЗ. x₃= 42¹³ mod 57 = 9.
Шаг 4. х₄ = 9¹⁷³ mod 57 =24.
Таким образом, C получил передаваемое сообщение m = 24.

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

С_Rd_R mod (р - 1) = 1.
С_R = 3, d_R = 19.
Аналогично. В выбирает параметры
С_Ad_A mod (p - 1) = 1
C_A = 3 и d_A = 47. Переходим к протоколу Шамира.
Шаг 1. x₁ = 26³mod29 = 2.
Шаг 2. х₂ = 2³ mod 29 = 8
ШагЗ. x₃= 8¹⁹ mod 29 = 2.
Шаг 4. х₄ = 2⁴⁷ mod 29 = 26.
Таким образом, A получил передаваемое сообщение m = 26.