ElGamal

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

• Ayşe, kertesi ${\displaystyle q\,}$ olan, ${\displaystyle g\,}$ üretecine sahip, çarpımsal bir ${\displaystyle G\,}$ döngüsel grubunun etkin bir tanımını üretir. Böyle bir grubun gereksinimleri aşağıdadır.
• Ayşe ${\displaystyle \{0,\ldots ,q-1\}}$ aralığından rastgele bir ${\displaystyle x\,}$ seçer.
• Ayşe ${\displaystyle h=g^{x}\,}$ değerini hesaplar.
• Ayşe, açık anahtar olarak ${\displaystyle <G,q,g>\,}$ ve ${\displaystyle h\,}$ değerlerini yayınlar. Ayşe ${\displaystyle x\,}$ değerini ise gizli anahtarı olarak kendisine saklar.

Şifreleme algoritması şöyle çalışır: Bir ${\displaystyle m\,}$ mesajını Ayşe'ye göndermek için, açık anahtar ${\displaystyle (G,q,g,h)\,}$ kullanılarak,

• Burak ${\displaystyle \{0,\ldots ,q-1\}}$ aralığından rastgele bir ${\displaystyle y\,}$ değeri seçer, ve ${\displaystyle c_{1}=g^{y}\,}$ değerini hesaplar.
• Burak paylaşılan gizli anahtarı ${\displaystyle s=h^{y}\,}$ şeklinde hesaplar. Her mesaj için yeni bir ${\displaystyle y\,}$ değeri üretildiği için, ${\displaystyle y\,}$ 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ı ${\displaystyle m\,}$'yi ${\displaystyle G\,}$ grubunun bir elemanına, ${\displaystyle m'\,}$'ye dönüştürür.
• Burak ${\displaystyle c_{2}=m'\cdot s}$ değerini hesaplar.
• Burak ${\displaystyle (c_{1},c_{2})=(g^{y},m'\cdot h^{y})=(g^{y},m'\cdot (g^{x})^{y})\,}$ gizli mesajını Ayşe'ye gönderir.

Deşifreleme algoritması şöyle çalışır: ${\displaystyle (c_{1},c_{2})\,}$ şeklindeki bir gizli mesajı deşifrelemek için, gizli anahtarı ${\displaystyle x\,}$ ile Ayşe şunları yapar:

• Ortak gizli anahtar ${\displaystyle s=c_{1}^{x}\,}$ değerini hesaplar.
• Daha sonra ${\displaystyle m'=c_{2}\cdot s^{-1}\,}$ değerini bulur ve bu değerden de ${\displaystyle m\,}$ mesajını elde eder.

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

${\displaystyle c_{2}\cdot s^{-1}=m'\cdot h^{y}\cdot (g^{xy})^{-1}=m'\cdot g^{xy}\cdot g^{-xy}=m'.}$

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 ${\displaystyle G}$ grubunun büyüklüğünden (${\displaystyle q}$) çok daha uzun mesajlar şifrelenebilir.

Deşifreleme için farklı bir yöntem kullanılarak ${\displaystyle s\,}$ ile bölme işleminden kaçınılabilir.

${\displaystyle (c_{1},c_{2})\,}$ şeklindeki bir gizli mesajı deşifre etmek için Ayşe gizli anahtarı ${\displaystyle x\,}$ ile şunları yapar:

• ${\displaystyle s'=c_{1}^{q-x}=g^{(q-x)y}}$ değerini hesaplar.${\displaystyle s'\,}$, ${\displaystyle s\,}$'in çarpımsal tersidir. Bu Lagrange teoremi'nin bir sonucudur:

${\displaystyle s\cdot s'=g^{xy}\cdot g^{y(q-x)}=(g^{q})^{y}=1^{y}=1}$.

• Daha sonra ${\displaystyle m'=c_{2}\cdot s'}$ değerini hesaplar, ve açık mesaj ${\displaystyle m\,}$'yi elde eder.

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

${\displaystyle c_{2}\cdot s'=m'\cdot s\cdot s'=m'\cdot 1=m'}$.