Naccache – Stern sırt çantası şifreleme sistemi - Naccache–Stern knapsack cryptosystem

Naccache – Stern Sırt Çantası Cryptosystem atipik açık anahtarlı şifreleme sistemi tarafından geliştirilmiş David Naccache ve Jacques Stern 1997 yılında. Bu şifreleme sistemi belirleyici ve dolayısıyla değil anlamsal olarak güvenli. Bugüne kadar kırılmamış olsa da, bu sistemde de eksik kanıtlanabilir güvenlik.

sistem görünümü

Bu sistem bir tür sırt çantası sorunu. Spesifik olarak, temel sorun şudur: verilen tamsayılar c,n,p ve v₀,...,v_n, bir vektör bul ${displaystyle xin {0,1} ^ {n}}$ öyle ki

${displaystyle cequiv prod _ {i = 0} ^ {n} v_ {i} ^ {x_ {i}} mod p}$

Buradaki fikir şudur: v_ben vardır nispeten asal ve modülden çok daha küçük p bu problem kolaylıkla çözülebilir. Şifre çözmeyi sağlayan bu gözlemdir.

Anahtar Üretimi

Genel / özel anahtar çifti oluşturmak için

• Büyük seçin önemli modül p.
• Pozitif bir tam sayı seçin n ve için ben 0'dan n, Ayarlamak p_ben olmak benile başlayan asal p₀ = 2 ve öyle ki ${displaystyle prod _ {i = 0} ^ {n} p_ {i}$.
• Gizli bir tam sayı seçin s < p-1, öyle ki gcd (p-1,s) = 1.
• Ayarlamak ${displaystyle v_ {i} = {sqrt [{s}] {p_ {i}}} mod p}$.

Açık anahtar o zaman p,n ve v₀,...,v_n. Özel anahtar s.

Şifreleme

Şifrelemek için n-bit uzun mesaj m, hesaplamak

${displaystyle c = prod _ {i = 0} ^ {n} v_ {i} ^ {m_ {i}} mod p}$

nerede m_ben ... benmesajın inci kısmı m.

Şifre çözme

Bir mesajın şifresini çözmek için c, hesaplamak

${displaystyle m = toplam _ {i = 0} ^ {n} {frac {2 ^ {i}} {p_ {i} -1}} imes kaldı (gcd (p_ {i}, c ^ {s} mod p ) -1ight)}$

Bu işe yarıyor çünkü kesir

${displaystyle {frac {gcd (p_ {i}, c ^ {s} mod p) -1} {p_ {i} -1}}}$

0 veya 1 olup olmamasına bağlı olarak p_ben böler c^s mod p.

Ayrıca bakınız

• Merkle – Hellman sırt çantası şifreleme sistemi
• Graham-Shamir sırt çantası şifreleme sistemi

Referanslar

• Orjinal kağıt
• Son bant genişliği iyileştirmesi