Числа р, g, h є публічним ключем.

Число а є приватним ключем.

Шифрування. Шифрувати можна числа 0 < т < р. Виконують такі кроки:

Дешифрування: т = D(C) = с2* (с1a)-1(mod p).

Конструкція алгоритму дешифрування ґрунтується на рівності

с2* (с1a)-1 =m*hr*(hr)-1(mod p).

Приклад 3.16. Нехай р = 29, g = 2, а = 5. Обчислюємо h = 25 mod 29 = 3. Утворимо ключі: 29, 2, 3 - публічний, 5 - приватний.

Хочемо переслати повідомлення m = 11. Виберемо r= 8 і обчислимо с1=2*mod 29 = 24 та с2 = (11- 38)mod 29 = 13.

Отримано криптотекст С = (24, 19). Щоб розшифрувати повідомлення, викорис-таємо таємний ключ а = 5:

D(C) = 19- (245)-1 mod 29 = 11.

Задача розкриття системи Ель-Гамаля зводиться до задачі знаходження дискретного логарифма за модулем р. У разі побудови криптографічної системи необхідно ви-лучати ті випадки, коли дискретне логарифмування можна легко виконати. Відомо, якщо число р - 1 має лише невеликі прості дільники, то дискретне логарифмування можна виконати ефективно за допомогою алгоритму Сільвера-Поліга-Хелмана. Тому число р необхідно вибирати так, щоб р - 1 мало лише великі прості дільники.

Криптосистеми на основі еліптичних кривих

З обчислювального погляду розглянута вище криптосистема Ель-Гамаля ґрунтується на складності вирішення проблеми логарифмування в множині (кільці) цілих чи-сел Zp за простим модулем р. Проте кільця вигляду Zp за простим модулем р не є єди-ними алгебричними структурами, у яких можна розглядати задачу обчислення дискретного логарифма.

Іншими алгебричними структурами такого типу є еліптичні криві. У 1985 р. Н.Кобліц і Х.Міллер незалежно один від одного запропонували використовувати ці структури для побудови криптографічних систем.

З огляду на традицію у випадку еліптичних кривих говорять не про множення елементів, а про їхнє додавання. У цьому разі використовують знак "+" (додавання) замість знака "*" (множення). Замість того, щоб говорити про піднесення до к-го сте-пеня, у випадку еліптичних кривих говорять про k-не кратне.

Еліптична крива над множиною (полем) дійсних чисел - це множина точок (х, у), що задовольняють рівняння

у2 = x3 + ах + b,

де 4а3 + 27b2 відмінне від нуля. Крім того, уводять у розгляд додаткову точку О, що лежить у нескінченності. Наведене вище рівняння описує криву на площині, вигляд якої залежить від значень параметрів а та b. Умова 4а3 + 27b2 0 гарантує, що рівняння кри-вої не має кратних нулів, вилучаючи з розгляду певні специфічні ситуації.

На множині описаних точок задають операцію додавання, що має просту геомет-ричну інтерпретацію. Для отримання суми двох точок необхідно провести через них пряму. Ця пряма перетинає еліптичну криву в додатковій третій точці. Третя точка і є результатом додавання перших двох.

Описана операція додавання робить множину точок еліптичної кривої абелевою групою, нейтральним елементом якої є точка О.

Дійсні числа, які є координатами точок еліптичної кривої, можна замінити на елементи з інших алгебричних структур, наприклад, на елементи множини (кільця) Zp. У цьому разі всі операції, які розглядають далі під час означення еліптичної кривої над кільцем Zp, виконують у Zp.

Нехай р > 3 - просте число, і нехай а та b - такі елементи кільця Zp, що 4а3+ 27b2 0. Еліптичною кривою Е над кільцем Zp називають множину розв'язків (х,у) рівняння

у2 =x3 + ах + b

разом з додатковою точкою в нескінченності О.

Задамо бінарну операцію на множині Е з використанням адитивного запису так:

0 + 0 = 0;

для довільних елементів x, у з множини Е:

(х, у) + О= (х, у);

для довільних елементів х1, у1 з множини Е (у1 0):

(x1,y1)+ (x1,y1)=2-2x1, (x1-x2)-y1), =(3x12+a)(2y1)-1;

для елементів x1,y1,x2,y2 з множини Е(x1x2)

(x1,y1)+ (x1,y1)=(x3,y3), x3=2-x1-x2, y3= (x1-x3)-y1, =(y2-y1)(x2-x1)-1;

Множина точок еліптичної кривої Е із заданою таким способом операцією утво-рює абелеву групу.

Зазначимо, що аналогічно можна означити еліптичні криві над скінченими по-лями характеристики 2.

Користуючись операцією додавання точок на кривій, природним способом визна-чають операцію множення точки кривої на довільне ціле число n:

пР = Р + Р + Р+...+Р, Р є Е,

де додавання виконують и разів.

Збудована функція пР є односторонньою функцією, на підставі якої можна ство-рити криптографічну систему. Зазначимо, що для обчислення за оптимальним алгорит-мом функції пР потрібно не більше, ніж 2 log2 n операцій додавання. Опишемо крипто-графічний протокол формування ключа, аналогічний до відомого протоколу Діффі-Хелмана.

Для налагодження захищеного зв'язку два користувачі А і В спільно вибирають еліптичну криву Е і точку Р на ній. Кожний із користувачів вибирає своє секретне ціле число. Нехай це будуть числа а і b, відповідно. Сторона А обчислює вираз аР, а сторона В - вираз bР. Сторони обмінюються обчисленими значеннями. У цьому разі параметри самої кривої, координати точки на ній і значення добутків аР, bР є загальнодоступними і можуть бути передані по відкритих лініях зв'язку. Користувач А множить отримане значення на а, а, відповідно, користувач В множить отримане значення на b. У результа-ті обидві сторони мають одне й те саме значення: а(bР) = b{аР) - аbР (координати точ-ки аbР). Отримане значення аbР є секретним і може бути використане для формування ключа шифрування. Зловмиснику для відтворення ключа необхідно розв'язати