Алгоритм електронного цифрового підпису Ель Гамаля (EGSA)

Надійний та зручний для реалізації на персональних комп’ютерах алгоритм цифрового підпису був розроблений у 1984 році американцем арабського походження Тахером Ель Гамалем. У 1991 році Національний інститут стандартів (НІСТ) США обґрунтував перед комісією Конгресу США вибір цього алгоритму як бази для відповідного національного стандарту. Найменування EGSA має походження від слів El Gamal Signature Algorithm (алгоритм цифрового підпису Ель Гамаля).

Ідея EGSA базується на тому, що для практичної неможливості фальсифікації ЕЦП може бути використана практично нерозв’язувана задача дискретного логарифмування.

Послідовно розглянемо алгоритм електронного цифрового підпису Ель Гамаля.

1). Відправник, який має підписати свій документ, вибирає деяке велике просте ціле число P. Це число є відкритим і передається усім отримувачам документів відправника. Реальні значення близькі до 2¹⁰²⁴ (» 10³⁰⁸).

Приклад. Відправник вибирає число P = 11.

2). Відправник вибирає також велике ціле число G, яке має задовольняти умовам 1 < G < P. Це число також є відкритим і передається усім отримувачам документів відправника. Реальні значення близькі до 2⁵¹² (» 10¹⁵⁴).

Приклад. Відправник вибирає число G = 2.

3). Відправник вибирає ціле число X, яке має задовольняти умовам 1 < X < P. Це число є секретним ключем відправника для підписування документів.

Приклад. Відправник вибирає секретний ключ X = 8.

4). Відправник обчислює число Y = G^X mod P. Це число є відкритим ключем відправника, яке використовується отримувачами для перевірки його підпису. Це число також передається усім отримувачам документів відправника.

Приклад. Відправник обчислює число Y = G^X mod P = 2⁸ mod 11 = 3.

5). Відправник обчислює хеш-значення H свого документу M. Кількість біт хеш-значення має бути на одиницю меншою кількості біт значення P – 1. У загальному випадку хеш-значення H документу M відправника має задовольняти умовам 1 < H < (P – 1).

Приклад. Відправник обчислює хеш-значення H свого документу M і отримує H = 5. Згадані умови стосовно кількості біт виконуються. Дійсно, значення H = 5 має 3 біта, а значення P – 1 = 10 має 4 біта.

6). Відправник вибирає випадкове ціле число K, яке має задовольняти умовам 1 < K < (P – 1). Крім того, числа K і P – 1 мають бути взаємно простими, тобто їх найбільший спільний дільник НСД(K, P – 1) = 1. Це число також є секретним числом відправника для підписування його документу M.

Приклад. Відправник вибирає випадкове ціле число K = 9.

7). Відправник обчислює ціле число a = G^K mod P. Це число є першою складовою електронного цифрового підпису його документу.

Приклад. Відправник обчислює число a = G^K mod P = 2⁹ mod 11 = 6.

8). Відправник знаходить ціле число b, використовуючи рівняння H = (X∙a + K∙b) mod (P – 1). Це число є другою складовою електронного цифрового підпису його документу.

Приклад. Відправник знаходить ціле число b із рівняння H = (X∙a + K∙b) mod (P – 1) або 5 = (8∙6 + 9∙b) mod 10. Це число можна знайти шляхом послідовного перебору:

b = 1; (8∙6 + 9∙1) mod 10 = 7;

b = 2; (8∙6 + 9∙2) mod 10 = 6;

b = 3; (8∙6 + 9∙3) mod 10 = 5.

Отримуємо b = 3.

9). Відправник передає отримувачу документ M, а також його електронний цифровий підпис у вигляді пари чисел S = (a, b).

Приклад. Відправник передає отримувачу документ M, а також його електронний цифровий підпис у вигляді пари чисел S = (6, 3).

Отримавши документ M, а також його електронний цифровий підпис S = (a, b), отримувач повинен перевірити, чи відповідає цей підпис документу.

1). Отримувач обчислює хеш-значення H отриманого документу M.

Приклад. Отримувач обчислює хеш-значення H документу M і отримує H = 5.

2). Отримувач обчислює ціле число A₁ = (Y^a ∙a^b) mod P.

Приклад. Отримувач обчислює ціле число A₁ = (Y^a ∙a^b) mod P = (3⁶ ∙6³) mod 11 = 10.

3). Отримувач обчислює ціле число A₂ = G^H mod P.

Приклад. Отримувач обчислює ціле число A₂ = G^H mod P = 2⁵ mod 11 = 10.

4). Отримувач порівнює знайдені числа A₁ і A₂. Ці числа будуть рівні тоді і тільки тоді, коли електронний цифровий підпис відповідає документу, тобто відправником документу M є дійсно власник секретного ключа X, і що відправник підписав саме цей документ M.

Приклад. ЕЦП S = (6, 3) відповідає отриманому документу M.

Використання алгоритму електронного цифрового підпису Ель Гамаля вимагає вибору щоразу іншого випадкового цілого числа K. Інакше, якщо зловмисник розкриє повторно використовуване відправником число K, то він зможе розкрити і його секретний ключ X.

Дата добавления: 2014-01-11