Criptosistemul Paye

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 septembrie 2017; verificările necesită 11 modificări .

Criptosistemul Peyet este un criptosistem probabilist cu cheie publică, inventat de criptograful francez Pascal Paillier în 1999 . Similar cu criptosistemele RSA , Goldwasser-Micali și Rabin , criptosistemul lui Peye se bazează pe complexitatea factorizării unui număr compus care este un produs din două numere prime . [unu]

Schema este un criptosistem homomorf aditiv , adică cunoscând doar cheia publică și textele cifrate corespunzătoare textelor clare și , putem calcula textul cifrat simplu . [2] $m_1$ $m_2$ $m_{1}+m_{2)$

Istorie

Algoritmul a fost propus pentru prima dată de Pascal Peyet în lucrarea sa în 1999 [3] . Lucrarea a descris o ipoteză despre complexitatea calculării rădăcinii restului modulo și a propus un mecanism adecvat pentru utilizarea acestei probleme matematice în scopuri criptografice. Articolul original notează că criptosistemul poate fi vulnerabil la atacuri bazate pe textul cifrat ales , dar deja în 2001 s-a demonstrat că, odată cu o ușoară schimbare în schema originală, criptosistemul încetează să mai fie vulnerabil la astfel de atacuri [4] . În 2006, a fost propusă o metodă de creștere a eficienței și securității criptosistemului Peye bazată pe permutări verificabile [5] .

Descrierea algoritmului

Algoritmul funcționează după cum urmează: [3]

Generare cheie

Alegeți două numere prime mari și , astfel încât . $p$ $q$ $\gcd(pq,(p-1)(q-1))=1$
si se calculeaza . $n=pq$ $\lambda =\operatorname {lcm} (p-1,q-1)$
Se alege un număr întreg aleatoriu , astfel încât $g$ $g\in \mathbb {Z} _{n^{2}}^{*}$
Unde se calculeaza . $\mu =(L(g^{\lambda }\mod n^{2}))^{-1}{\bmod {n))$ $L(u)=div({\frac {u-1}{n)})$

Cheia publică este o pereche . $(n,g)$
Cheia privată este perechea $(\lambda,\mu).$

Criptare

Să presupunem că textul simplu trebuie criptat , $m$ $m\in \mathbb {Z} _{n}$
Alegeți un număr aleatoriu $r$ $r\in \mathbb {Z} _{n}^{*}$
Calculați textul cifrat $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$

Decriptare

Acceptăm text cifrat $c\in \mathbb {Z} _{n^{2}}^{*}$
Calculați mesajul original $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$

Semnătura electronică

Pentru a lucra în modul semnătură electronică , este necesară o funcție hash . $h:\mathbb {N} \mapsto \{0,1\}^{k}\subset \mathbb {Z} _{n^{2}}^{*}$

Semnătura mesajului

Pentru a semna un mesaj , este necesar să se calculeze $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} }$

Semnătura electronică va fi o pereche de . $(s_{1},s_{2})$

Verificarea semnăturii

O semnătură este considerată valabilă dacă este îndeplinită următoarea condiție:

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

Proprietăți omomorfe

O caracteristică distinctivă a criptosistemului Peye este homomorfismul acestuia . Deoarece funcția de criptare este omomorfă aditiv, se pot scrie următoarele identități [2] :

Adăugarea omomorfă a textelor clare

Produsul a două texte cifrate va fi decriptat ca sumă a textelor lor simple respective,

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

Înmulțind textul cifrat cu obținem suma textelor clare corespunzătoare,

g^{m_{2)}

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

Înmulțirea omomorfă a textelor clare

Un text cifrat ridicat la puterea altui text cifrat va fi decriptat ca produs a două texte clare,

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

În general, ridicarea textului cifrat la o putere va fi decriptată ca produs al textului simplu prin ,

k

k

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

Generalizare

În 2001, Ivan Damgard și Mads Jurik au propus o generalizare [6] a criptosistemului Peye. Pentru a face acest lucru, se propune efectuarea de calcule modulo , unde , este un număr natural . Algoritmul modificat arată astfel: $n^{s+1}$ $n=p*q$ $s$

Generare cheie

În mod aleatoriu și independent unul de celălalt, sunt alese două numere prime mari și . $p$ $q$
si se calculeaza . $n=pq$ $\lambda =\operatorname {lcm} (p-1,q-1)$
Se alege un număr astfel încât , unde este un număr coprim cunoscut cu și . $g\in \mathbb {Z} _{n^{s+1}}^{*}$ $g=(1+n)^{j}x{\bmod {n}}^{s+1}$ $j$ $n$ $x\în H$
Folosind teorema chineză a restului , se alege astfel încât și . De exemplu, poate fi egal cu criptosistemul original Paye. $d$ $d{\bmod {n}}\in \mathbb {Z} _{n}^{*}$ $d=0{\bmod {\lambda ))$ $d$ $\lambda$

Cheia publică este o pereche . $(n,g)$
Cheia privată este . $d$

Criptare

Să presupunem că vrem să criptăm un mesaj , unde . $m$ $m\in \mathbb {Z} _{n^{s)}$
Alegem un număr aleatoriu astfel încât . $r$ $r\in \mathbb {Z} _{n^{s+1}}^{*}$
Calculăm textul cifrat . $c=g^{m}\cdot r^{n^{s}}{\bmod {n}}^{s+1}$

Decriptare

Să presupunem că avem un text cifrat și vrem să-l decriptăm. $c\in \mathbb {Z} _{n^{s+1}}^{*}$
Noi calculăm . Dacă este într-adevăr un text cifrat, atunci sunt valabile următoarele egalități: . $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}}$
Folosim o versiune recursivă a mecanismului de decriptare a criptosistemului Peye pentru a obține . Deoarece produsul este cunoscut, putem calcula . $jmd$ $jd$ $m=(jmd)\cdot (jd)^{-1}\;bmod\;n^{s)$

Aplicație

Votul electronic

Folosind criptosistemul Peyet , este posibil să se organizeze alegeri între mai mulți candidați folosind următoarea schemă: [7] [8]

Să fie numărul de alegători și așa încât . $N$ $k\in \mathbb {N}$ $N<2^{k}$
Dacă alegătorul dorește să voteze pentru numărul candidatului , atunci el criptează numărul și trimite textul cifrat primit coordonatorului electoral. $i$ ${\displaystyle 2^{k(i-1)))$
Atunci când rezumă rezultatele alegerilor, coordonatorul decriptează produsul tuturor textelor cifrate primite de la alegători. Este ușor de observat că primii biți ai rezultatului vor da numărul de voturi exprimate pentru primul candidat, al doilea biți va da numărul de voturi exprimate pentru al doilea candidat și așa mai departe. $k$ $k$

Loteria electronică

Utilizând criptosistemul Paye, puteți organiza o loterie electronică după cum urmează: [7] [8]

Lăsați jucătorii să vrea să participe la loterie, fiecare are propriul bilet de loterie cu un număr unic . $N$ $n\in \{0,\dots ,N-1\}$
Fiecare jucător alege un număr aleatoriu, îl criptează și îl trimite organizatorului loteriei.
Pentru a calcula biletul „norocos”, organizatorul decriptează produsul tuturor textelor cifrate primite, primind în același timp suma numerelor aleatorii generate de jucători. Organizatorul loteriei anunță câștigătorul biletului cu numărul . $s$ $s{\bmod {n)}$

Este ușor de observat că toți participanții vor avea probabilități egale de câștig, chiar dacă jucătorii încearcă să falsifice rezultatul loteriei trimițând numere pre-preparate organizatorului. $n-1$

Moneda electronică

O altă trăsătură distinctivă a criptosistemului Peye este așa-numita auto- orbire . Acest termen se referă la capacitatea de a schimba textul cifrat fără a schimba textul simplu . Acest lucru poate fi utilizat în dezvoltarea sistemelor de monedă electronică, cum ar fi cash . Să presupunem că doriți să plătiți pentru un articol online, dar nu doriți să oferiți comerciantului numărul cardului dvs. de credit și, prin urmare, identitatea dvs. Ca și în cazul votului electronic, putem verifica validitatea unei monede electronice (sau a unui vot electronic) fără a dezvălui identitatea persoanei cu care este asociată în prezent.

Note

↑ Jonathan Katz, Yehuda Lindell, „Introduction to Modern Cryptography: Principles and Protocols”, Chapman & Hall/CRC, 2007
↑ 1 2 Varnovsky N. P., Shokurov A. V. „Encryption homomorphic”, 2007
↑ 1 2 Pascal Paillier, „Public-Key Cryptosystems Based on Composite Degree Residuosity Classes”, 1999
↑ Pierre-Alain Fouque și David Pointcheval, „Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks”, 2001
↑ Lan Nguyen, Rei Safavi-Naini, Kaoru Kurosawa, „A Provably Secure and Eﬃcient Veriﬁable Shuﬄe based on a Variant of the Paillier Cryptosystem”, 2006
↑ Jurik M., Damgård I. „O generalizare, o simplificare și unele aplicații ale sistemului probabilistic Public-Key al lui Paillier”, 1999
↑ 1 2 P.-A., Poupard G., Stern J., „Sharing Decryption in the Context of Voting or Loteries”, 2001
↑ 1 2 Jurik MJ, „Extensii la criptosistemul paillier cu aplicații la protocoale criptologice”, 2003

Literatură

Paillier P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes (English) // Advances in cryptology, EUROCRYPT'99. - 1999. - P. 223-238 . - ISBN 978-3-540-48910-8 . - doi : 10.1007/3-540-48910-X_16 . Arhivat din original pe 17 decembrie 2014.

Fouque P.-A., Poupard G., Stern J. Sharing Decryption in the Context of Voting or Loteries // 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 Extensii la criptosistemul mai bun cu aplicații la protocoale criptologice (engleză) // Public Key Cryptography. - 2003. - P. 119-136 .

Jurik M., Damgård I. O generalizare, o simplificare și unele aplicații ale sistemului probabilistic de cheie publică a lui Paillier // Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptosystems. - 2001. - P. 119-136 .

Varnovsky N. P., Shokurov A. V. Criptare homomorfă // Proceedings of ISP RAS. - 2007. - S. 27-36 . (Rusă)

Katz J., Lindell Y. Introducere în criptografia modernă: principii și protocoale. - Chapman & Hall / CRC, 2007. - P. 385-395. — ISBN 978-1584885511 .

Link -uri

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP