Paye kryptosystem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 30 september 2017; kontroller kräver 11 redigeringar .

Peyet-kryptosystemet är ett probabilistiskt kryptosystem med offentlig nyckel som uppfanns av den franske kryptografen Pascal Paillier 1999 . I likhet med RSA , Goldwasser-Micali och Rabins kryptosystem är Peyes kryptosystem baserat på komplexiteten i att faktorisera ett sammansatt tal som är en produkt av två primtal . [ett]

Schemat är ett additivt homomorft kryptosystem, det vill säga att vi bara känner till den publika nyckeln och chiffertexterna som motsvarar klartexterna och , vi kan beräkna klartextchiffertexten . [2] $m_1$ $m_2$ ${\displaystyle m_{1}+m_{2))$

Historik

Algoritmen föreslogs först av Pascal Peyet i hans papper 1999 [3] . Uppsatsen beskrev ett antagande om komplexiteten i att beräkna roten av resten modulo och föreslog en lämplig mekanism för att använda detta matematiska problem för kryptografiska ändamål. Den ursprungliga artikeln noterar att kryptosystemet kan vara sårbart för attacker baserat på vald chiffertext , men redan 2001 visades det att med en liten förändring i det ursprungliga schemat så upphör kryptosystemet att vara sårbart för sådana attacker [4] . 2006 föreslogs en metod för att öka effektiviteten och säkerheten hos Peye-kryptosystemet baserat på verifierbara permutationer [5] .

Beskrivning av algoritmen

Algoritmen fungerar enligt följande: [3]

Nyckelgenerering

Välj två stora primtal och , så att . $sid$ $q$ $\gcd(pq,(p-1)(q-1))=1$
och beräknas . $n=pq$ $\lambda =\operatörsnamn {lcm} (p-1,q-1)$
Ett slumpmässigt heltal väljs , så att $g$ $g\in \mathbb {Z} _{n^{2}}^{*}$
Var beräknas . $\mu =(L(g^{\lambda}\mod n^{2}))^{-1}{\bmod {n))$ $L(u)=div({\frac {u-1}{n)))$

Den publika nyckeln är ett par . $(n,g)$
Den privata nyckeln är paret $(\lambda ,\mu ).$

Kryptering

Antag att klartexten måste krypteras , $m$ $m\in \mathbb {Z} _{n}$
Välj ett slumpmässigt tal $r$ $r\in \mathbb {Z} _{n}^{*}$
Beräkna chiffertexten $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$

Dekryptering

Vi accepterar chiffertext $c\in \mathbb {Z} _{n^{2}}^{*}$
Beräkna det ursprungliga meddelandet $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$

Elektronisk signatur

För att arbeta i läget för elektroniska signaturer krävs en hashfunktion . $h:\mathbb {N} \mapsto \{0,1\}^{k}\subset \mathbb {Z} _{n^{2}}^{*}$

Meddelandesignatur

För att underteckna ett meddelande är det nödvändigt att beräkna $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} }$

Den elektroniska signaturen kommer att vara ett par . $(s_{1},s_{2})$

Signaturverifiering

En signatur anses giltig om följande villkor är uppfyllt:

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

Homomorfa egenskaper

Ett utmärkande drag för Peye-kryptosystemet är dess homomorfism . Eftersom krypteringsfunktionen är additivt homomorf, kan följande identiteter skrivas [2] :

Homomorfisk tillägg av klartexter

Produkten av två chiffertexter kommer att dekrypteras som summan av deras respektive klartexter,

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

Om vi multiplicerar chiffertexten med får vi summan av motsvarande klartexter,

g^{m_{2))

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

Homomorf multiplikation av klartexter

En chiffertext upphöjd till en annan chiffertext kommer att dekrypteras som produkten av två klartexter,

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 }}.

I allmänhet kommer att höja chiffertexten till en makt dekrypteras som produkten av klartexten av ,

k

k

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

Generalisering

2001 föreslog Ivan Damgard och Mads Jurik en generalisering [6] av Peye-kryptosystemet. För att göra detta föreslås det att utföra beräkningar modulo , där , är ett naturligt tal . Den modifierade algoritmen ser ut så här: $n^{s+1}$ $n=p*q$ $s$

Nyckelgenerering

Slumpmässigt och oberoende av varandra väljs två stora primtal och . $sid$ $q$
och beräknas . $n=pq$ $\lambda =\operatörsnamn {lcm} (p-1,q-1)$
Ett tal väljs så att , där är ett känt samprimtal med och . $g\in \mathbb {Z} _{n^{s+1}}^{*}$ $g=(1+n)^{j}x{\bmod {n}}^{s+1}$ $j$ $n$ $x\i H$
Med hjälp av den kinesiska restsatsen väljer man så att och . Till exempel kan det vara lika med det ursprungliga Paye-krypteringssystemet. $d$ $d{\bmod {n}}\in \mathbb {Z} _{n}^{*}$ $d=0{\bmod {\lambda ))$ $d$ $\lambda$

Den publika nyckeln är ett par . $(n,g)$
Den privata nyckeln är . $d$

Kryptering

Låt oss säga att vi vill kryptera ett meddelande , där . $m$ $m\in \mathbb {Z} _{n^{s))$
Vi väljer ett slumpmässigt tal så att . $r$ $r\in \mathbb {Z} _{n^{s+1}}^{*}$
Vi beräknar chiffertexten . $c=g^{m}\cdot r^{n^{s}}{\bmod {n}}^{s+1}$

Dekryptering

Anta att vi har en chiffertext och vi vill dekryptera den. $c\in \mathbb {Z} _{n^{s+1}}^{*}$
Vi beräknar . Om det verkligen är en chiffertext, gäller följande likheter: . $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}}$
Vi använder en rekursiv version av Peye-krypteringsmekanismen för att få . Eftersom produkten är känd kan vi beräkna . $jmd$ $jd$ ${\displaystyle m=(jmd)\cdot (jd)^{-1}\;bmod\;n^{s))$

Applikation

Elektronisk röstning

Med Peyets kryptosystem är det möjligt att organisera val mellan flera kandidater med hjälp av följande schema: [7] [8]

Låt vara antalet väljare och sådant . $N$ $k\in \mathbb {N}$ ${\displaystyle N<2^{k))$
Om väljaren vill rösta på kandidatnummer , krypterar han numret och skickar den mottagna chiffertexten till valsamordnaren. $i$ ${\displaystyle 2^{k(i-1)))$
När man sammanfattar valresultatet dekrypterar samordnaren produkten av alla chiffertexter som tas emot från väljarna. Det är lätt att se att de första bitarna av resultatet kommer att ge antalet avgivna röster för den första kandidaten, de andra bitarna kommer att ge antalet avgivna röster för den andra kandidaten, och så vidare. $k$ $k$

Elektroniskt lotteri

Med Paye-kryptosystemet kan du organisera ett elektroniskt lotteri enligt följande: [7] [8]

Låt spelarna vilja delta i lotteriet, alla har sin egen lott med ett unikt nummer . $N$ $n\in \{0,\dots ,N-1\}$
Varje spelare väljer ett slumpmässigt nummer, krypterar det och skickar det till lotteriarrangören.
För att beräkna den "lyckliga" biljetten dekrypterar arrangören produkten av alla mottagna chiffertexter, samtidigt som den får summan av slumptal som genereras av spelarna. Arrangören av lotteriet utropar vinnaren av lotten med numret . $s$ $s{\bmod {n))$

Det är lätt att se att alla deltagare kommer att ha lika vinstsannolikheter även om spelarna försöker förfalska lotteriresultatet genom att skicka i förväg förberedda nummer till arrangören. $n-1$

Elektronisk valuta

En annan utmärkande egenskap hos Peye-kryptosystemet är den så kallade självblindande . Denna term hänvisar till möjligheten att ändra chiffertexten utan att ändra klartexten . Detta kan användas i utvecklingen av e-valutasystem såsom ecash . Låt oss säga att du vill betala för en vara online, men du vill inte ge handlaren ditt kreditkortsnummer och därmed din identitet. Precis som med e-röstning kan vi verifiera giltigheten av ett e-mynt (eller e-röst) utan att avslöja identiteten på den person som det för närvarande är associerat med.

Anteckningar

↑ Jonathan Katz, Yehuda Lindell, "Introduktion till modern kryptografi: principer och protokoll," Chapman & Hall/CRC, 2007
↑ 1 2 Varnovsky N. P., Shokurov A. V. "Homomorphic encryption", 2007
↑ 1 2 Pascal Paillier, "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes", 1999
↑ Pierre-Alain Fouque och David Pointcheval, "Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks", 2001
↑ Lan Nguyen, Rei Safavi-Naini, Kaoru Kurosawa, "En bevisligen säker och effektiv verifierbar Shuﬄe baserad på en variant av Paillier Cryptosystem", 2006
↑ Jurik M., Damgård I. "A Generalization, a Simplification and Some Applications of Pailliers Probabilistic Public-Key System", 1999
↑ 1 2 P.-A., Poupard G., Stern J., "Sharing Decryption in the Context of Voting or Lotteries", 2001
↑ 1 2 Jurik MJ, "Utökningar till paillier kryptosystem med applikationer till kryptologiska protokoll", 2003

Litteratur

Paillier P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes (engelska) // Advances in cryptology, EUROCRYPT'99. - 1999. - S. 223-238 . - ISBN 978-3-540-48910-8 . - doi : 10.1007/3-540-48910-X_16 . Arkiverad från originalet den 17 december 2014.

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

Jurik MJ Utvidgningar till paillier kryptosystem med applikationer till kryptologiska protokoll (engelska) // Public Key Cryptography. - 2003. - S. 119-136 .

Jurik M., Damgård I. A Generalization, a Simplification and Some Applications of Pailliers Probabilistic Public-Key System // Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptosystems. - 2001. - S. 119-136 .

Varnovsky N. P., Shokurov A. V. Homomorf kryptering // Proceedings of ISP RAS. - 2007. - S. 27-36 . (ryska)

Katz J., Lindell Y. Introduktion till modern kryptografi: principer och protokoll. - Chapman & Hall / CRC, 2007. - P. 385-395. — ISBN 978-1584885511 .

Länkar

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort