ElGamal İmza Algoritması

• H çakışma olmayan bir (collision-resistant hash function) kriptografik özet fonksiyon olsun.
• p büyük bir asal sayı olsun öyle ki ayrık logaritmaları mod p'de zor olsun.
• g < p rassal seçilen bir mod n’deki çarpımsal grubun ${\displaystyle Z_{p}^{*}}$ üreteci olsun.

Bu sistem parametreleri kullanıcılar arasında paylaşılabilir.

• Gizli anahtar olan x'i rassal olarak 1 < x < p − 1. değerini seç
• y = g ^x mod p değerini hesapla
• Açık anahtar(p, g, y).
• Özel anahtar x.

Bu adımlar imzalayan kişi tarafından bir kez yapılır.

Mesaj mi imzalamak için imzalayan kişi aşağıdaki adımları gerçekleştirir:

• Rassal bir k değeri seç öyle ki 0 < k < p − 1 ve gcd(k, p − 1) = 1.
• ${\displaystyle r\,\equiv \,g^{k}{\pmod {p}}}$ değerini hesapla
• ${\displaystyle s\,\equiv \,(H(m)-xr)k^{-1}{\pmod {p-1}}}$ değerini hesapla
• Eğer ${\displaystyle s=0}$ ise başa dön.

(r,s) ikilisi mnin dijital imzasıdır. İmzalayan kişi bu adımları her imza için tekrarlar.

Mesaj m nin imzası olan (r,s) aşağıdaki gibi doğrulanır.

• ${\displaystyle 0<r<p}$ ve ${\displaystyle 0<s<p-1}$.
• ${\displaystyle g^{H(m)}\,\equiv \,y^{r}r^{s}{\pmod {p}}.}$

Doğrulayan kişi tüm koşullar sağlandığında imzayı kabul eder sağlanmazsa reddeder.

İmzalama algoritması ile üretilen imza her zaman doğrulayan kişi tarafından kabul edilirse algoritma doğrudur.

İmza oluşturma

${\displaystyle H(m)\,\equiv \,xr+sk{\pmod {p-1}}.}$

Bundan dolayı Fermat'nın son teoreminden

${\displaystyle {\begin{aligned}g^{H(m)}&\equiv g^{xr}g^{ks}\\&\equiv (g^{x})^{r}(g^{k})^{s}\\&\equiv (y)^{r}(r)^{s}{\pmod {p}}.\\\end{aligned}}}$

Üçüncü kişi imzalayan kişinin gizli anahtarı olan x değerini bularak ya da özet fonksiyonda çakışma bularak imzaların sahtesini yapabilir. Fakat bu iki problemin de zor olduğuna inanılmaktadır. İmzalayan kişi her bir imza için farklı ve rassal bir k değeri seçmeye ve k' nın ya da k ile ilgili kısmi bilginin sızmadığından emin olmalıdır. Diğer türlü, atak yapan kişi gizli anahtar olan x değerini ortaya çıkartabilir. Eğer iki mesaj, aynı k değerleri ve aynı anahtar kullanılarak gönderiliyorsa, atak yapan kişi, x değerini hesaplayabilir. [2]

• Dijital İmza Algoritması