Criptosistemul Goldwasser-Micali
În criptologie , criptosistemul Goldwasser-Micali este un criptosistem dezvoltat de Shafi Goldwasser și Silvio Micali în 1982 . Este primul criptosistem dovedit sigur în Modelul Standard , o avansare permisă de introducerea de către Goldwasser și Micali a noțiunii actuale de securitate semantică ca joc de securitate , participând la nașterea securității dovedibile în criptologia modernă. Din aceste motive, Goldwasser și Micali au primit premiul Turing în 2012.
În ciuda meritelor sale teoretice și a importanței sale în istoria criptologică recentă, criptosistemul Goldwasser-Micali nu este utilizat în practică: este mult mai puțin eficient decât alternativele și securitatea semantică este insuficientă pentru multe aplicații.
Descriere
Sintaxa generală
Criptosistemul Goldwasser și Micali este o schemă de criptare cu cheie publică : este alcătuit din trei algoritmi :
- un algoritm probabilistic de generare a cheii care ia ca intrare un parametru de securitate și returnează o pereche constând dintr-o cheie privată și cheia publică corespunzătoare;(sk,pk){\ displaystyle ({\ mathsf {sk}}, {\ mathsf {pk}})}
- un algoritm de criptare, de asemenea probabilistic, care ia ca intrare parametrul de securitate, un mesaj clar și o cheie publică și returnează un mesaj criptat;
- și un algoritm de decriptare determinist care ia ca intrare parametrul de securitate, un mesaj criptat și o cheie privată și returnează un mesaj.
Detaliu algoritmi
Generarea de chei criptografice
Generarea cheilor se face după cum urmează:
- Se generează două numere prime și distincte, notăm . Dimensiunea și se determină pe baza setărilor de securitate din dovada de securitate (a se vedea mai jos).p{\ displaystyle p}q{\ displaystyle q \,}nu=pq{\ displaystyle n = pq}p{\ displaystyle p}q{\ displaystyle q}
- Se găsește un număr întreg ale cărui simboluri Jacobi în ceea ce privește și să fie egale cu -1, adică nu este un reziduu pătratic modulo ni .z∈(Z/(nu))×{\ displaystyle z \ in \ mathbb {(} \ mathbb {Z} / (n)) ^ {\ times}}p{\ displaystyle p}q{\ displaystyle q}p{\ displaystyle p}q{\ displaystyle q}
- Algoritmul revine .(sk=p,pk={nu,z}){\ displaystyle ({\ mathsf {sk}} = p, {\ mathsf {pk}} = \ {n, z \})}
Pentru pasul 2, există practic două metode. Prima metodă este de a desena la întâmplare și de a verifica simbolul său Jacobi; în principiu, unul din patru are proprietatea dorită. A doua metodă este de a repara mod , care asigură că se potrivește.
z{\ displaystyle z}(p,q)≡3{\ displaystyle (p, q) \ equiv 3}4{\ displaystyle 4}z=nu-1{\ displaystyle z = n-1}
Criptare pe un bit
Fie un mesaj de un bit , adică . Pentru a cripta acest mesaj,
m{\ displaystyle m}m∈{0,1}{\ displaystyle m \ in \ {0,1 \}}
- Algoritmul extrage uniform un număr întreg din .y{\ displaystyle y}(Z/(nu))×{\ displaystyle (\ mathbb {Z} / (n)) ^ {\ times}}
- Algoritmul returnează mesajul criptat vs.=zmy2modnu{\ displaystyle c = z ^ {m} y ^ {2} {\ bmod {n}}}
Pentru a cripta un mesaj mai lung, format din mai mulți biți, fiecare bit este criptat independent. Deci, dacă mesajul criptat corespunzător este de unde este criptat fiecare .
m=(m1,...,mk)∈{0,1}k{\ displaystyle m = (m_ {1}, \ dotsc, m_ {k}) \ in \ {0,1 \} ^ {k}}vs.=(vs.1,...,vs.k)∈(Z/(nu))k{\ displaystyle c = (c_ {1}, \ dotsc, c_ {k}) \ in \ mathbb {(} \ mathbb {Z} / (n)) ^ {k}}vs.eu{\ displaystyle c_ {i}}meu{\ displaystyle m_ {i}}
Acest mod de a face lucrurile este responsabil pentru lățimea de bandă scăzută a criptosistemului. Independența dintre fiecare cifru permite, de asemenea, unui atacator să reordoneze membrii fără a decripta vreodată: aceasta este o vulnerabilitate de maleabilitate , care nu este surprinsă de modelul de securitate semantic (vezi discuția de mai jos).
vs.{\ displaystyle c}
Decriptare pe un bit
Algoritmul de decriptare constă din:
vs.{\ displaystyle c}
- Dacă este un reziduu pătratic modulo , se returnează 1. În caz contrar se returnează 0.vs.{\ displaystyle c}nu{\ displaystyle n}
Acest pas este eficient, deoarece algoritmul de decriptare primește cheia privată care dă factorizarea . Dacă cifrul corespunde unui mesaj de mai mulți biți , fiecare este descifrat pentru a da bitul mesajului clar.
sk{\ displaystyle {\ mathsf {sk}}}nu{\ displaystyle n}vs.=(vs.1,...,vs.k){\ displaystyle c = (c_ {1}, \ dotsc, c_ {k})}vs.eu{\ displaystyle c_ {i}}meu{\ displaystyle m_ {i}}
Securitate
Securitatea semantică (IND-CPA) a Criptosistem Goldwasser și Micali a fost redus, în Modelul Standard , la dificultatea de modulo problema pătratice reziduurilor - adică ipoteza că este dificil să se determine dacă un număr este un rest modulo pătratică . Această dovadă este din punct de vedere istoric prima de acest fel și a contribuit la dezvoltarea noțiunii de securitate dovedibilă în criptologie.
nu{\ displaystyle n}vs.{\ displaystyle c}nu{\ displaystyle n}
Când factorizarea a se cunoaște, problema residuality este ușor, acest lucru este exact ceea ce a descris algoritmul de decriptare în secțiunea anterioară nu. În prezent (2018) aceasta este doar o condiție suficientă și nu este exclus faptul că există un algoritm eficient pentru a rezolva problema rezidualității pătratice, deși astăzi nu sunt cunoscute.
nu{\ displaystyle n}
Cel mai cunoscut atac (în 2018) constă astfel în calcularea factorizării , care determină modul de generare a cheilor pentru acest algoritm: a rezista unui atacator clasic și trebuie să fie individual suficient de mare pentru a evita o factorizare de către ECM (astfel ) și produsul lor trebuie să ofere suficientă rezistență la cei mai buni algoritmi de factorizare generică, în special la site- ul numărului de corp . Pentru un nivel clasic de securitate pe 128 de biți, acesta corespunde . Confruntat cu un atacant cuantic , algoritmul lui Shor oferă factorizarea în timp polinomial și, prin urmare, nu există parametri care să facă criptosistemul sigur în acest context.
nu{\ displaystyle n}p{\ displaystyle p}q{\ displaystyle q}p≈q{\ displaystyle p \ approx q}nu≈23072{\ displaystyle n \ approx 2 ^ {3072}}nu{\ displaystyle n}
Maleabilitate și omomorfism
Criptosistemul Goldwasser-Micali nu este sigur împotriva modelelor de atacatori mai puternici: are doar securitate semic (IND-CPA). În special, după cum sa menționat într-o secțiune anterioară, există atacuri de maleabilitate care permit unui adversar să manipuleze cifrele într-un mod nedetectabil. Existența unor astfel de atacuri arată că criptosistemul nu atinge securitatea IND-CCA, adică este generic vulnerabil la atacurile cu un cifru ales . Aceste observații sunt desigur anacronice, deoarece modelele corespunzătoare au fost dezvoltate ulterior și precis pentru a surprinde limitele acestui sistem.
Un alt punct de vedere asupra aceluiași fenomen este acela că criptosistemul Goldwasser-Micali este parțial omomorf : dacă sunt doi biți, respectiv criptate , apoi decriptate . Cu alte cuvinte, exclusivitatea sau funcția este calculabilă omomorf pe acest criptosistem.
m1,m2{\ displaystyle m_ {1}, m_ {2}}vs.1,vs.2{\ displaystyle c_ {1}, c_ {2}}vs.1×vs.2modnu{\ displaystyle c_ {1} \ times c_ {2} {\ bmod {n}}}m1⊕m2{\ displaystyle m_ {1} \ oplus m_ {2}}
Note și referințe
Note
-
Conform (Dent 2008), criptosistemul Rabin și cel al Goldwasser-Micali sunt responsabili pentru conștientizarea, în anii 1990, a necesității de a formaliza (și a demonstra) securitatea schemelor criptografice. A se vedea, de asemenea (Goldwasser 2002).
-
Un algoritm de criptare determinist nu poate fi sigur semantic.
-
Simbolul Jacobi fiind o funcție multiplicativă , avem .(znu)=(zp)(zq)=+1{\ displaystyle \ left ({\ frac {z} {n}} \ right) = \ left ({\ frac {z} {p}} \ right) \ left ({\ frac {z} {q}} \ dreapta) = + 1}
-
Pentru fiecare bit al cifrului, bitul mesajului este transmis .1/Buturuga2nu{\ displaystyle 1 / \ log _ {2} n}
-
Algoritmul clasic constă în calcularea simbolului Legendre modulo și modulo , care necesită în esență algoritmul lui Euclid .p{\ displaystyle p}q{\ displaystyle q}
-
criptosistem lui Rabin (1979) precede cu câțiva ani, Goldwasser-Micali și a fost prezentat cu o dovadă a echivalenței între calculul rădăcinilor pătrate modulo și factoring . A se vedea (Dent 2008) pentru o discuție.nu{\ displaystyle n}nu{\ displaystyle n}
Referințe
-
(în) Kazue Sako , „Schema de criptare Goldwasser-Micali” în Enciclopedia Henk CA van Tilborg de criptografie și securitate , Springer SUA,2005( ISBN 9780387234731 , DOI 10.1007 / 0-387-23483-7_177 , citit online ) , p. 241–242
-
(în) S. Goldwasser și S. Micali, „Criptare probabilistică și cum să joci poker mintea păstrând secret toate informațiile părtinitoare” în Procesele STOC '82 ale celui de-al 14-lea Simpozion anual ACM pe teoria calculelor ,1982, p. 365-377.
-
(en) S. Goldwasser și S. Micali, „ Criptare probabilistică ” , J. Comput. Syst. Știință. , vol. 28, n o 21984, p. 270-299 ( DOI 10.1016 / 0022-0000 (84) 90070-9 ).
-
(în) Jonathan Katz și Yehuda Lindell, Introducere în criptografia modernă, ediția a II-a , Boca Raton, Chapman și Hall ,2014, 583 p. ( ISBN 978-1-4665-7026-9 , citit online ) , „Definirea criptării securizate prin calcul”.
-
(en) Seung Geol Choi, Dana Dachman-Soled, Tal Malkin și Hoeteck Wee, " Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One " , Theory of Cryptography Conference (CBT) ,2008( DOI 10.1007 / 978-3-540-78524-8_24 , citiți online ).
-
(ro) Alexander W. Dent , „A Brief History of Provably-Secure Public-Key Encryption” , în progres în criptologie - AFRICACRYPT 2008 , Springer Berlin Heidelberg,11 iunie 2008( ISBN 9783540681595 , DOI 10.1007 / 978-3-540-68164-9_24 , citit online ) , p. 357-370
-
(în) Shafi Goldwasser , " Fundamente matematice ale criptografiei moderne: perspectivă de complexitate de calcul " , arXiv: cs / 0212055 ,30 noiembrie 2002( citiți online , consultat pe 24 august 2018 )
-
(în) „ Shafi Goldwasser - Laureat al Premiului AM Turing ” pe amturing.acm.org (accesat la 24 august 2018 )
-
(în) „ Silvio Micali - Laureat al Premiului AM Turing ” pe amturing.acm.org (accesat la 24 august 2018 )
-
(in) Association for Computing Machines (ACM) , „ ACM Turing Award 2012 ” pe youtube.com ,19 iunie 2013(accesat pe 24 august 2018 )
-
(în) Benjamin Justus , „ Distribuția reziduurilor pătratice și a non-reziduurilor în tipul de criptosistem Goldwasser-Micali ” , Journal of Mathematical Cryptology , vol. 8, n o 21 st ianuarie 2014( ISSN 1862-2976 și 1862-2984 , DOI 10.1515 / jmc-2013-0001 , citit online , consultat 24 august 2018 )
-
(în) Benjamin Justus , „ Distribuția reziduurilor pătratice și a non-reziduurilor în tipul de criptosistem Goldwasser-Micali. II ” , Journal of Mathematical Cryptology , vol. 9, n o 21 st ianuarie 2015( ISSN 1862-2976 și 1862-2984 , DOI 10.1515 / jmc-2014-0004 , citit online , accesat la 24 august 2018 )
-
(în) Rene Peralta și Eiji Okamoto, „ Unele probleme combinatorii de importanță pentru criptografie ” , Proceedings of the IEICE 1996 Symposium on Cryptography and Information Security ,1996( citește online )
-
(în) Abbas Acar , Hidayet Aksu , A. Selcuk Uluagac și Mauro Conti , " Un sondaj privind schemele de criptare homomorfă: teorie și implementare " , arXiv: 1704.03578 [cs] ,11 aprilie 2017( citiți online , consultat pe 24 august 2018 )
-
(în) Kun Peng , Colin Boyd și Ed Dawson , „A Multiplicative homomorphic Sealed-Bid Auction based on Goldwasser-Micali Encryption” în Lecture Notes in Computer Science , Springer Berlin Heidelberg,2005( ISBN 9783540290018 , DOI 10.1007 / 11556992_27 , citit online ) , p. 374-388
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">