Алгоритм Ель-Гамаля (EGSA)

Спочатку вибирають два великі цілі числа P, G, де Р – просте, G < P, порядку 10³⁰⁸(або 2¹⁰²⁴) для Р та 10¹⁵⁴ (або 2⁵¹²) для G, які вважаються несекретними. На основі випадкового числа Х, де 1 < X < Р – 1, обчислюємо Y за формулою:

Y = G^X mod P.

Це число Y відкрито передається потенційним адресатам для перевірки підпису відправника, який має Х як секретний ключ.

Формування ЕЦП для файла М здійснюється шляхом обчислення значення h(M), m = h(M), для хеш-функції h( ), побудованої за алгоритмом SHA. Потім відправник обчислює:

1) число "а" за формулою: а = G^K (mod P),

2) генерує випадкове число К, 1 < K < P – 1, яке є взаємно простим із числом Р – 1 ;

3) знаходить "b" із рівня m = (X ∙ a + K ∙ b) ∙ (mod (P – 1) за допомогою розширеного алгоритму Евкліда.

Пара чисел (a, b) є цифровим підписом S під файлом М. Отримувач приймає підписаний файл як трійку (М, a, b) та перевіряє відповідність ЕЦП. Для цього хешує М тією ж функцією та отримує m = h (M).

Потім він обчислює А за формулою: А = Y^A ∙ a^B (mod P).

Якщо має місце рівність А = G^m (mod P), то повідомлення M та ЕЦП під ним уважають істинним.

Приклад:

Нехай Р = 11, G = 2, X = 8. Знайдемо Y, де Y = G^X mod P = 28 mod 11 = 3.

Нехай файл М має хеш-значення 5, тобто m = 5, та К = 9. Упевнимося у взаємній простоті К та Р – 1, а потім обчислюємо "а", де

а = G^K (mod P) = 29 mod 11 = 5.

Число b знаходимо із наступного "рівняння" 5 = (6 * 8 + 9 * 6) * (mod 10), яке розв`яжемо розширеним алгоритмом Евкліда. Матимемо b = 3.

Далі передаємо підписаний файл М як трійку (М, 6, 3). Отримувач, знаючи про Y = 3 тa маючи ту ж саму хеш-функцію, обчислює для М число h(M) = m = 5. Потім обчислює два числа:

Y^A ∙ a^B (mod P) = 3⁶ ∙ 6³ (mod 11) = 10,

G^m (mod P) = 2⁵ (mod 11) = 10,

та впевнюється в істинності підпису під файлом М.

Схема цифрового підпису Ель Гамаля має низку переваг порівняно зі схемою RSA:

1. При заданому рівні стійкості алгоритму цифрового підпису цілі числа, що беруть участь у розрахунках, мають запис на 25 % коротше, що зменшує складність обчислень майже в 2 рази і дозволяє значно скоротити обсяг використовуваної пам'яті.

2. При виборі модуля Р достатньо перевірити, що це число є простим, і що у числа (Р – 1) є великий простий множник.

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Алгоритми електронного цифрового підпису (ЕЦП)	\|	Хід роботи

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.