Шифр Шамира

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

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

c_Ad_A mod (р- 1)=1, (3.17)

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

c_Bd_B mod (p- 1)=1, (3.18)

и держит их в секрете.

После этого А передает свое сообщение т, используя трехступенчатый протокол. Если т<р (т рассматривается как число), то сообщение т передается сразу, если же тр, то сообщение предствляется в виде m₁, m₂,... ,m_t, где все т_i<р, и затем передаются последовательно m₁, m₂,... ,m_t. При этом для кодирования каждого m_i, лучше выбирать случайно новые пары (c_A, d_A) и (c_B, d_B) — в противном случае надежность системы понижается. В настоящее время такой шифр, как правило, используется для передачи чисел, например, секретных ключей, значения которых меньше р. Таким образом, мы будем рассматривать только случай т<р. Дадим описание протокола.

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

x₁= т mod p, (3.19)

где т — исходное сообщение, и пересылает x₁ к В.

Шаг 2. В, получив x₁, вычисляет число

х₂ = mod p (3.20)

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

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

х₃ = mod p (3.21)

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

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

х₄ = mod p. (3.22)

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

1) х_а = т, т.е. в результате реализации протокола от А к В действительно передается исходное сообщение;

2) злоумышленник не может узнать, какое сообщение было передано.

Доказательство. Вначале заметим, что любое целое число е 0 может быть представлено в виде е=k (р- 1)+ r, где r = е mod (р- 1). Поэтому на основании теоремы Ферма

х^е mod р = mod p = (1 ^k·x^r) mod р = х^{е mod (p-1)} mod p. (3.23)

Справедливость первого пункта утверждения вытекает из следующей цепочки равенств:

х₄ =mod р = mod = mod p= mod p =

= mod p = mod p = m

(предпоследнее равенство следует из (2.23), а последнее выполняется в силу (3.17) и (3.18)).

Доказательство второго пункта утверждения основано на предположении, что для злоумышленника, пытающегося определить т,не существует стратегии более эффективной, чем следующая. Вначале он вычисляет c_B из (3.20), затем находит d_B и, наконец, вычисляет x4=т по (3.22). Но для осуществления этой стратегии злоумышленник должен решить задачу дискретного логарифмирования (3.20), что практически невозможно при больших р.

Опишем метод нахождения пар c_A, d_A и c_B, d_B, удовлетворяющих (3.17) и (3.18). Достаточно описать только действия для абонента А, так как действия для В совершенно аналогичны. Число c_A выбираем случайно так, чтобы оно было взаимно простым с р- 1 (поиск целесообразно вести среди нечетных чисел, так как р — 1 четно). Затем вычисляем d_A с помощью обобщенного алгоритма Евклида.

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