• 29 HAZİRAN 2020
  • Okunma Sayısı: 1159

Nidanur GENÇ - Karaelmas Kriptoloji Takımı

Zonguldak Bülent Ecevit Üniversitesi - [email protected]

 

ELGAMAL ALGORİTMASI

ElGamal şifrelemesi, Diffie-Hellman anahtar alışverişine dayanan bir asimetrik şifreleme algoritması olup Taher Elgamal tarafından 1984 yılında önerilmiştir. ElGamal GNU Privacy Guard yazılımda, PGP’nin son versiyonlarında ve başka kriptosistemlerde kullanılmaktadır. 

Algoritma

ElGamal açık anahtarlı şifreleme yöntemlerinden birisidir. Anahtar üretimi, şifreleme ve deşifreleme olarak 3 adımdan oluşur

Anahtar üretilmesi

Public ve private olarak iki anahtar oluşturulur. Anahtar üretimi aşamaları aşağıdaki şekilde sıralanır:
1. Büyük bir asal p sayısı seçilir.
2. Alıcı 0

3. Alıcı g€Zp olacak şekilde bir g değeri seçer.
4. Alıcı h=g^x değerini hesaplar
5. Alıcı, açık anahtar olarak ve h değerini yayınlar, x değerini ise gizli anahtar olarak kendisine saklar.

Şifreleme

Mesajın şifrelenmesi için alıcı tarafından üretilen açık anahtar bilgilerine ihtiyaç duyulur. Bu açık anahtar bilgileri doğrultusunda,
1. Gönderici 0

2. Gönderici m mesajını kullanarak c2=m . h^y (modp) değerini hesaplar.
3. Bu işlemler sonunda gönderici (c1,c2) gizli mesajını alıcıya gönderir.

Şifre Çözme

Alıcı, gönderilen (c1,c2) ikilisini deşifre etmek için gizli anahtarı olan x değerini kullanır.
Alıcı m= c2/c1^x (modp) işlemini yapar ve açık metine ulaşır.

Örnek: P=31 ve g=3 olarak seçilsin. Alıcı olan Nida’nın özel anahtarını(x) 7 olsun. Gönderici olan Recep ise m=13 mesajını göndermek istesin ve özel anahtarı(y) 5 olsun. Bu metni şifreleyip şifresini çözelim.

                                                          h≡3^7(mod31)≡17

                                                     c1≡3^5(mod31)≡26

                                                  c2≡13.17^5(mod31)≡28

                            mc2/c1^x (modp)≡28/26^7(mod31)≡28.26^23(mod31)≡13


Algoritmanın Avantaj ve Dezavantajları

ElGamal için diğer asimetrik şifreleme sistemlerdeki avantaj ve dezavantajlara sahip diyebiliriz. ElGamal algoritması da tıpkı diğer asimetrik şifreleme sistemlerindeki gibi anahtar sayısını azaltmada etkili olabilmektedir. Buna örnek vermek gerekirse, bir milyon kullanıcının iletişim kurduğu bir sistemde, asimetrik bir kriptosistemi kullanırsa sadece 2 milyon anahtar gerekirken simetrik bir sistemde bu sayı en az 500 milyardır.Elgamal algoritmasının en büyük dezavantajı, algoritma sırasında farklı hesaplamaların karmaşıklığı, çalışma sırasında çok fazla zaman ve hesaplama kapasitesi gerektiren büyük tuşların kullanılmasıdır.Ayrıca ElGamal mesaj boyutunu 2 katına çıkarır. Bu da büyük verilerle çalışmayı zor hale getirir yani algoritmanın sadece kısa mesaj işlemede etkili olduğu söylenebilir.Bu kripto algoritmasının bir diğer dezavantajı ise iki taraf arasındaki iletişimin bir anlamda doğrulanması gerekir ve bu asimetrik şifrelemede genel bir sorundur.Ayrık logaritma problemlerini çözmenin zorluğu nedeniyle, ElGamal kriptosistemine yapılan saldırılar azdır.

ElGamal Dijital İmza Şeması
ElGamal imza şeması ayrık logoritmanın hesaplanmasının zorluğuna dayanan bir dijital imzadır. Taher Elgamel tarafından 1984 yılında bulunmuştur. Kripto sistemi ile aynı adı taşımasına rağmen, ElGamal dijital imza şeması ElGamal şifreleme algoritmasından oldukça farklıdır. ElGamal imza algoritması pratikte az kullanılmaktadır.

İmzalama Protokolü

A kişisi bir mesaj imzalamak istiyor(m). Bu imzalama işlemi için ilk adımlar ElGamal şifreleme ile aynı şekildedir.

Büyük bir asal p ve 1

y=g^x modp değeri hesaplanır.

Açık anahtarlar (p,g,y) ve özel anahtar x ‘tir.

İmza Oluşturma

A kişisi mesajı imzalamak için;

gcd(k,p−1)=1 olacak şekilde k sayısı seçer.

r≡g^k(mod p) hesaplanır.

Son olarak s≡(m-xr)k^-1 (mod p - 1) değeri hesaplanır.

Eğer s=0 ise başa dönülür. (r,s) ikilisi m’nin dijital imzasıdır. İmzalayan kişi bu adımları her imza için tekrarlar.
 

Doğrulama

Mesaj m nin imzası olan (r,s) şu şekilde doğrulanır
0

g^h(m) ≡ y^r . r^s (mod p) doğrulayan kişi tüm koşullar sağlandığında imzayı kabul eder sağlanmazsa da reddeder.

Doğruluk

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

                                                                         v1 ≡ p^r . r^s≡ g^m≡ v2

 
Örnek: İmzalanacak verinin sayısal olarak kodlandığını düşünelim ve m=15 olsun. Recep g=7, p=71 ve x değerini 16 olarak belirlesin.
                                                                          y≡g^x≡7^16 (mod 71)≡19


Recep açık anahtar olarak (71,7,19) değerlerini yayınlar. İmza oluşturma aşamasında gcd(k,p−1)=1 kuralına uyacak şekilde rasgele k=31 sayısı seçilir.


                                                                          r≡g^k≡7^31 (mod 71)≡11


Son aşama olarak s değeri bulunur.


                                                     s≡(m−xr)k^-1 (mod p -1)≡61(15−16.11)(mod 70)≡49


Bu nedenle (m,r,s) = (15 , 11, 49) olarak bulunur. Sonrasında bu imzanın geçerliliği kontrol edilebilir.

                                                                   v1≡p^r * r^s ≡19^11 * 11^49 (mod71)≡23

                                                                       v2=g^m≡7^15(mod71)≡23

 

Burada v1≡v2 olduğundan dolayı imza geçerlidir.

Güvenlik

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

KAYNAKÇA

[1] Wikipedia contributors, ElGamal Encryption, Wikipedia, The Free Encyclopedia, viewed on 25.02.2020, http://en.wikipedia.org/wiki/ElGamal

[2]Jakić, Marijana. "ElGamal algoritam." (2015).

[3] Discrete Logarithms, The ElGamal Cryptosystem and Diffie-Hellman Key Exchange viewed on 27.02.2020, www.commonlounge.com/discussion/2be4d294aa9e44d4b67f6644cd9b5ced

[4]Wikipedia contributors, ElGamal Signature Scheme, Wikipedia, The Free Encyclopedia, viewed on 25.02.2020, http://en.wikipedia.org/wiki/ElGamal_signature_scheme

[5]Digital Signatures: ElGamal Signature Scheme and Digital Signature Algorithm viewed on 27.02.2020, www.commonlounge.com/discussion/35a1c2baa00b447f9275e8f71b02ef29

TÜM MAKALELER