ElGamal şifreleme sistemi

Şifreleme ElGamal veya şifreleme El Gamal (ya da El Gamal sistemi ) bir protokoldür asimetrik kriptografi ile icat Taher ElGamal 1984 ve sorununa inşa ayrık logaritma .

Bu protokol, son sürümleri kendi sürümünü bile eliptik eğriler üzerinde uygulayan ücretsiz GNU Privacy Guard tarafından kullanılır . RSA şifrelemesinin aksine , hiçbir zaman patent koruması altında olmamıştır .

Taher Elgamal'ın kurucu makalesi bir şifreleme protokolü , aynı zamanda benzerliklerine rağmen (her ikisi de ayrı logaritma sorunu üzerine inşa edilmiştir ) karıştırılmaması gereken bir dijital imza sunar . Bu makale yalnızca fırsatları ile şifreleme protokolü .

Algoritmanın açıklaması

Algoritma, Diffie-Hellman karar probleminin (DDH) zor olduğu sonlu bir döngüsel grup için tanımlanmıştır . CPA saldırılarına karşı direnç bölümünde daha kesin bilgiler verilmektedir .

Biz fark edebilir GKD bir olduğunu daha güçlü bir çalışma hipotezi bunun hiç sorun olmadığını tutan beri ayrık logaritmanın bunun dışında ayrık logaritma zordur. GKD probleminin kolay olduğu, ancak ayrık logaritmayı çözmek için etkili bir algoritmanın olmadığı gruplar da vardır .

Asimetrik bir şifreleme şeması olduğundan , şifreleme sistemi üç algoritmadan ( olasılıklı ) oluşur: GenClefs , Encrypt ve Decrypt .

Örnek için, Bob'un Alice'e bir mesaj göndermek istediğini varsayacağız . Ancak bu mesaj hassas bilgiler içeriyor, bu nedenle Bob, Alice dışında hiç kimse tarafından anlaşılır olmasını istemiyor. Böylece Bob mesajını şifreleyecek.

Asimetrik şifreleme şemaları genellikle simetrik analoglarından daha yavaş olduğundan, ElGamal şifreleme genellikle pratikte PGP spesifikasyonu gibi hibrit şifrelemenin bir parçası olarak kullanılır .

Bu şifreleme şemasına bakmanın bir yolu, Diffie-Hellman anahtar değişim protokolü ile bir paralel çizmektir . Şifreleme algoritması daha sonra şifrelenmiş bir mesaj göndererek oluşur , bir tarafından tek maske paylaşılan anahtarı altında o yana Alice hesaplanabilir, (resim ters bakınız). $c_ {1}$ ${\ displaystyle h ^ {r} = g ^ {r \ cdot x}}$ ${\ displaystyle c_ {2} = g ^ {r}}$

Anahtar oluşturma

Şifreleme şemasındaki ilk adım, bir çift anahtar üretmektir: genel anahtar ve gizli anahtar . Birincisi mesajları şifrelemek, ikincisi ise bunların şifresini çözmek için kullanılacaktır.

Alice, anahtar çiftini oluşturmak için , Diffie-Hellman karar hipotez probleminin zor olduğu q sıralı döngüsel bir grup ve bu grubun bir oluşturucusunu alarak başlayacaktır . $G$ $g$
Alice daha sonra özel anahtarı olacak bir element çekecek ve hesaplayacaktır . ${\ displaystyle {\ mathsf {sk}} \ triangleq x \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ ${\ displaystyle h = g ^ {x}}$
Son olarak, Alice genel anahtarı olarak yayınlayacak . ${\ displaystyle {\ mathsf {pk}} \ triangleq (G, q, g, h)}$

Şifreleme algoritması

Yani Bob, Alice'in genel anahtarına erişebilir . Bob , grubun bir öğesi olarak kodlanmış bir mesajı şifrelemek için rastgele bir sayı çizerek başlar ve hesaplama sırasında mesajı kapatmak için kullanır . Alice mesajı deşifre sağlamak için Bob tehlike mesajı bilgisinin bu kısmına ekleyecektir: . ${\ displaystyle {\ mathsf {pk}} = (G, q, g, h)}$ $m$ $G$ ${\ displaystyle r \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ $m$ ${\ displaystyle c_ {2} = m \ cdot h ^ {r}}$ ${\ displaystyle c_ {1} = g ^ {r}}$

Sonunda şifre şu iki parçadan oluşacak : ve Bob , Alice'e gönderir . ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle C \ in G ^ {2}}$

Şifre Çözme Algoritması

Erişim ve erişim olan Alice böylece şunları hesaplayabilir: ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle {\ mathsf {sk}} = x}$

{\ displaystyle {\ frac {c_ {2}} {{c_ {1}} ^ {x}}} = {\ frac {m \ cdot h ^ {r}} {g ^ {r \ cdot x}}} = {\ frac {m \ cdot {\ iptal {g ^ {x \ cdot r}}}} {\ iptal {g ^ {r \ cdot x}}}} = m}

Ve bu nedenle mesajı bulabilir . $m$

güvenlik

Seçilmiş Açık Metin Saldırılarıyla Yüzleşmek

Kamuya açık bilgilere bakıldığında ; Sadece öğelerinin görünür hale getirildiğini ve üslerin görünmediğini anlıyoruz (burada sırasıyla x ve s ). Gayri resmi olarak, ayrık logaritma probleminin , mesajı bulmayı mümkün kılacak gizli bilgiyi ( örneğin) bulmanın zor olduğu gerçeği olarak yorumlanabileceğini fark edebiliriz . ${\ displaystyle g ^ {x}, g ^ {s}}$ $G$ ${\ displaystyle {\ mathsf {sk}} = \ log _ {g} (h)}$

Daha doğrusu, planın anlamsal güvenliğini garanti etmeyi mümkün kılan Diffie-Hellmann (veya DDH ) karar problemidir .

Gösteri İndirgeme

Önemsiz olmayan bir olasılıkla kazanan ElGamal şifrelemesinin anlamsal güvenliğine karşı bir rakibimiz olduğunu varsayarsak ε . Daha sonra GKD'ye karşı bir rakip oluşturmak mümkün hale gelir ve bu, bu sorunun varsayılan zorluğuyla çelişir. Az önce tarif ettiğimiz bu indirim , planın güvenlik kanıtını oluşturacaktır. ${\ mathcal A}$ ${\ mathcal B}$

"Olarak bundan sonra anılacaktır bu rakibi oluşturmak için  indirgeme  " üçlü almak için varsayılır DDH  : amacı karar vermek daha sonra ya ile ihmal edilemez bir olasılık. Bunun için, yukarıda açıklanan düşmanla ElGamal şifreleme sisteminin anlamsal güvenliğiyle yüzleşen bir arayüze sahiptir. ${\ displaystyle (g ^ {a}, g ^ {b}, g ^ {c})}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle c \ in _ {R} \ mathbb {Z} _ {p}}$

Bu nedenle indirim, açık anahtarı ElGamal'a karşı düşmana gönderecektir . Karşı rakip için talebin oluşturulması zaman semantik güvenlik kriptosistemin, azaltma olarak şifrelenmiş göndermek olacaktır: için kendi seçtiği. Eğer üçlü bir DDH üçlüsü ise, yani eğer , o zaman ElGamal için açık anahtarla ilgili geçerli bir şifre olarak oluşturulacaktır . Öte yandan, üs rastgele ise, o zaman ElGamal'a karşı rakip, rastgele yanıt verme dışında, mücadelenin iki mesajını ayırt edemeyecektir. ${\ displaystyle {\ mathsf {pk}} = (G, q, g, h = g ^ {a})}$ ${\ displaystyle C = (g ^ {b}, m_ {i} \ cdot g ^ {c})}$ ${\ displaystyle i \ in \ {0,1 \}}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle C = (g ^ {b}, m_ {i} \ cdot (g ^ {a}) ^ {b}) = (g ^ {b}, m_ {i} \ cdot h ^ {b}) }$ ${\ displaystyle {\ mathsf {pk}}}$ $vs$

Rakibimiz başarılı olursa sadece "1" (GGD için meydan okuyucunun GGD üçlüsü gönderdiği gerçeğine karşılık gelir) ve "0" (GKD için rakibinin üçlü rastgele gönderdiği gerçeğine karşılık gelir) yanıtlamamız gerekir. aksi takdirde.

Analiz

Şimdi edecek sınırlamak avantaj avantajı bizim indirimden kazanma £ değerinin bizim şemalarına karşı sözde rakibin.

İki durumumuz olduğunu belirterek başlıyoruz: ya meydan okuyucumuz tarafından gönderilen meydan okuma gerçek bir DDH üçlüsü ya da tek tip olarak çizilmiş bir üçlü.

{\ displaystyle {\ begin {align} {\ textrm {Adv}} ^ {DDH} ({\ mathcal {B}}) & = | \ Pr [{\ mathcal {B}} \ - 1 \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {B}} \ to 1 \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ - i \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {A}} \ to i \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ to 0 \ mid i = 0 \ land {\ text {GG}}] \ Pr [i = 0] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {GKD} }] \ Pr [i = 1] - {\ frac {1} {2}} | \\ & = | {\ frac {1} {2}} (1- \ Pr [{\ mathcal {A}} \ 1 \ mid i = 0 \ land {\ text {DDH}}] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH}}]) - {\ frac {1} {2}} | \\ & = {\ frac {1} {2}} | - \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 0 \ land {\ text {GKD }}] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH}}] | \\ & = {\ frac {1} {2}} {\ textrm {Adv}} ^ {\ text {ElGamal}} ({\ mathcal {A}}) \\ & = {\ frac {\ varepsilon} {2}} \ end {hizalı}}}

Dolayısıyla, önemli kalan bir avantajımız var: GKD ile şifreleme sistemimiz arasında aynı güvenliği sağlamak için GKD sorununun ek bir güvenlik biti ile güvende kalması yeterlidir .

Seçilmiş şifre saldırılarıyla karşı karşıya

Seçilmiş şifreleme saldırıları gibi daha fazla güce sahip bir saldırganın bulunduğu modellerde, ElGamal şifreleme sistemi işlenebilirliği nedeniyle güvenli değildir ; aslında, mesaj için bir şifre verildiğinde , mesaj için geçerli olacak şifreyi oluşturabiliriz . ${\ displaystyle C = (c_ {1}, c_ {2})}$ $m$ ${\ displaystyle C '= (c_ {1}, 2 \ cdot c_ {2})}$ ${\ displaystyle 2 \ cdot m}$

Bu şekillendirilebilirlik ( çarpımsal bir homomorfizmdir ) öte yandan, örneğin elektronik oylama için kullanılmasını mümkün kılar .

Bununla birlikte, ElGamal şifresinin bir uzantısı olarak görülebilen Cramer-Shoup şifreleme sistemi gibi seçilmiş şifreleme saldırılarına karşı güvenliği sağlayan varyantlar vardır .

Misal

Örneğin, g = 5 oluşturucu ile grubu alabiliriz ( Uyarı : Bu güvenli bir grup değildir, bu değerler sadece basit bir örnek oluşturmak için alınmıştır). ${\ displaystyle G = (\ mathbb {Z} / 100000007 \ mathbb {Z} ^ {*}, \ times)}$

Bu nedenle olası bir genel anahtar : ve bir gizli anahtar olabilir . ${\ displaystyle {\ mathsf {pk}} = (G, 100000006,5,29487234)}$ ${\ displaystyle {\ mathsf {sk}} = 81996614}$

Şifreleme olasılıklı bir algoritma olduğundan, aynı mesaj için farklı olası çıktılar olduğunu unutmayın. Bu nedenle , 42 mesajı için olası bir şifreleme (58086963, 94768547) olabilir , ancak aynı zamanda sırasıyla 6689644 ve 83573058'e eşit r riskleri için (83036959, 79165157) olabilir .

Ancak iki rakamımız için hesaplama yaparsak , çıktıda 42 alacağız . ${\ displaystyle {\ dfrac {c_ {2}} {c_ {1} ^ {sk}}}}$

Notlar ve referanslar

(fr) Bu makale kısmen veya tamamen alınır İngilizce Vikipedi başlıklı makalesinde " ElGamal şifreleme " ( yazarların listesini görmek ) .

ElGamal 1984 .
RFC4880 , (tr) " OpenPGP Mesaj Formatı "
GnuPG 2.1 değişiklik günlüğü
Joux ve Nguyen 2003 .
Katz ve Lindell 2014 , Bölüm 10.5 The ElGamal Encryption Scheme.
Belenios, (en) " Belenios'un Özellikleri "

Ekler

Kaynakça

[ElGamal 1984] (en) Taher ElGamal, " Açık Anahtarlı Şifreleme Sistemi ve Ayrık Logaritmalara Dayalı İmza Şeması " , Crypto , Springer,1984( DOI 10.1007 / 3-540-39568-7_2 )
[Katz ve Lindell 2014] (en) Jonathan Katz ve Yehuda Lindell, Modern Kriptografiye Giriş, 2. Baskı , Boca Raton, Chapman and Hall ,2014, 583 s. ( ISBN 978-1-4665-7026-9 , çevrimiçi okuyun ) , "Bölüm 10.5 The El Gamal Encryption Scheme"
[Menezes, van Oorschot ve Vanstone 1996] (en) AJ Menezes , PC van Oorschot ve SA Vanstone , Handbook of Applied Cryptography , CRC Press,1996, 810 s. ( ISBN 978-1-4398-2191-6 , çevrimiçi okuyun [PDF] ) , "Bölüm 8.4 ElGamal açık anahtarlı şifreleme"
[Joux and Nguyen 2003] (tr) Antoine Joux ve Kim Nguyen, " Decarating Decision Diffie - Hellman in Computational Diffie - Hellman in Cryptographic Groups " , Journal of Cryptology , cilt. 16,2003, s. 239-247 ( DOI 10.1007 / s00145-003-0052-4 )