ElGamal elektron raqamli imzo algoritmi

1985 yilda Taher ElGamal taklif qilgan imzo sxemasi — DSA va GOST R 34.10-94 ning asosi. Xavfsizligi diskret logarifm masalasiga tayanadi.

Algoritm

Katta tub son p tanlanadi (xabarning o'nlik ko'rinishi M < p, aks holda bloklarga ajratiladi).
Tasodifiy g < p tanlanadi.
Yopiq kalit x < p; ochiq kalit y = g^x mod p.
Imzo: p−1 bilan o'zaro tub tasodifiy k tanlanadi; a = g^k mod p; b = (M − a·x)·k⁻¹ mod (p−1). (a, b) — imzo.
Tekshirish: y^a·a^b ≡ g^M (mod p) bo'lsa, imzo to'g'ri.

💡 Nega tekshirish ishlaydi?

b ning ta'rifidan k·b ≡ M − a·x (mod p−1), ya'ni M ≡ a·x + k·b. Demak g^M = g^ax·g^kb = (g^x)^a·(g^k)^b = y^a·a^b.

Mashq 1: p = 83, g = 3, x = 7, k = 9, M = 12 → a = 3⁹ mod 83 = 12, b = (12 − 12·7)·9⁻¹ mod 82 = 74 → (a, b) = (12, 74).