Naccache – Sternův kryptosystém - Naccache–Stern cryptosystem

The Naccache – Sternův kryptosystém je homomorfní kryptosystém veřejného klíče jehož bezpečnost spočívá na problém vyšší reziduaity. Kryptosystém Naccache – Stern byl objeven uživatelem David Naccache a Jacques Stern v roce 1998.

Definice schématu

Jako mnozí kryptosystémy veřejného klíče, toto schéma funguje ve skupině ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*}}$ kde n je produktem dvou velkých připraví. Toto schéma je homomorfní a tudíž tvárný.

Generování klíčů

• Vyberte rodinu k malý zřetelný připraví str₁,...,str_k.
• Rozdělte sadu na polovinu a nastavte ${displaystyle u = prod _ {i = 1} ^ {k / 2} p_ {i}}$ a ${displaystyle v = prod _ {k / 2 + 1} ^ {k} p_ {i}}$.
• Soubor ${displaystyle sigma = uv = prod _ {i = 1} ^ {k} p_ {i}}$
• Vyberte si velká prvočísla A a b takové, že oba str = 2au+1 a q=2bv+1 jsou hlavní.
• Soubor n=pq.
• Vyberte si náhodný G mod n takhle G má řád φ (n)/4.

Veřejným klíčem jsou čísla σ,n,G a soukromý klíč je dvojice str,q.

Když k= 1 toto je v podstatě Kryptosystém Benaloh.

Šifrování zpráv

Tento systém umožňuje šifrování zprávy m ve skupině ${displaystyle mathbb {Z} / sigma mathbb {Z}}$.

• Vyberte náhodně ${displaystyle xin mathbb {Z} / nmathbb {Z}}$.
• Vypočítat ${displaystyle E (m) = x ^ {sigma} g ^ {m} mod n}$

Pak E (m) je šifrování zprávy m.

Dešifrování zprávy

K dešifrování nejprve najdeme m mod str_i pro každého ia poté použijeme Čínská věta o zbytku vypočítat m mod ${displaystyle sigma}$.

Vzhledem k šifrovacímu textu C, k dešifrování, vypočítáme

• ${displaystyle c_ {i} ekviv c ^ {phi (n) / p_ {i}} mod n}$. Tím pádem

${displaystyle {egin {matrix} c ^ {phi (n) / p_ {i}} & equiv & x ^ {sigma phi (n) / p_ {i}} g ^ {mphi (n) / p_ {i}} mod n & equiv & g ^ {(m_ {i} + y_ {i} p_ {i}) phi (n) / p_ {i}} mod n & equiv & g ^ {m_ {i} phi (n) / p_ {i} } mod nend {matrix}}}$

kde ${displaystyle m_ {i} ekvivalent mmod p_ {i}}$.

• Od té doby str_i je vybrán jako malý, m_i lze obnovit vyčerpávajícím hledáním, tj. porovnáním ${displaystyle c_ {i}}$ na ${displaystyle g ^ {jphi (n) / p_ {i}}}$ pro j od 1 do str_i-1.
• Jednou m_i je známý pro každého i, m lze získat přímou aplikací čínské věty o zbytku.

Bezpečnostní

The sémantická bezpečnost kryptosystému Naccache – Stern spočívá na rozšíření kvadratický problém reziduaity známý jako problém vyšší reziduaity.

Reference

Naccache, David; Stern, Jacques (1998). „Nový kryptosystém veřejného klíče založený na vyšších reziduích“. Sborník z 5. konference ACM o počítačové a komunikační bezpečnosti. CCS '98. ACM. str. 59–66. doi:10.1145/288090.288106. ISBN  1-58113-007-4.