ElGamal şifrelemesi: Revizyonlar arasındaki fark

[kontrol edilmemiş revizyon]

← Önceki sürümle aradaki fark Sonraki sürümle aradaki fark →

İçerik silindi İçerik eklendi

Satır içi

Sayfanın 11.46, 23 Mayıs 2012 tarihindeki hâli

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 $G$ üzerinde tanımlanabilir. Güvenliği $G$ grubunda kesikli logaritma(en:Discrete logarithm) adı verilen belli bir problemin zorluğuna dayanmaktadır (aşağıda açıklanacaktır).

Algoritma

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

Anahtar üretilmesi

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

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

Şifreleme

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

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

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

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

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

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

Güvenlik

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

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

Eğer $G$ için Kararsal Diffie–Hellman varsayımı (en:decisional Diffie–Hellman assumption) doğru ise, o halde ElGamal şifreleme fonksiyonu semantik güvenliğien:Semantic security 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ı (en:decisional Diffie–Hellman assumption).

ElGamal şifrelemesi, koşulsuz şekillenebilirlik olduğu için, seçili gizli mesaj ataklarına (en:chosen ciphertext attack) karşı dayanıksızdır. Mesela mesajı ( $m$ ) bilinmeyen bir $(c_{1},c_{2})$ gizli mesajı verildiğinde, $2m$ mesajının geçerli bir gizli mesajı olarak $(c_{1},2c_{2})$ 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ı (en:decisional Diffie–Hellman assumption) 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, $G$ için DDH varsayımı altında Cramer–Shoup kriptosistemi(en:Cramer–Shoup cryptosystem), seçili gizli mesaj ataklarına karşı dayanıklıdır. Bu sistemin güvenlik ispatı rassal kahin modelini (en:random oracle model) 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

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şifreleme için farklı bir yöntem kullanılarak $s\,$ ile bölme işleminden kaçınılabilir.

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

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

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

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

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

c_{2}\cdot s'=m'\cdot s\cdot s'=m'\cdot 1=m'

.

Ayrıca bakınız

Referanslar

^ Taher ElGamal (1985). "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" (PDF). IEEE Transactions on Information Theory. 31 (4): 469–472. doi:10.1109/TIT.1985.1057074. (conference version appeared in CRYPTO'84, pp. 10–18)
^ ^a ^b CRYPTUTOR, "Elgamal encryption scheme"
^ ^a ^b M. Abdalla, M. Bellare, P. Rogaway, "DHAES, An encryption scheme based on the Diffie–Hellman Problem" (Appendix A)

ElGamal, Taher (1985). A public key cryptosystem and a signature scheme based on discrete logarithms (PDF). Lecture Notes in Computer Science. 196. Santa Barbara, California, United States: Springer-Verlag. ss. 10–18. doi:10.1007/3-540-39568-7_2. Bilinmeyen parametre |kitapbaşlık= görmezden gelindi (yardım)
A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. "Chapter 8.4 ElGamal public-key encryption". Handbook of Applied Cryptography (PDF). CRC Press.
Dan Boneh (1998). "The Decision Diffie–Hellman Problem". Lecture Notes in Computer Science. 1423: 48–63. doi:10.1007/BFb0054851.

Bu algoritma 1984 yılında Taber ElGamal tarafindan öne sürüldü.Daha sonra farklı varyasyonlar geliştirildi.Bu varyasyonlardan bir tanesi olan DSA (Digital Signature Algorithm) 1991 yılında DSS (Digital Signature Standard) olarak kabul edilmiştir. ElGamal asimetrik bir şifreleme yöntemidir. Anahtar üretimi ve şifreleme/açma işlemlerinden oluşur. Anahtar üretiminde dairesel gruptan yararlanılır.

[1] Taher ElGamal (1985). "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" (PDF). IEEE Transactions on Information Theory. 31 (4): 469–472. doi:10.1109/TIT.1985.1057074. (conference version appeared in CRYPTO'84, pp. 10–18)

[cryptutor-2] CRYPTUTOR, "Elgamal encryption scheme"

[DHAES-3] M. Abdalla, M. Bellare, P. Rogaway, "DHAES, An encryption scheme based on the Diffie–Hellman Problem" (Appendix A)

[1]

[2]

[3]

@@ 1. satır: / 1. satır: @@
+'''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.
+<ref>{{cite journal |author=Taher ElGamal |title=A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms |journal=IEEE Transactions on Information Theory |volume=31 |issue=4 |year=1985 |pages=469–472 |doi=10.1109/TIT.1985.1057074 |url=http://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf}} (conference version appeared in [[CRYPTO]]'84, pp. 10&ndash;18)</ref>
+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 <math>G</math> üzerinde tanımlanabilir.
+Güvenliği <math>G</math> grubunda kesikli logaritma([[:en:Discrete logarithm]]) adı verilen belli bir problemin zorluğuna dayanmaktadır (aşağıda açıklanacaktır).
+== Algoritma ==
+ElGamal şifrelemesi üç bileşenden oluşur: anahtar üretici, şifreleme algoritması, ve deşifreleme algoritması.
+=== Anahtar üretilmesi ===
+Anahtar üretici şöyle çalışır:
+* Ayşe, kertesi <math>q\,</math> olan, <math>g\,</math> üretecine sahip, çarpımsal bir <math>G\,</math> döngüsel grubunun etkin bir tanımını üretir. Böyle bir grubun gereksinimleri aşağıdadır.
+* Ayşe <math>\{0, \ldots, q-1\}</math> aralığından rastgele bir <math>x\,</math> seçer.
+* Ayşe <math>h = g^x\,</math> değerini hesaplar.
+* Ayşe, '''açık anahtar''' olarak <math><G, q, g>\,</math> ve <math>h\,</math> değerlerini yayınlar. Ayşe <math>x\,</math> değerini ise '''gizli anahtar'''ı olarak kendisine saklar.
+=== Şifreleme ===
+Şifreleme algoritması şöyle çalışır: Bir <math>m\,</math> mesajını Ayşe'ye göndermek için, açık anahtar <math>(G,q,g,h)\,</math> kullanılarak,
+* Burak <math>\{0, \ldots, q-1\}</math> aralığından rastgele bir <math>y\,</math> değeri seçer, ve <math>c_1=g^y\,</math> değerini hesaplar.
+* Burak paylaşılan gizli anahtarı <math>s=h^y\,</math> şeklinde hesaplar. Her mesaj için yeni bir <math>y\,</math> değeri üretildiği için, <math>y\,</math> değerine '''geçici anahtar'''([[:en:Ephemeral key]]) 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ı <math>m\,</math>'yi <math>G\,</math> grubunun bir elemanına, <math>m'\,</math>'ye dönüştürür.
+* Burak <math>c_2=m'\cdot s</math> değerini hesaplar.
+* Burak <math>(c_1,c_2)=(g^y, m'\cdot h^y)=(g^y, m'\cdot(g^x)^y)\,</math> gizli mesajını Ayşe'ye gönderir.
+=== Deşifreleme ===
+Deşifreleme algoritması şöyle çalışır: <math>(c_1,c_2)\,</math> şeklindeki bir gizli mesajı deşifrelemek için, gizli anahtarı <math>x\,</math> ile Ayşe şunları yapar:
+* Ortak gizli anahtar <math>s=c_1^x\,</math> değerini hesaplar.
+* Daha sonra <math>m'=c_2 \cdot s^{-1}\,</math> değerini bulur ve bu değerden de <math>m\,</math> mesajını elde eder.
+Deşifreleme algoritmasından gerçekten de doğru mesaj elde edildiği şu eşitliklerle gösterilebilir:
+:<math> c_2 \cdot s^{-1} = m'\cdot h^y \cdot (g^{xy})^{-1} = m'\cdot g^{xy} \cdot g^{-xy} = m'.</math>
+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 <math>G</math> grubunun büyüklüğünden (<math>q</math>) çok daha uzun mesajlar şifrelenebilir.
+== Güvenlik ==
+ElGamal metodunun güvenliği <math>G</math> grubunun ve mesaj üzerinde kullanılan dolgulama metodunun özelliklerine dayanmaktadır.
+Eğer kullanılan döngüsel grup <math>G</math> için Hesaplamasal [[Diffie–Hellman]] varsayımı doğru ise, o halde ElGamal şifreleme fonksiyonu tek yönlüdür.
+<ref name=cryptutor>''CRYPTUTOR'', "[http://crypto.cs.uiuc.edu/wiki/index.php/Elgamal_encryption_scheme Elgamal encryption scheme]"</ref>
+Eğer <math>G</math> için Kararsal [[Diffie–Hellman]] varsayımı ([[:en:decisional Diffie–Hellman assumption]]) doğru ise, o halde ElGamal şifreleme fonksiyonu semantik güvenliği[[:en:Semantic security]] sağlar.
+<ref name=cryptutor /> Semantic security is not implied by the computational Diffie–Hellman assumption alone.
+<ref name=DHAES>M. Abdalla, M. Bellare, P. Rogaway, "DHAES, An encryption scheme based on the Diffie–Hellman Problem" (Appendix A)</ref>
+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ı]] ([[:en:decisional Diffie–Hellman assumption]]).
+ElGamal şifrelemesi, koşulsuz [[şekillenebilir|şekillenebilirlik]] olduğu için, seçili gizli mesaj ataklarına ([[:en:chosen ciphertext attack]]) karşı dayanıksızdır.
+Mesela mesajı (<math>m</math>) bilinmeyen bir <math>(c_1, c_2)</math> gizli mesajı verildiğinde, <math>2m</math> mesajının geçerli bir gizli mesajı olarak <math>(c_1, 2 c_2)</math> 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ı ([[:en:decisional Diffie–Hellman assumption]]) 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, <math>G</math> için DDH varsayımı altında [[Cramer–Shoup kriptosistemi]]([[:en:Cramer–Shoup cryptosystem]]), seçili gizli mesaj ataklarına karşı dayanıklıdır.
+Bu sistemin güvenlik ispatı [[rassal kahin modeli]]ni ([[:en:random oracle model]]) gerektirmemekte, standart modelde yapılabilmektedir.
+Önerilmiş başka bir metot olan DHAES,<ref name=DHAES /> metodunun güvenlik ispatı içinse DDH'ten daha zayıf bir varsayım yeterlidir.
+== Verimlilik ==
+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şifreleme için farklı bir yöntem kullanılarak <math>s\,</math> ile bölme işleminden kaçınılabilir.
+<math>(c_1,c_2)\,</math> şeklindeki bir gizli mesajı deşifre etmek için Ayşe gizli anahtarı <math>x\,</math> ile şunları yapar:
+* <math>s'=c_1^{{q-x}}=g^{(q-x)y}</math> değerini hesaplar.<math>s'\,</math>, <math>s\,</math>'in çarpımsal tersidir. Bu Lagrange teoremi'nin ([[:en:Lagrange's_theorem_(group_theory)]]) bir sonucudur:
+<math>s\cdot s' = g^{xy}\cdot g^{y(q-x)} = (g^q)^y = 1^y =1</math>.
+* Daha sonra <math>m'= c_2 \cdot s'</math> değerini hesaplar, ve açık mesaj <math>m\,</math>'yi elde eder.
+Deşifreleme algoritması doğru açık mesajı verir çünkü:
+:<math> c_2 \cdot s' = m' \cdot s \cdot s' = m' \cdot 1 = m'</math>.
+==Ayrıca bakınız==
+* [[ElGamal İmza Algoritması]]
+* [[Homomorfik şifreleme]]
+==Referanslar==
+<references />
+* {{cite conference
+  | first = Taher
+  | last = ElGamal
+  | başlık = A public key cryptosystem and a signature scheme based on discrete logarithms
+  | kitapbaşlık = Advances in cryptology: Proceedings of CRYPTO 84
+  | pages = 10–18
+  | volume = 196
+  | series = Lecture Notes in Computer Science
+  | publisher = Springer-Verlag
+  | date = 1985
+  | location = Santa Barbara, California, United States
+  | url = http://groups.csail.mit.edu/cis/crypto/classes/6.857/papers/elgamal.pdf
+  | doi = 10.1007/3-540-39568-7_2}}
+* {{cite book
+|author=A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone
+|publisher=CRC Press
+|url=http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf
+|başlık=Handbook of Applied Cryptography
+|chapter=Chapter 8.4 ElGamal public-key encryption}}
+* {{cite journal
+|author=[[Dan Boneh]]
+|title=The Decision Diffie–Hellman Problem
+|journal=Lecture Notes in Computer Science
+|year=1998 |volume=1423 |pages=48–63 |doi=10.1007/BFb0054851
+|url=http://crypto.stanford.edu/~dabo/abstracts/DDH.html}}
+{{DEFAULTSORT:Elgamal Şifreleme}}
+[[Category:Kriptoloji]]
+[[cs:ElGamal]]
+[[de:Elgamal-Verschlüsselungsverfahren]]
+[[es:Cifrado ElGamal]]
+[[fa:رمزنگاری الجمل]]
+[[fr:Cryptosystème de ElGamal]]
+[[it:ElGamal]]
+[[he:צופן אל-גמאל]]
+[[lt:ElGamal kriptosistema]]
+[[nl:Elgamal-encryptiesysteem]]
+[[ja:ElGamal暗号]]
+[[pl:ElGamal]]
+[[pt:El Gamal]]
+[[ru:Схема Эль-Гамаля]]
+[[fi:ElGamal]]
+[[sv:ElGamal-kryptering]]
 {{düzenle|Temmuz 2008}}
 Bu algoritma 1984 yılında Taber ElGamal tarafindan öne sürüldü.Daha sonra farklı varyasyonlar geliştirildi.Bu varyasyonlardan bir tanesi olan DSA (Digital Signature Algorithm) 1991 yılında DSS (Digital Signature Standard) olarak kabul edilmiştir.
 ElGamal asimetrik bir şifreleme yöntemidir. Anahtar üretimi ve şifreleme/açma işlemlerinden oluşur. Anahtar üretiminde dairesel gruptan yararlanılır.
-[[Kategori:Kriptoloji]]
 [[cs:ElGamal]]