Blum – Goldwasser şifreleme sistemi - Blum–Goldwasser cryptosystem

Blum – Goldwasser (BG) kripto sistemi bir asimetrik anahtar şifreleme algoritması öneren Manuel Blum ve Shafi Goldwasser 1984 yılında. Blum – Goldwasser bir olasılığa dayalı, anlamsal olarak güvenli sabit boyutlu şifreleme sistemi şifreli metin genişletme. Şifreleme algoritması, XOR tabanlı bir kesintisiz şifreleme kullanmak Blum-Blum-Shub (BBS) sözde rastgele sayı üreteci anahtar akışı. Şifre çözme, BBS oluşturucunun son durumu, Özel anahtar, ilk tohumu bulmak ve anahtar akışını yeniden oluşturmak için.

BG şifreleme sistemi anlamsal olarak güvenli varsayılan inatçılık temelinde tamsayı çarpanlara ayırma; özellikle, bileşik bir değeri çarpanlara ayırma ${ displaystyle N = pq}$ nerede ${ displaystyle p, q}$ büyüktür asal. BG, daha önceki olasılıklı şifreleme şemalarına göre birçok avantaja sahiptir. Goldwasser – Micali kripto sistemi. Birincisi, anlamsal güvenliği, herhangi bir ek varsayım gerektirmeden (örn. ikinci dereceden kalıntı problemi ya da RSA sorunu ). İkincisi, BG, depolama açısından etkilidir ve sabit bir boyuta neden olur. şifreli metin genişletme mesaj uzunluğundan bağımsız olarak. BG aynı zamanda hesaplama açısından nispeten etkilidir ve RSA gibi şifreleme sistemleriyle karşılaştırıldığında bile iyi performans gösterir (mesaj uzunluğu ve üs seçeneklerine bağlı olarak). Ancak, BG, uyarlanabilir seçilmiş şifreli metin saldırılarına karşı oldukça savunmasızdır (aşağıya bakın).

Şifreleme, olasılıklı bir algoritma kullanılarak gerçekleştirildiğinden, belirli bir düz metin, her şifrelendiğinde çok farklı şifreli metinler üretebilir. Bu, bir düşmanın yakalanan mesajları bilinen şifreli metinler sözlüğüyle karşılaştırarak tanımasını engellediği için önemli avantajlara sahiptir.

Operasyon

Blum – Goldwasser şifreleme sistemi üç algoritmadan oluşur: bir genel ve bir özel anahtar üreten olasılıklı bir anahtar oluşturma algoritması, olasılıklı bir şifreleme algoritması ve belirleyici bir şifre çözme algoritması.

Anahtar oluşturma

Genel ve özel anahtarlar şu şekilde oluşturulur:

1. İki büyük farklı asal sayı seçin ${ displaystyle p}$ ve ${ displaystyle q}$ öyle ki ${ displaystyle p eşdeğeri 3 { bmod {4}}}$ ve ${ displaystyle q eşdeğeri 3 { bmod {4}}}$.
2. Hesaplama ${ displaystyle n = pq}$.^[1]

Sonra ${ displaystyle n}$ açık anahtar ve çift ${ displaystyle (p, q)}$ özel anahtardır.

Şifreleme

Bir mesaj ${ displaystyle M}$ genel anahtarla şifrelenmiştir ${ displaystyle n}$ aşağıdaki gibi:

1. Blok boyutunu bit cinsinden hesaplayın, ${ displaystyle h = lfloor log_ {2} (log_ {2} (n)) rfloor}$.
2. Dönüştürmek ${ displaystyle M}$ bir dizi ${ displaystyle t}$ bloklar ${ displaystyle m_ {1}, m_ {2}, noktalar, m_ {t}}$, her bloğun olduğu yer ${ displaystyle h}$ bit uzunluğunda.
3. Rastgele bir tam sayı seçin ${ displaystyle r$.
4. Hesaplama ${ displaystyle x_ {0} = r ^ {2} { bmod {n}}}$.
5. İçin ${ displaystyle i}$ 1'den ${ displaystyle t}$
   1. Hesaplama ${ displaystyle x_ {i} = x_ {i-1} ^ {2} { bmod {n}}}$.
   2. Hesaplama ${ displaystyle p_ {i} =}$ en az önemli ${ displaystyle h}$ bitleri ${ displaystyle x_ {i}}$.
   3. Hesaplama ${ displaystyle c_ {i} = m_ {i} oplus p_ {i}}$.
6. Son olarak hesaplayın ${ displaystyle x_ {t + 1} = x_ {t} ^ {2} { bmod {n}}}$.

Mesajın şifrelenmesi ${ displaystyle M}$ o zaman hepsi ${ displaystyle c_ {i}}$ değerler artı final ${ displaystyle x_ {t + 1}}$ değer: ${ displaystyle (c_ {1}, c_ {2}, noktalar, c_ {t}, x_ {t + 1})}$.

Şifre çözme

Şifrelenmiş bir mesaj ${ displaystyle (c_ {1}, c_ {2}, noktalar, c_ {t}, x)}$ özel anahtarla şifresi çözülebilir ${ displaystyle (p, q)}$ aşağıdaki gibi:

1. Hesaplama ${ displaystyle d_ {p} = ((p + 1) / 4) ^ {t + 1} { bmod {(p-1)}}}$.
2. Hesaplama ${ displaystyle d_ {q} = ((q + 1) / 4) ^ {t + 1} { bmod {(q-1)}}}$.
3. Hesaplama ${ displaystyle u_ {p} = x ^ {d_ {p}} { bmod {p}}}$.
4. Hesaplama ${ displaystyle u_ {q} = x ^ {d_ {q}} { bmod {q}}}$.
5. Kullanmak Genişletilmiş Öklid Algoritması, hesaplamak ${ displaystyle r_ {p}}$ ve ${ displaystyle r_ {q}}$ öyle ki ${ displaystyle r_ {p} p + r_ {q} q = 1}$.
6. Hesaplama ${ displaystyle x_ {0} = u_ {q} r_ {p} p + u_ {p} r_ {q} q { bmod {n}}}$. Bu, şifrelemede kullanılanla aynı değer olacaktır (aşağıdaki kanıta bakın). ${ displaystyle x_ {0}}$ daha sonra aynı sırayı hesaplamak için kullanılabilir ${ displaystyle x_ {i}}$ aşağıdaki gibi mesajın şifresini çözmek için şifrelemede kullanılan değerler.
7. İçin ${ displaystyle i}$ 1'den ${ displaystyle t}$
   1. Hesaplama ${ displaystyle x_ {i} = x_ {i-1} ^ {2} { bmod {n}}}$.
   2. Hesaplama ${ displaystyle p_ {i} =}$ en az önemli ${ displaystyle h}$ bitleri ${ displaystyle x_ {i}}$.
   3. Hesaplama ${ displaystyle m_ {i} = c_ {i} oplus p_ {i}}$.
8. Son olarak değerleri yeniden birleştirin ${ displaystyle (m_ {1}, m_ {2}, noktalar, m_ {t})}$ mesaja ${ displaystyle M}$.

Misal

İzin Vermek ${ displaystyle p = 19}$ ve ${ displaystyle q = 7}$. Sonra ${ displaystyle n = 133}$ ve ${ displaystyle h = lfloor log_ {2} (log_ {2} (133)) rfloor = 3}$. Altı bitlik mesajı şifrelemek için ${ displaystyle 101001_ {2}}$, onu iki adet 3 bitlik bloğa ayırıyoruz ${ displaystyle m_ {1} = 101_ {2}, m_ {2} = 001_ {2}}$, yani ${ displaystyle t = 2}$. Rastgele seçiyoruz ${ displaystyle r = 36}$ ve hesapla ${ displaystyle x_ {0} = 36 ^ {2} { bmod {1}} 33 = 99}$. Şimdi hesaplıyoruz ${ displaystyle c_ {i}}$ değerler aşağıdaki gibidir:

${ displaystyle { begin {align} x_ {1} & = 99 ^ {2} { bmod {1}} 33 = 92 = 1011100_ {2}; quad p_ {1} = 100_ {2}; quad c_ {1} = 101_ {2} oplus 100_ {2} = 001_ {2} x_ {2} & = 92 ^ {2} { bmod {1}} 33 = 85 = 1010101_ {2}; dörtlü p_ {2} = 101_ {2}; quad c_ {2} = 001_ {2} oplus 101_ {2} = 100_ {2} x_ {3} & = 85 ^ {2} { bmod { 1}} 33 = 43 end {hizalı}}}$

Yani şifreleme ${ displaystyle (c_ {1} = 001_ {2}, c_ {2} = 100_ {2}, x_ {3} = 43)}$.

Şifresini çözmek için hesaplıyoruz

${ displaystyle { begin {align} d_ {p} & = 5 ^ {3} { bmod {1}} 8 = 17 d_ {q} & = 2 ^ {3} { bmod {6}} = 2 u_ {p} & = 43 ^ {17} { bmod {1}} 9 = 4 u_ {q} & = 43 ^ {2} { bmod {7}} = 1 ( r_ {p}, r_ {q}) & = (3, -8) { text {beri}} 3 cdot 19 + (- 8) cdot 7 = 1 x_ {0} & = 1 cdot 3 cdot 19 + 4 cdot (-8) cdot 7 { bmod {1}} 33 = 99 uç {hizalı}}}$

Görülebilir ki ${ displaystyle x_ {0}}$ şifreleme algoritmasındaki ile aynı değere sahiptir. Bu nedenle şifre çözme, şifrelemeyle aynı şekilde ilerler:

${ displaystyle { begin {align} x_ {1} & = 99 ^ {2} { bmod {1}} 33 = 92 = 1011100_ {2}; quad p_ {1} = 100_ {2}; quad m_ {1} = 001_ {2} oplus 100_ {2} = 101_ {2} x_ {2} & = 92 ^ {2} { bmod {1}} 33 = 85 = 1010101_ {2}; dörtlü p_ {2} = 101_ {2}; quad m_ {2} = 100_ {2} oplus 101_ {2} = 001_ {2} end {hizalı}}}$

Doğruluğun kanıtı

Değerini göstermeliyiz ${ displaystyle x_ {0}}$ şifre çözme algoritmasının 6. adımında hesaplanan, şifreleme algoritmasının 4. adımında hesaplanan değere eşittir.

Şifreleme algoritmasında, yapım gereği ${ displaystyle x_ {0}}$ ikinci dereceden bir kalıntı modulodur ${ displaystyle n}$. Bu nedenle aynı zamanda ikinci dereceden bir kalıntı modulodur ${ displaystyle p}$diğerleri gibi ${ displaystyle x_ {i}}$ ondan karesi alınarak elde edilen değerler. Bu nedenle Euler'in kriteri, ${ displaystyle x_ {i} ^ {(p-1) / 2} eşdeğeri 1 mod {p}}$. Sonra

${ displaystyle x_ {t + 1} ^ {(p + 1) / 4} equiv (x_ {t} ^ {2}) ^ {(p + 1) / 4)} equiv x_ {t} ^ { (p + 1) / 2} equiv x_ {t} (x_ {t} ^ {(p-1) / 2}) equiv x_ {t} mod {p}}$

Benzer şekilde,

${ displaystyle x_ {t} ^ {(p + 1) / 4} equiv x_ {t-1} mod {p}}$

İlk denklemi kuvvete yükseltmek ${ displaystyle (p + 1) / 4}$ biz alırız

${ displaystyle x_ {t + 1} ^ {((p + 1) / 4) ^ {2}} equiv x_ {t} ^ {(p + 1) / 4} equiv x_ {t-1} mod {p}}$

Bunu tekrar ediyorum ${ displaystyle t}$ zamanımız var

${ displaystyle x_ {t + 1} ^ {(p + 1) / 4) ^ {t + 1}} equiv x_ {0} mod {p}}$

${ displaystyle x_ {t + 1} ^ {d_ {p}} equiv u_ {p} equiv x_ {0} mod {p}}$

Ve benzer bir argümanla bunu gösterebiliriz ${ displaystyle x_ {t + 1} ^ {d_ {q}} equiv u_ {q} equiv x_ {0} mod {q}}$.

Son olarak, o zamandan beri ${ displaystyle r_ {p} p + r_ {q} q = 1}$ile çarpabiliriz ${ displaystyle x_ {0}}$ ve Al

${ displaystyle x_ {0} r_ {p} p + x_ {0} r_ {q} q = x_ {0}}$

olan ${ displaystyle u_ {q} r_ {p} p + u_ {p} r_ {q} q equiv x_ {0}}$, her ikisi de modulo ${ displaystyle p}$ ve ${ displaystyle q}$, ve bu nedenle ${ displaystyle u_ {q} r_ {p} p + u_ {p} r_ {q} q equiv x_ {0} mod {n}}$.

Güvenlik ve verimlilik

Blum – Goldwasser planı anlamsal olarak güvenli sadece son BBS durumu verilen anahtar akışı bitlerini tahmin etmenin sertliğine dayanır ${ displaystyle y}$ ve genel anahtar ${ displaystyle N}$. Ancak, formun şifreli metinleri ${ displaystyle { vec {c}}, y}$ savunmasız uyarlanabilir seçilmiş şifreli metin saldırısı düşmanın şifre çözmeyi istediği ${ displaystyle m ^ { prime}}$ seçilmiş bir şifreli metnin ${ displaystyle { vec {a}}, y}$. Şifre çözme ${ displaystyle m}$ orijinal şifreli metnin oranı şu şekilde hesaplanabilir: ${ displaystyle { vec {a}} oplus m ^ { prime} oplus { vec {c}}}$.

Düz metin boyutuna bağlı olarak BG, RSA'dan daha fazla veya daha az hesaplama açısından pahalı olabilir. Çoğu RSA dağıtımı, şifreleme süresini en aza indirmek için optimize edilmiş sabit bir şifreleme üssü kullandığından, RSA şifrelemesi genellikle en kısa mesajlar dışında tümü için BG'den daha iyi performans gösterir. Bununla birlikte, RSA şifre çözme üssü rastgele dağıtıldığı için, modüler üs alma, aynı uzunluktaki bir şifreli metin için BG şifre çözme ile karşılaştırılabilir sayıda kare / çarpma gerektirebilir. BG, RSA'nın birden çok ayrı şifreleme gerektirdiği durumlarda daha uzun şifreli metinlere daha verimli bir şekilde ölçeklendirme avantajına sahiptir. Bu durumlarda, KŞ önemli ölçüde daha verimli olabilir.

Referanslar

1. M. Blum, S. Goldwasser, "Tüm Kısmi Bilgileri Gizleyen Etkin Olasılıksal Açık Anahtar Şifreleme Düzeni", Kriptolojideki Gelişmeler - CRYPTO '84, s. 289–299, Springer Verlag, 1985.
2. Menezes, Alfred; van Oorschot, Paul C .; ve Vanstone, Scott A. Uygulamalı Kriptografi El Kitabı. CRC Press, Ekim 1996. ISBN  0-8493-8523-7

Dış bağlantılar

• Menezes, Oorschot, Vanstone, Scott: Uygulamalı Kriptografi El Kitabı (ücretsiz PDF indirmeleri), 8. Bölüme bakın