Criptosistem Goldwasser - Micali

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 13 decembrie 2019; verificările necesită 3 modificări .

Criptosistemul Goldwasser-Micali ( GM ) este un sistem criptografic cu cheie publică dezvoltat de Shafi Goldwasser și Silvio Micali în 1982 . GM este prima schemă de criptare probabilistică cu cheie publică care se dovedește sigură în ipotezele criptografice standard. Cu toate acestea, criptosistemul GM este ineficient deoarece textul cifrat poate fi de sute de ori mai lung decât mesajul criptat. Pentru a demonstra proprietățile de securitate ale unui criptosistem, Goldwasser și Micali au introdus noțiunea larg utilizată de securitate semantică .

Goldwasser și Micali au primit premiul Turing 2012 pentru crearea unui criptosistem probabilistic ca o lucrare de pionierat care a avut un impact semnificativ asupra criptografiei moderne .

Bazele

Conceptul de rezistență la un atac IND-CPA a fost propus pentru prima dată de Goldwasser și Micali. Ei au numit acest concept persistență semantică. Constă în faptul că textul cifrat nu permite nicio informație utilă despre textul simplu (cu excepția lungimii textului simplu) să se scurgă către orice atacator cu resurse de calcul limitate polinomial. Goldwasser și Micali au descoperit că în multe aplicații, mesajele pot conține informații a priori utile pentru organizarea atacurilor. De exemplu, textul cifrat poate conține o singură instrucțiune simplă (de exemplu, „cumpără” sau „vinde”, sau numele unuia dintre mai mulți candidați la vot). Goldwasser și Micali au subliniat că criptosistemele cu cheie publică bazate pe aplicarea directă a funcțiilor unidirecționale cu secret, de regulă, ascund foarte slab conținutul unor astfel de mesaje.

Proprietate (persistență semantică). Toate elementele de text simplu care pot fi calculate eficient dintr-un anumit text cifrat pot fi calculate eficient fără acesta.

Goldwasser și Micali au propus o schemă de criptare probabilistică care are această proprietate. Criptează întregul mesaj bit cu bit și toată complexitatea asociată cu găsirea unui singur bit criptat în textul c este verificarea dacă numărul c aparține setului sau setului $QR_{N}$ $J(N)=\left\{x\in \mathbb {Z} _{N}^{\ast },\left({\frac {x}{N))\right)=1\right \}$

Descrierea algoritmului

Generare cheie

Pentru a seta parametrii cheie, Alice trebuie să efectueze următoarele operații:

Alegeți două numere aleatoare și , satisfacând condiția de biți $p$ $q$ $|p|=|q|$
Calculați valoarea $N = pq$
Extrageți un număr întreg aleatoriu care satisface condiția ( simboluri Jacobi ) (Astfel , dar .) $y$ $\left({\frac {y}{p}}\right)=\left({\frac {y}{q}}\right)=-1$
$y\in J(N)$ $y\notin QR_{N}$
Descrieți perechea ca o cheie publică și păstrați perechea secretă ca o cheie privată. $(N,y)$ $(p,q)$

Criptare

Pentru a trimite un șir lui Alice , Bob face următoarele: $m=b_{1}b_{2}\dots b_{l}$
$pentru(i=1,2\dots ,l)$

{ }
$\quad x\leftarrow _{U}\mathbb {Z} _{N}^{\ast };$
$\quad if\,(b_{i}==0)\,\,c_{i}\leftarrow x^{2}(mod\,N);$
$\quad else\c_{i}\leftarrow yx^{2}(mod\,N);$

Bob îi trimite un mesaj lui Alice $E_{N}(m)\leftarrow (c_{1},c_{2}\dots ,c_{l}).$

Decriptare

După ce a primit tuplu , Alice efectuează următoarele operații: $(c_{1},c_{2},\dots ,c_{l})$
$pentru(i=1,2\dots ,l)$

{

$\quad if\,(c_{i}\in QR_{N})\,\,b_{i}\leftarrow 0;$
$\quad b_{i}\leftarrow 1;$

}

$set\ m\leftarrow (b_{1},b_{2},\dots ,b_{l}).$

Complexitatea temporală a algoritmului

Pentru a cripta un mesaj format din biți, trebuie să efectuați operații pe biți. Această expresie este o estimare a complexității în timp a algoritmului. Gradul de expansiune al acestui algoritm este egal cu : un bit din textul simplu corespunde unui bit din textul cifrat. Deoarece calculul simbolului Legendre modulo și modulo prevedea că trebuie efectuate operații pe biți, operațiuni pe biți sunt necesare pentru a descifra tuplu . Această expresie este o estimare a complexității de timp a decriptării. $l$ $O(l(\log _{2}N)^{2})$ $\log _{2}N$ $\log _{2}N$
$p$ $q$ $|p|=|q|=k$ $O_{B}(k^{2})$ $(c_{1},c_{2},\dots c_{k})$ $O_{B}((\log _{2}N)^{2})$

Puterea criptosistemului GM

Algoritmul de criptare din criptosistemul GM poate fi considerat un algoritm randomizat fără erori: operațiile aleatorii din algoritmul de criptare nu pot distorsiona textul cifrat și, în același timp, au următoarele proprietăți importante.

Zero biți din textul sursă sunt distribuiți uniform peste set , iar unii peste set . Ambele distribuții sunt uniforme, deoarece pentru bitul zero conținut în textul original, pătratul înseamnă o mapare a grupului de pe mulțime , iar pentru un bit de unitate, înmulțirea unui element al mulțimii cu un număr este o mapare de la mulțime la set . $QR_{N}$ $J_{N}\backslash QR_{N}$
$\mathbb {Z} _{N}^{\ast }$ $QR_{N}$ $QR_{N}$ $y$ $QR_{N}$ $J_{N}\backslash QR_{N}$

Referințe

Mao V. Criptografia modernă : Teorie și practică / transl. D. A. Klyushina - M . : Williams , 2005. - 768 p. — ISBN 978-5-8459-0847-6

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