Z CA=(YA) XC modp=(128) 11 mod 30803=17068
Z=Zab=Zва
Таким чином, будь-яка пара абонентів може обчислити свій секретний ключ, який у нашому прикладі є Z.
Завдання 2. Шифрування за алгоритмом Шаміра
Зашифрувати повідомлення за алгоритмом Шаміра для трьох абонентів, взявши значення повідомлення m і значення p з таблиці 2. За номером i (передостання цифра) студент вибирає повідомлення для зашифровування, по j - необхідні для реалізації цього алгоритму число р. Вибір даних для інших абонентів призвести циклічно згідно з процедурою (i + 1) і (g + 1).
Останні цифри номера залікової книжки - (00). Вибираємо для трьох абонентів (повідомлення, p) - (12,29), (14,31), (16,37).
Таблиця 2. Вихідні дані для вибору повідомлень (m)
I012Сообщеніе141618J012p 313741
Перейдемо до опису системи. Нехай є два абонента А і В, з'єднані лінією зв'язку. А хоче передати повідомлення m абоненту Б так, щоб ніхто не дізнався його зміст. А вибирає випадкове велике просте число р і відкрито передає його В. Потім А вибирає два числа з А і d A, такі, що
з А d A mod (р - 1)=1. (2.1)
Ці числа А тримає в секреті і передавати не буде. У теж вибирає два числа з в d в, такі, що
з в
і тримає їх у секреті.
Після цього А передає своє повідомлення m, використовуючи триступеневий протокол. Якщо m < р (m розглядається як число), то повідомлення т передається відразу, якщо ж т р, то повідомлення представляється у вигляді m1, m2, ..., mt, де всі mi < р, і потім передаються послідовно m1, m2, ..., mt. При цьому для кодування кожного mi краще вибирати випадково нові пари (cA, dA) і (cB, dB) - в іншому випадку надійність системи знижується. В даний час такий шифр, як правило, використовується для передачі чисел, наприклад, секретних ключів, значення яких менше р. Таким чином, ми будемо розглядати тільки випадок m < р.
Опис протоколу.
Крок 1. А обчислює число:
Х1=mСА modp (2.3),
де m - вихідне повідомлення, і пересилає х1 до В.
Крок 2. В, отримавши х1, обчислює число:
X2=х1CB mod p (2.4),
і передає х 2 до А.
Крок 3. А обчислює число:
X 3=х 2 dA mod p (2.5),
і передає його В.
Крок 4. В, отримавши х 3, обчислює число
X 4=x 3 dB mod p (2.6).
Затвердження (властивості протоколу Шаміра).
) х 4=m, тобто в результаті реалізації протоколу від А до В дійсно передається вихідне повідомлення;
) зловмисник не може, дізнатися, яке повідомлення було передано.
Доказ. Спочатку зауважимо, що будь-яке ціле число е 0 може бути представлено у вигляді
е=k (р - 1) + r, де r=е mod (p - 1)
Тому на підставі теореми Ферма:
(2.7).
Справедливість першого пункту твердження випливає з наступної ланцюжка рівності:
