Шифр Ель Гамаля

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

Приклад обчислення і перевірки цифрового підпису
Маємо наступні загальні параметри:

Р = 13, А = 7.
Я підписую своє повідомлення m=1 цифровим підписом, сформованим по алгоритму Ель Гамаля. Обираю собі закритий ключ Х1=3 і формую  відкритий ключ: Y1 = 7^3 mod 13 = 5. Відкритий ключ передаю партнерам.

Потім обираю випадкове секретне число, взаємно просте з Р-1. Нехай k=7. Далі обчислюю число a = A^k mod P = 7^7 mod 13 = 6
Потім за допомоою алгоритму Евкліда знаходжу  b в рівнянні:
m = (X1 * а +k * b) mod (P-1) = 1=3*6+7*1 mod12
Рішенням  буде значення b=1.
Таким чином, пара чисел (6,1) буде цифровим підписом повідомлення  m=1.

При бажанні інший партнер може перевірити цифровий підпис в повідомленні: він отримує мій відкритий ключ та обчислює  с1 і с2 і порівнює їх.
с1=Y1^a * a^b mod P=5^6 * 6^8 mod 13=10,

c2= A^m mod P= 7^2mod 13= 10
Якщо с1 = с2, то цифровий підпис в повідомленні m=1 вірний.