ElGamal İmza Algoritması

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

ElGamal imza şeması Ayrık Logaritmanın hesaplanmasının zorluğuna dayanan bir dijital imzadır. Taher Elgamal tarafından 1984 yılında bulunmuştur. Açık anahtarlı kriptosistemi ve imza şeması ayrık logaritmaya dayanmaktadır.

ElGamal imza algoritması pratikte nadir kullanılır. NSA tarafından geliştirilen varyantı Dijital İmza Algoritması daha çok kullanılmaktadır. Bunun dışında başka varyantlar da vardır.ElGamal imza şeması yine Taher ElGamal tarafından bulunan ElGamal şifreleme algoritması ile karıştırılmamalıdır.

ElGamal imza şeması üçüncü şahısların güvensiz bir hattan gönderilen mesajın doğruluğunu onaylamasına izin verir.

Sistem Parametreleri[değiştir | kaynağı değiştir]

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

Anahtar Oluşturma[değiştir | kaynağı değiştir]

  • 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(pgy).
  • Özel anahtar x.

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

İmza Oluşturma[değiştir | kaynağı değiştir]

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

  • Rassal bir k değeri seç öyleki 0 < k < p − 1 ve gcd(kp − 1) = 1.
  •  r \, \equiv \, g^k \pmod p değerini hesapla
  •  s \, \equiv \, (H(m)-x r)k^{-1} \pmod{p-1} değerini hesapla
  • Eğer 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.

Doğrulama[değiştir | kaynağı değiştir]

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

  • 0<r<p ve 0<s<p-1.
  •  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.

Doğruluk[değiştir | kaynağı değiştir]

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

İmza oluşturma

 H(m) \, \equiv \, x r + s k \pmod{p-1}.

Bundan dolayı Fermat'nın son teoreminden


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

Güvenlik[değiştir | kaynağı değiştir]

Üçü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.

Ayrıca bakınız[değiştir | kaynağı değiştir]