Cramer – Shoup şifreleme sistemi - Cramer–Shoup cryptosystem - Wikipedia

Cramer – Shoup sistemi asimetrik bir anahtar şifreleme algoritmasıdır ve standart kriptografik varsayımlar kullanılarak uyarlanabilir seçilmiş şifreli metin saldırısına karşı güvenli olduğu kanıtlanmış ilk verimli şemadır. Güvenliği, karar verici Diffie-Hellman varsayımının hesaplama inatçılığına (yaygın olarak varsayılır, ancak kanıtlanamaz) dayanır. Ronald Cramer ve Victor Shoup tarafından 1998 yılında geliştirilen ElGamal şifreleme sisteminin bir uzantısıdır. Son derece esnek olan ElGamal'ın aksine, Cramer – Shoup becerikli bir saldırgana karşı bile biçimlendirilmemeyi sağlamak için başka öğeler ekler. Bu biçimlendirilemezlik, evrensel bir tek yönlü hash fonksiyonu ve ek hesaplamalar kullanılarak elde edilir ve ElGamal'dakinden iki kat daha büyük bir şifreli metin ile sonuçlanır.

Uyarlanabilir seçilmiş şifreli metin saldırıları

Cramer-Shoup tarafından ulaşılan güvenlik tanımı resmi olarak "ayırt edilemezlik altında uyarlanabilir seçilmiş şifreli metin saldırısı "(IND-CCA2). Bu güvenlik tanımı şu anda bir açık anahtar şifreleme sistemi için bilinen en güçlü tanımdır: saldırganın bir şifre çözme oracle planın gizli şifre çözme anahtarını kullanarak herhangi bir şifreli metnin şifresini çözecektir. Güvenlik tanımının "uyarlanabilir" bileşeni, saldırganın bu şifre çözme oracle'ına saldırmak için belirli bir hedef şifre metnini gözlemlemesinden önce ve sonra erişebileceği anlamına gelir (ancak bu hedef şifreli metnin şifresini çözmek için oracle'ı kullanması yasaktır). Uyarlanabilir olmayan seçilmiş şifreli metin saldırılarına (IND-CCA1) karşı daha zayıf güvenlik kavramı, saldırganın yalnızca hedef şifreli metni gözlemlemeden önce şifre çözme oracle'ına erişmesine izin verir.

Yaygın olarak kullanılan birçok şifreleme sisteminin böyle bir saldırgana karşı güvensiz olduğu iyi bilinmesine rağmen, uzun yıllar sistem tasarımcıları saldırının pratik olmadığını ve büyük ölçüde teorik olarak ilgisini çekti. Bu, 1990'ların sonlarında, özellikle Daniel Bleichenbacher karşı pratik bir uyarlanabilir seçilmiş şifreli metin saldırısı gösterdi SSL bir biçim kullanan sunucular RSA şifreleme.^[1]

Cramer – Shoup, uyarlanabilir seçilmiş şifreli metin saldırısına karşı güvenlik sağlayan ilk şifreleme şeması değildi. Naor – Yung, Rackoff – Simon ve Dolev – Dwork – Naor, standart (IND-CPA) şemalardan IND-CCA1 ve IND-CCA2 şemalarına kesin olarak güvenli dönüşümler önerdi. Bu teknikler, standart bir kriptografik varsayımlar dizisi altında güvenlidir (rastgele oracle'lar olmadan), ancak karmaşık sıfır bilgi kanıtı teknikleri ve hesaplama maliyeti ve şifreli metin boyutu açısından verimsizdir. Dahil olmak üzere çeşitli diğer yaklaşımlar Bellare /Rogaway 's OAEP ve Fujisaki – Okamoto olarak bilinen matematiksel bir soyutlamayı kullanarak verimli yapılar elde edin rastgele oracle. Ne yazık ki, bu şemaları pratikte uygulamak için bazı pratik işlevlerin (örn. kriptografik karma işlevi ) rastgele oracle yerine. Giderek artan sayıda kanıt, bu yaklaşımın güvensizliğini gösteriyor.^[2] konuşlandırılan planlara karşı hiçbir pratik saldırı gösterilmemiş olmasına rağmen.

Şifreleme sistemi

Cramer – Shoup üç algoritmadan oluşur: anahtar oluşturucu, şifreleme algoritması ve şifre çözme algoritması.

Anahtar oluşturma

• Alice verimli bir tanım oluşturur döngüsel grup ${ displaystyle G}$ düzenin ${ displaystyle q}$ iki farklı, rastgele jeneratörler ${ displaystyle g_ {1}, g_ {2}}$.
• Alice beş rastgele değer seçer ${ displaystyle ({x} _ {1}, {x} _ {2}, {y} _ {1}, {y} _ {2}, z)}$ itibaren ${ displaystyle {0, ldots, q-1 }}$.
• Alice hesaplar ${ displaystyle c = {g} _ {1} ^ {x_ {1}} g_ {2} ^ {x_ {2}}, d = {g} _ {1} ^ {y_ {1}} g_ {2 } ^ {y_ {2}}, h = {g} _ {1} ^ {z}}$.
• Alice yayınlar ${ displaystyle (c, d, h)}$açıklamasıyla birlikte ${ displaystyle G, q, g_ {1}, g_ {2}}$onun gibi Genel anahtar. Alice korur ${ displaystyle (x_ {1}, x_ {2}, y_ {1}, y_ {2}, z)}$ onun gibi gizli anahtar. Grup, sistem kullanıcıları arasında paylaşılabilir.

Şifreleme

Bir mesajı şifrelemek için ${ displaystyle m}$ Alice'e açık anahtarı altında ${ displaystyle (G, q, g_ {1}, g_ {2}, c, d, h)}$,

• Bob dönüştürür ${ displaystyle m}$ elemanına ${ displaystyle G}$.
• Bob rastgele seçer ${ displaystyle k}$ itibaren ${ displaystyle {0, ldots, q-1 }}$, sonra hesaplar:
  • ${ displaystyle u_ {1} = {g} _ {1} ^ {k}, u_ {2} = {g} _ {2} ^ {k}}$
  • ${ displaystyle e = h ^ {k} m}$
  • ${ displaystyle alpha = H (u_ {1}, u_ {2}, e)}$, nerede H() bir evrensel tek yönlü karma işlevi (veya a çarpışmaya dayanıklı kriptografik karma işlevi, daha güçlü bir gerekliliktir).
  • ${ displaystyle v = c ^ {k} d ^ {k alpha}}$
• Bob şifreli metni gönderir ${ displaystyle (u_ {1}, u_ {2}, e, v)}$ Alice'e.

Şifre çözme

Bir şifreli metnin şifresini çözmek için ${ displaystyle (u_ {1}, u_ {2}, e, v)}$ Alice'in gizli anahtarıyla ${ displaystyle (x_ {1}, x_ {2}, y_ {1}, y_ {2}, z)}$,

• Alice hesaplar ${ displaystyle alpha = H (u_ {1}, u_ {2}, e) ,}$ ve bunu doğrular ${ displaystyle {u} _ {1} ^ {x_ {1}} u_ {2} ^ {x_ {2}} ({u} _ {1} ^ {y_ {1}} u_ {2} ^ {y_ {2}}) ^ { alpha} = v ,}$. Bu test başarısız olursa, daha fazla şifre çözme işlemi iptal edilir ve çıktı reddedilir.
• Aksi takdirde, Alice düz metni şu şekilde hesaplar: ${ displaystyle m = e / ({u} _ {1} ^ {z}) ,}$.

Şifre çözme aşaması, düzgün biçimlendirilmiş şifreli metinlerin şifresini doğru bir şekilde çözer, çünkü

${ displaystyle {u} _ {1} ^ {z} = {g} _ {1} ^ {kz} = h ^ {k} ,}$, ve ${ displaystyle m = e / h ^ {k}. ,}$

Olası mesajların alanı, mesajın boyutundan büyükse ${ displaystyle G}$, sonra Cramer – Shoup bir hibrit şifreleme sistemi uzun mesajlarda verimliliği artırmak.

Referanslar

• Ronald Cramer ve Victor Shoup. "Uyarlanabilir seçilmiş şifreli metin saldırısına karşı güvenilir bir şekilde güvenli bir pratik açık anahtar şifreleme sistemi." Crypto 1998, LNCS 1462, s. 13ff (ps,pdf )
• Emacs Lisp ve Java'da Cramer – Shoup'un oyuncak uygulamaları
• 1998'de Cramer ve Shoup'un Kablolu Haberler ve Bruce Schneier 's Crypto-Gram
• Ronald Cramer ve Victor Shoup: "Evrensel hash provaları ve seçilen şifreli metin güvenli açık anahtar şifrelemesi için bir paradigma." Eurocrypt 2002 tutanaklarında, LNCS 2332, s. 45–64. Tam Sürüm (pdf)