Этот шифр, предложенный Шамиром (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 - схема обмена ключами в системе Шамира

Утверждение (свойства протокола Шамира):

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 с помощью обобщенного алгоритма Евклида.

Пример 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.

Контрольные вопросы

1. Дайте краткую характеристику системы шифрования по алгоритму Шамира.

2. Сколько пересылок между двумя абонентами необходимо совершить для передачи одного сообщения в данном алгоритме?

3. Какими преимуществами перед другими алгоритмами шифрования обладает система Шамира?