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

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

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

 

I
Сообщение
J
p

Решение:

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

 

 

⇐ Предыдущая123Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: