передане повідомлення m=18.
Завдання 3
Шифрування за алгоритмом Ель-Гамаля
По таблиці 3, вибрати повідомлення m і секретний ключ x і провести шифрування за методом Ель-Гамаля для п'яти абонентів. Варіант завдання визначається останніми цифрами номера студентського квитка. За номером i (передостання цифра) студент вибирає повідомлення для зашифровування, по j (остання цифра) - необхідні для реалізації цього алгоритму секретний ключ x. Вихідні дані для інших чотирьох секретних ключів x вибираються циклічно за процедурою (i +1) і (j +1).
Таблиця 3. Вихідні дані для вибору повідомлень і числа х.
i01234Сообщеніе7911133j01234х4347512911
Нехай є абоненти А, В, С, D, E які хочуть передавати один одному зашифровані повідомлення, не маючи ніяких захищених каналів зв'язку. Шифр Ель - Гамаля вирішує це завдання, використовуючи, на відміну від шифру Шаміра, тільки одну пересилку повідомлення. Фактично тут використовується схема Діффі - Хеллмана, щоб сформувати загальний секретний ключ для двох абонентів, які передають одне одному повідомлення, і потім повідомлення шифрується шляхом множення його на цей ключ. Для кожного наступного повідомлення секретний ключ обчислюється заново.
Для всієї групи абонентів вибираються деякий велике просте число р і число g, такі, що різні ступені g суть різні числа по модулю р. Числа р і g передаються абонентам у відкритому вигляді (вони можуть використовуватися всіма абонентами мережі).
Нам необхідно вибрати числа p і g так, щоб вони відповідали наступним вимогам:
gq mod p 1,
де p=2q +1.
Візьмемо p=61 і g=11.
q +1=61
q=30
Перевіримо співвідношення:
30 mod 61=60 +1 - виконується.
Потім кожен абонент групи вибирає свою секретну число ci:
< Ci < р - 1
(див. таблицю 5.1), і обчислює відповідне йому відкрите число di:
i=gСi mod p (3.1)
Таблиця 5.1 - Ключі користувачів в системі Ель-Гамаля
АбонентСекретний ключОткритий ключA4350B4750C5150D2911E1150
Покажемо тепер, як A передає повідомлення m абоненту В. Будемо припускати, як і при описі шифру Шаміра, що повідомлення представлено у вигляді числа m < р.
Крок 1. A формує випадкове число до, 1 до р - 2, обчислює числа
r=gk mod p, (3.2)=mdBk mod p, (3.3)
і передає пару чисел (r, е) абоненту В.
Крок 2. В, отримавши (r, е), обчислює
m '= ЕRP - 1-cb mod р (3.4)
Затвердження (властивості шифру Ель-Гамаля):
) Абонент B отримав повідомлення, тобто m '= m;
) противник, знаючи р, g, dB, r і е, не може обчислити m.
Передамо повідомлення m=7 від A до B. Візьмемо р=61, g=11. Нехай абонент B вибрав для себе секретне число сb=47 і обчислив по (3.1) dB=50.
Абонент A вибирає випадково число k, наприклад k=23, і обчислює по (3.2), (3.3):
r=1123 mod 61=50,
е=75023 mod 61=16.
Тепер A посилає до B зашифроване повідомлення у вигляді пари чисел. B обчислює по (3.4):
'= 165061-1-47 mod 61=7.
Ми бачимо, що B зміг розшифрувати передане повідомлення. ...
