ElGamal şifrelemesi

(ElGamal sayfasından yönlendirildi)

ElGamal şifrelemesi, Diffie-Hellman anahtar alış-verişi'ne dayanan bir asimetrik şifreleme algoritması olup Taher Elgamal tarafından 1984 yılında önerilmiştir.[1]

ElGamal, bedava bulunan GNU Privacy Guard yazılımında, PGP'nin son versiyonlarında ve başka kriptosistemlerde kullanılmaktadır.

DSA ElGamal dijital anahtar metodunun bir türevi olup, ElGamal şifrelemesi ile karıştırılmamalıdır.

ElGamal şifrelemesi herhangi bir döngüsel grup üzerinde tanımlanabilir. Güvenliği grubunda kesikli logaritma adı verilen belli bir problemin zorluğuna dayanmaktadır (aşağıda açıklanacaktır).

Algoritma

değiştir

ElGamal şifrelemesi üç bileşenden oluşur: anahtar üretici, şifreleme algoritması ve deşifreleme algoritması.

Anahtar üretilmesi

değiştir

Anahtar üretici şöyle çalışır:

  • Ayşe, kertesi   olan,   üretecine sahip, çarpımsal bir   döngüsel grubunun etkin bir tanımını üretir. Böyle bir grubun gereksinimleri aşağıdadır.
  • Ayşe   aralığından rastgele bir   seçer.
  • Ayşe   değerini hesaplar.
  • Ayşe, açık anahtar olarak   ve   değerlerini yayınlar. Ayşe   değerini ise gizli anahtarı olarak kendisine saklar.

Şifreleme

değiştir

Şifreleme algoritması şöyle çalışır: Bir   mesajını Ayşe'ye göndermek için, açık anahtar   kullanılarak,

  • Burak   aralığından rastgele bir   değeri seçer ve   değerini hesaplar.
  • Burak paylaşılan gizli anahtarı   şeklinde hesaplar. Her mesaj için yeni bir   değeri üretildiği için,   değerine geçici anahtar da denir.

Yukarıdaki adımlar şifreleme zamanından daha önce yapılabilir, çünkü bu adımlarda mesaj henüz kullanılmamıştır.

  • Burak gizli mesajı  'yi   grubunun bir elemanına,  'ye dönüştürür.
  • Burak   değerini hesaplar.
  • Burak   gizli mesajını Ayşe'ye gönderir.

Deşifreleme

değiştir

Deşifreleme algoritması şöyle çalışır:   şeklindeki bir gizli mesajı deşifrelemek için, gizli anahtarı   ile Ayşe şunları yapar:

  • Ortak gizli anahtar   değerini hesaplar.
  • Daha sonra   değerini bulur ve bu değerden de   mesajını elde eder.

Deşifreleme algoritmasından gerçekten de doğru mesaj elde edildiği şu eşitliklerle gösterilebilir:

 

ElGamal kriptosistemi genellikle bir hibrid kriptosistem içinde kullanılır. Hibrid kriptosistemlerde mesaj simetrik bir kriptosistemle şifrelendikten sonra burada kullanılan anahtar ise bir açık anahtar sistemiyle şifrelenir. Böylece kullanılan   grubunun büyüklüğünden ( ) çok daha uzun mesajlar şifrelenebilir.

Güvenlik

değiştir

ElGamal metodunun güvenliği   grubunun ve mesaj üzerinde kullanılan dolgulama metodunun özelliklerine dayanmaktadır.

Eğer kullanılan döngüsel grup   için Hesaplamasal Diffie-Hellman varsayımı doğru ise, o halde ElGamal şifreleme fonksiyonu tek yönlüdür.[2]

Eğer   için kararsal Diffie-Hellman varsayımı doğru ise, o halde ElGamal şifreleme fonksiyonu semantik güvenliği sağlar.[2] Semantic security is not implied by the computational Diffie–Hellman assumption alone.[3] Bu varsayımın doğru olduğu düşünülen gruplar hakkında daha fazla bilgi için bkz. Kararsal Diffie–Hellman Varsayımı.

ElGamal şifrelemesi, koşulsuz şekillenebilir olduğu için, seçili gizli mesaj ataklarına karşı dayanıksızdır. Mesela mesajı ( ) bilinmeyen bir   gizli mesajı verildiğinde,   mesajının geçerli bir gizli mesajı olarak   kolayca elde edilebilir.

Seçili mesaj güvenliğine ulaşmak için metodun değiştirilmesi veya uygun bir dolgulama metodu kullanılmalıdır. Yapılan değişikliğe göre kararsal Diffie-Hellman varsayımı gerekebilir veya gerekmeyebilir.

ElGamal ile ilişkili olup seçili gizli mesaj güvenliğini sağlayan başka metotlar da önerilmiştir. Örneğin,   için DDH varsayımı altında Cramer–Shoup kriptosistemi, seçili gizli mesaj ataklarına karşı dayanıklıdır. Bu sistemin güvenlik ispatı rassal kahin modelini gerektirmemekte, standart modelde yapılabilmektedir. Önerilmiş başka bir metot olan DHAES,[3] metodunun güvenlik ispatı içinse DDH'ten daha zayıf bir varsayım yeterlidir.

Verimlilik

değiştir

ElGamal şifreleme bir olasılıksal şifreleme metodudur, yani bir mesaj çok sayıda farklı gizli mesaja şifrelenebilir, dolayısıyla ElGamal şifreleme mesajdan gizli mesaj üretirken 2:1'lik bir genişleme oranına sahiptir.

ElGamal şifreleme iki üs alma işlemi gerektirir; fakat, bu üs alma işlemleri mesajdan bağımsız oldukları için önceden hesaplanabilir. Deşifreleme ise sadece bir üs alma işlemi gerektirir.

Deşifreleme

değiştir

Deşifreleme için farklı bir yöntem kullanılarak   ile bölme işleminden kaçınılabilir.

  şeklindeki bir gizli mesajı deşifre etmek için Ayşe gizli anahtarı   ile şunları yapar:

  •   değerini hesaplar. ,  'in çarpımsal tersidir. Bu Lagrange teoremi'nin bir sonucudur:

 .

  • Daha sonra   değerini hesaplar ve açık mesaj  'yi elde eder.

Deşifreleme algoritması doğru açık mesajı verir çünkü:

 .

Ayrıca bakınız

değiştir

Kaynakça

değiştir
  1. ^ Taher ElGamal (1985). "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" (PDF). IEEE Transactions on Information Theory. 31 (4). ss. 469-472. doi:10.1109/TIT.1985.1057074. 13 Ağustos 2011 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 23 Mayıs 2012.  (conference version appeared in CRYPTO'84, pp. 10–18)
  2. ^ a b CRYPTUTOR, "Elgamal encryption scheme 21 Nisan 2009 tarihinde Wayback Machine sitesinde arşivlendi."
  3. ^ a b M. Abdalla, M. Bellare, P. Rogaway, "DHAES, An encryption scheme based on the Diffie–Hellman Problem" (Appendix A)