Методические указания к заданию №2.2

Этот шифр, предложенный Шамиром (Adi Shamir), был первым, позволяющим организовать обмен секретными сообщениями по от­крытой линии связи для лиц, которые не имеют никаких защищен­ных каналов и секретных ключей и, возможно, никогда не видели друг друга. (Напомним, что система Диффи-Хеллмана позволяет сформировать только секретное слово, а передача сообщения потре­бует использования некоторого шифра, где это слово будет исполь­зоваться как ключ.)

Перейдем к описанию системы. Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение m абоненту B так, чтобы никто не узнал его содержание. А выбирает случай­ное большое простое число р и открыто передает его В. Затем А выбирает два числа с_{А и} d_A, такие, что

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

Эти числа А держит в секрете и передавать не будет. В тоже вы­бирает два секретных числа с_в и d_в, такие, что

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

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

х₂ = х₁^CB mod p (2.4)

и передает х₂ к А.

Шаг 3. А вычисляет число

х₃ = х₂^dA mod p (2.5)

и передает его В.

Шаг 4. В, получив х₃, вычисляет число

х₄ = x₃^dB mod p (2.6)

Схема обмена ключами по алгоритму Шамира представлена на рисунке 2.

Рисунок 2 - схема обмена ключами в системе Шамира

Пример 2.1. Пусть А хочет передать В сообщение m = 10. А выбирает р = 23, с_А = 7 (gcd(7,22) = 1) и вычисляет d_A = 19. Аналогично, В выбирает параметры c_B = 5 (взаимно простое с 22) и d_B = 9. Переходим к протоколу Шамира.

Шаг 1. x₁ = 10⁷ mod 23 = 14.

Шаг 2. х₂ = 14⁵ mod 23 = 15.

ШагЗ. x₃= 15¹⁹ mod 23 = 19.

Шаг 4. х₄ = 19⁹ mod 23 = 10.

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

Дата добавления: 2014-01-05