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

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