Paye kriptorendszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. szeptember 30-án felülvizsgált verziótól ; az ellenőrzések 11 szerkesztést igényelnek .

A Peyet kriptorendszer egy valószínűségi nyilvános kulcsú kriptorendszer , amelyet Pascal Paillier francia kriptográfus talált fel 1999-ben . Az RSA , Goldwasser-Micali és Rabin kriptorendszerekhez hasonlóan a Peye kriptorendszere egy összetett szám faktorálásának összetettségén alapul, amely két prímszám szorzata . [egy]

A séma egy additív homomorf titkosítási rendszer, azaz csak a nyilvános kulcs és a nyílt szövegekhez tartozó rejtjelezett szövegek ismeretében, és a sima szöveges titkosítást tudjuk kiszámítani . [2] $m_1$ $m_2$ ${\displaystyle m_{1}+m_{2))$

Történelem

Az algoritmust először Pascal Peyet javasolta 1999-ben megjelent cikkében [3] . A cikk leírt egy feltételezést a maradék modulo gyökér kiszámításának bonyolultságáról, és megfelelő mechanizmust javasolt ennek a matematikai problémának a kriptográfiai célokra való felhasználására. Az eredeti cikk megjegyzi, hogy a kriptorendszer sebezhető lehet a választott rejtjelezett szövegen alapuló támadásokkal szemben , de már 2001-ben kiderült, hogy az eredeti séma enyhe változtatásával a kriptorendszer megszűnik sebezhetővé válni az ilyen támadásokkal szemben [4] . 2006-ban egy módszert javasoltak a Peye kriptorendszer hatékonyságának és biztonságának növelésére, ellenőrizhető permutációk alapján [5] .

Az algoritmus leírása

Az algoritmus a következőképpen működik: [3]

Kulcsgenerálás

Válasszon két nagy prímszámot és , úgy, hogy . $p$ $q$ $\gcd(pq,(p-1)(q-1))=1$
és kiszámítják . $n=pq$ $\lambda =\operátornév {lcm} (p-1,q-1)$
Egy véletlenszerű egész számot választunk , úgy, hogy $g$ $g\in \mathbb {Z} _{n^{2}}^{*}$
Hol számítják ki . $\mu =(L(g^{\lambda }\mod n^{2}))^{-1}{\bmod {n))$ $L(u)=div({\frac {u-1}{n)))$

A nyilvános kulcs egy pár . ${\megjelenítési stílus (n,g)}$
A privát kulcs a pár $(\lambda ,\mu ).$

Titkosítás

Tegyük fel, hogy a nyílt szöveget titkosítani kell , $m$ $m\in \mathbb {Z} _{n}$
Válasszon egy véletlen számot $r$ $r\in \mathbb {Z} _{n}^{*}$
Számítsa ki a rejtjelezett szöveget $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$

Dekódolás

Elfogadjuk a titkosított szöveget $c\in \mathbb {Z} _{n^{2}}^{*}$
Számítsa ki az eredeti üzenetet $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$

Elektronikus aláírás

Az elektronikus aláírás módban való munkához hash funkcióra van szükség . $h:\mathbb {N} \mapsto \{0,1\}^{k}\subset \mathbb {Z} _{n^{2}}^{*}$

Üzenet aláírása

Egy üzenet aláírásához számolni kell $m$

$s_{1}={\frac {L(h(m)^{\lambda }{\bmod {n}}^{2})}{L(g^{\lambda }{\bmod {n }}^{2})}}{\bmod {n}}$

$s_{2}=(h(m)g^{-s_{1)))^({\frac {1}{n)){\bmod {\lambda ))}{\bmod {n} }$

Az elektronikus aláírás egy pár lesz . $(s_{1},s_{2})$

Aláírás ellenőrzése

Az aláírás érvényesnek minősül, ha az alábbi feltétel teljesül:

$h(m)=g^{s_{1}}s_{2}^{n}{\bmod {n}}^{2}$ .

Homomorf tulajdonságok

A Peye kriptorendszer megkülönböztető jellemzője a homomorfizmusa . Mivel a titkosítási függvény additívan homomorf, a következő azonosságok írhatók fel [2] :

Nyílt szövegek homomorf összeadása

Két titkosított szöveg szorzata a megfelelő nyílt szövegek összegeként kerül visszafejtésre,

D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod {n))^{2})=m_{1}+m_ {2}{\bmod {n}}.

A titkosított szöveget megszorozva a megfelelő nyílt szövegek összegét kapjuk,

g^{m_{2))

D(E(m_{1},r_{1})\cdot g^{m_{2}}{\bmod {n}}^{2})=m_{1}+m_{2}{ \bmod{n}}.

Nyílt szövegek homomorf sokszorosítása

Egy másik rejtjelszöveg erejéig emelt titkosított szöveg két nyílt szöveg szorzataként dekódolásra kerül,

D(E(m_{1},r_{1})^{m_{2}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n }},

D(E(m_{2},r_{2})^{m_{1}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n }}.

Általában a titkosított szöveg hatványra emelését a nyílt szöveg szorzataként dekódolja ,

k

k

D(E(m_{1},r_{1})^{k}{\bmod {n}}^{2})=km_{1}{\bmod {n}}.

Általánosítás

2001-ben Ivan Damgard és Mads Jurik a Peye kriptorendszer általánosítását [6] javasolta . Ehhez javasoljuk a modulo számítások elvégzését , ahol , egy természetes szám . A módosított algoritmus így néz ki: $n^{s+1}$ $n=p*q$ $s$

Kulcsgenerálás

Véletlenszerűen és egymástól függetlenül két nagy prímszámot és választunk . $p$ $q$
és kiszámítják . $n=pq$ $\lambda =\operátornév {lcm} (p-1,q-1)$
Egy számot úgy választunk ki , hogy ahol egy ismert másodprím szám és . $g\in \mathbb {Z} _{n^{s+1}}^{*}$ $g=(1+n)^{j}x{\bmod {n}}^{s+1}$ $j$ $n$ $x\in H$
A kínai maradéktételt használva választunk olyat, hogy és . Például egyenlő lehet az eredeti Paye kriptorendszerrel. $d$ $d{\bmod {n}}\in \mathbb {Z} _{n}^{*}$ $d=0{\bmod {\lambda ))$ $d$ $\lambda$

A nyilvános kulcs egy pár . ${\megjelenítési stílus (n,g)}$
A privát kulcs a . $d$

Titkosítás

Tegyük fel, hogy titkosítani szeretnénk egy üzenetet , ahol . $m$ $m\in \mathbb {Z} _{n^{s))$
Olyan véletlen számot választunk , hogy . $r$ $r\in \mathbb {Z} _{n^{s+1}}^{*}$
Kiszámoljuk a titkosított szöveget . $c=g^{m}\cdot r^{n^{s}}{\bmod {n}}^{s+1}$

Dekódolás

Tegyük fel, hogy van egy titkosított szövegünk , és szeretnénk visszafejteni. $c\in \mathbb {Z} _{n^{s+1}}^{*}$
Kiszámoljuk . Ha valóban titkosított szöveg, akkor a következő egyenlőségek teljesülnek: . $c^{d}\;mod\;n^{s+1}$ $c$ $c^{d}=(g^{m}r^{n^{s)))^{d}=((1+n)^{jm}x^{m}r^{n^ {s}})^{d}=(1+n)^{jmd\;bmod\;n^{s}}(x^{m}r^{n^{s}})^{d\; bmod\;\lambda }=(1+n)^{jmd\;bmod\;n^{s}}$
A Peye kriptorendszer visszafejtési mechanizmusának rekurzív verzióját használjuk a beszerzéshez . Mivel a szorzat ismert, ki tudjuk számítani . $jmd$ $jd$ ${\displaystyle m=(jmd)\cdot (jd)^{-1}\;bmod\;n^{s))$

Alkalmazás

Elektronikus szavazás

A Peyet kriptorendszer segítségével több jelölt között is lehet választásokat szervezni a következő séma szerint: [7] [8]

Legyen a szavazók száma és olyan, hogy . $N$ $k\in \mathbb {N}$ ${\displaystyle N<2^{k))$
Ha a választópolgár jelöltszámra kíván szavazni , akkor titkosítja a számot , és a kapott titkosított szöveget elküldi a választási koordinátornak. $én$ ${\displaystyle 2^{k(i-1)))$
A választási eredmények összesítésekor a koordinátor visszafejti a választóktól kapott összes titkosított szöveg szorzatát. Könnyen belátható, hogy az eredmény első bitjei az első jelöltre leadott szavazatok számát, a második bitek a második jelöltre leadott szavazatok számát és így tovább. $k$ $k$

Elektronikus lottó

A Paye kriptorendszer használatával az alábbiak szerint szervezhet elektronikus lottójátékot: [7] [8]

Hagyja , hogy a játékosok részt vegyenek a lottón, mindenkinek van saját sorsjegye, egyedi számmal . $N$ $n\in \{0,\dots ,N-1\}$
Minden játékos választ egy véletlen számot, titkosítja és elküldi a lottó szervezőjének.
A "szerencsés" jegy kiszámításához a szervező visszafejti az összes kapott rejtjelezett szöveg szorzatát, miközben megkapja a játékosok által generált véletlen számok összegét. A sorsolás szervezője a számmal kihirdeti a jegy nyertesét . $s$ $s{\bmod {n))$

Könnyen belátható, hogy minden résztvevő egyenlő esélyekkel fog nyerni még akkor is, ha a játékosok megpróbálják meghamisítani a sorsolás eredményét úgy, hogy előre elkészített számokat küldenek a szervezőnek. $n-1$

Elektronikus pénznem

A Peye kriptorendszer másik megkülönböztető jellemzője az úgynevezett önvakítás . Ez a kifejezés a titkosított szöveg megváltoztatásának képességére utal a nyílt szöveg megváltoztatása nélkül . Ezt fel lehet használni az e-valuta rendszerek, például az ecash fejlesztésében . Tegyük fel, hogy online szeretne fizetni egy tételért , de nem szeretné megadni a kereskedőnek hitelkártyaszámát , és így személyazonosságát sem. Az e-szavazáshoz hasonlóan ellenőrizhetjük az e-érmék (vagy e-szavazatok) érvényességét anélkül, hogy felfednénk annak a személynek a kilétét, akihez jelenleg kapcsolódik.

Jegyzetek

↑ Jonathan Katz, Yehuda Lindell, "Bevezetés a modern kriptográfiába: alapelvek és protokollok", Chapman és Hall/CRC, 2007
↑ 1 2 Varnovsky N. P., Shokurov A. V. "Homomorf titkosítás", 2007
↑ 1 2 Pascal Paillier, "Public-Key Cryptosystems Based on Composite Degree Residuality Classes", 1999
↑ Pierre-Alain Fouque és David Pointcheval, "Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks", 2001
↑ Lan Nguyen, Rei Safavi-Naini, Kaoru Kurosawa, "A Provably Secure and Efcient Verifiable Shufie based on Variant of the Paillier Cryptosystem", 2006
↑ Jurik M., Damgård I. "A Paillier-féle valószínűségi nyilvános kulcsrendszer általánosítása, egyszerűsítése és néhány alkalmazása", 1999
↑ 1 2 P.-A., Poupard G., Stern J., "Sharing Decryption in the Context of Voting or Lotteries", 2001
↑ 1 2 Jurik MJ, "Kiterjesztések a paillier kriptorendszerhez kriptológiai protokollok alkalmazásaival", 2003

Irodalom

Paillier P. Public-Key Cryptosystems Based on Composite Degree Residuality Classes (angol) // Advances in cryptology, EUROCRYPT'99. - 1999. - P. 223-238 . - ISBN 978-3-540-48910-8 . - doi : 10.1007/3-540-48910-X_16 . Az eredetiből archiválva : 2014. december 17.

Fouque P.-A., Poupard G., Stern J. Sharing Decryption in the Context of Voting or Lotteries // Financial Cryptography, Proceedings of 4th International Conference. - 2001. - P. 90-104 . — ISBN 978-3-540-45472-4 . - doi : 10.1007/3-540-45472-1_7 .

Jurik MJ Kiterjesztések a paillier kriptorendszerhez kriptológiai protokollok alkalmazásaival (angol) // Nyilvános kulcsú kriptográfia. - 2003. - P. 119-136 .

Jurik M., Damgård I. Paillier valószínűségi nyilvános kulcsú rendszerének általánosítása, egyszerűsítése és néhány alkalmazása // Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptosystems. - 2001. - P. 119-136 .

Varnovsky N. P., Shokurov A. V. Homomorf titkosítás // Proceedings of ISP RAS. - 2007. - S. 27-36 . (Orosz)

Katz J., Lindell Y. Bevezetés a modern kriptográfiába: alapelvek és protokollok. - Chapman & Hall / CRC, 2007. - P. 385-395. — ISBN 978-1584885511 .

Linkek

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya