ign="justify"> (передостаннє рівність випливає з (2.7), а останнє виконується в силу (2.1) та (2.2)).
Доказ другого пункту затвердження засновано на припущенні, що для зловмисника, що намагається визначити m, не існує стратегії більш ефективною, ніж наступна. Спочатку він обчислює CB з (2.4), потім знаходить d B і, нарешті, обчислює Х 4=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 1, u 2, u 3), V=(v 1, v 2, v 3) і Т=(t 1, t 2, t 3). Тоді алгоритм записується таким чином.
Рішення
Нехай А хоче передати У повідомлення m=14. А вибирає р=31,
з А d A mod (р - 1)=1.
з А=11, d A=41.
Аналогічно, В вибирає параметри
з в d в mod (p - 1)=1
B=31 і d B=21.
Переходимо до протоколу Шаміра.
Крок 1. x 1=14 листопада mod 51=44.
Крок 2. х 2=44 31 mod 51=29.
ШагЗ. x 3=29 41 mod 51=5.
Крок 4. х 4=21 травня mod 51=14.
Таким чином, У отримав передане повідомлення m=14.
Нехай B хоче передати C повідомлення m=16. B вибирає р=53,
З B d B mod (р - 1)=1.
З B=5, d B=21.
Аналогічно. C вибирає параметри
З c d c mod (p - 1)=1
c=11 і d c=19.
Переходимо до протоколу Шаміра.
Крок 1. x 1=16 травня mod 53=24.
Крок 2. х 2=24 листопада mod 53=15.
ШагЗ. x 3=15 21 mod 53=47.
Крок 4. х 4=47 19 mod 53=16.
Таким чином, C отримав передане повідомлення m=16.
1. Нехай R хоче передати A повідомлення m=18. C вибирає р=57,
З R d R mod (р - 1)=1.
З R=5, d R=45.
Аналогічно. У вибирає параметри
З A d A mod (p - 1)=1
A=101 і d A=173. Переходимо до протоко?? У Шаміра.
Крок 1. x 1=18 травня mod 57=18.
Крок 2. х 2=18101 mod 57=18.
ШагЗ. x 3=18 45 mod 57=18.
Крок 4. х 4=18 173 mod 57=18.
Таким чином, A отримав ...
