Cryptosystem Goldwasser - Micali

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 13. joulukuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Goldwasser-Micali Cryptosystem ( GM ) on julkisen avaimen salausjärjestelmä, jonka Shafi Goldwasser ja Silvio Micali kehittivät vuonna 1982 . GM on ensimmäinen julkisen avaimen todennäköisyyspohjainen salausjärjestelmä, joka on todistetusti turvallinen tavallisilla salausoletuksilla. GM-salausjärjestelmä on kuitenkin tehoton, koska salateksti voi olla satoja kertoja pidempi kuin salattu viesti. Todistaakseen kryptojärjestelmän turvallisuusominaisuudet Goldwasser ja Micali esittelivät laajalti käytetyn semanttisen turvallisuuden käsitteen .

Goldwasser ja Micali saivat vuoden 2012 Turing Award -palkinnon todennäköisyyspohjaisen salausjärjestelmän luomisesta uraauurtavana työnä, jolla on ollut merkittävä vaikutus nykyaikaiseen kryptografiaan .

Perusteet

Goldwasser ja Micali ehdottivat ensimmäisenä IND-CPA- hyökkäyksen vastustuskyvyn käsitettä . He kutsuivat tätä käsitettä semanttiseksi pysyvyydeksi. Se johtuu siitä, että salateksti ei salli mitään hyödyllistä tietoa selkeästä tekstistä (paitsi itse selkeän tekstin pituudesta) vuotaa kenellekään hyökkääjälle, jolla on polynomisesti rajalliset laskentaresurssit. Goldwasser ja Micali havaitsivat, että monissa sovelluksissa viestit voivat sisältää ennakkotietoja , joista on hyötyä hyökkäysten järjestämisessä. Esimerkiksi salateksti voi sisältää vain yhden yksinkertaisen ohjeen (esimerkiksi "osta" tai "myy" tai yhden useista ehdokkaista äänestäessä). Goldwasser ja Micali ovat huomauttaneet, että julkisen avaimen salausjärjestelmät, jotka perustuvat salaisen yksisuuntaisten toimintojen suoraan soveltamiseen, piilottavat pääsääntöisesti erittäin heikosti tällaisten viestien sisällön.

Ominaisuus (semanttinen pysyvyys). Kaikki selkotekstielementit, jotka voidaan laskea tehokkaasti tietystä salatekstistä, voidaan laskea tehokkaasti ilman sitä.

Goldwasser ja Micali ovat ehdottaneet todennäköisyyspohjaista salausjärjestelmää , jolla on tämä ominaisuus. Se salaa koko viestin bitti kerrallaan, ja kaikki yhden salatun bitin löytämiseen tekstistä c liittyvä vaikeus on tarkistaa, kuuluuko numero c joukkoon vai joukkoon. $QR_{N}$ $J(N)=\left\{x\in \mathbb {Z} _{N}^{\ast },\left({\frac {x}{N))\right)=1\oikea \}$

Algoritmin kuvaus

Avaimen luominen

Alicen on suoritettava seuraavat toiminnot asettaakseen tärkeimmät parametrit :

Valitse kaksi satunnaislukua ja bittiehdon mukaisesti $s$ $q$ $|p|=|q|$
Laske arvo $N = pq$
Poimi satunnainen kokonaisluku , joka täyttää ehdon ( Jacobin symbolit ) (Näin , mutta .) $y$ $\left({\frac {y}{p}}\right)=\left({\frac {y}{q}}\right)=-1$
$y\in J(N)$ $y\notin QR_{N}$
Kuvaile paria julkisena avaimena ja pidä pari salassa yksityisenä avaimena. ${\näyttötyyli (N,y)}$ $(p,q)$

Salaus

Bob lähettää merkkijonon Alicelle seuraavasti: $m=b_{1}b_{2}\dots b_{l}$
$for(i=1,2\pisteet ,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 lähettää viestin Alicelle $E_{N}(m)\leftarrow (c_{1},c_{2}\dots ,c_{l}).$

Salauksen purku

Saatuaan monikon Alice suorittaa seuraavat toiminnot: $(c_{1},c_{2},\dots ,c_{l})$
$for(i=1,2\pisteet ,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}).$

Algoritmin aika monimutkaisuus

Biteistä koostuvan viestin salaamiseksi sinun on suoritettava bittikohtaisia toimintoja. Tämä lauseke on arvio algoritmin aikamonimutkaisuudesta. Tämän algoritmin laajennusaste on yhtä suuri kuin : yksi bitti pelkkää tekstiä vastaa bittiä salattua tekstiä. Koska Legendre-symbolien modulo ja modulo laskenta edellytti, että bittikohtaiset toiminnot on suoritettava , bittikohtaiset toiminnot vaaditaan monikon tulkitsemiseen . Tämä lauseke on arvio salauksen purkamisen aikamonimutkaisuudesta. $l$ $O(l(\log _{2}N)^{2})$ $\log _{2}N$ $\log _{2}N$
$s$ $q$ $|p|=|q|=k$ $O_{B}(k^{2})$ $(c_{1},c_{2},\dots c_{k})$ $O_{B}((\log _{2}N)^{2})$

GM-salausjärjestelmän vahvuus

GM-salausjärjestelmän salausalgoritmia voidaan pitää virheettömänä satunnaistettuna algoritmina: salausalgoritmin satunnaiset toiminnot eivät voi vääristää salatekstiä, ja samalla niillä on seuraavat tärkeät ominaisuudet.

Lähdetekstin nollabitit jakautuvat tasaisesti joukolle ja ykköset joukkoon . Molemmat jakaumat ovat tasaisia, koska alkuperäisen tekstin sisältämälle nollabitille neliöinti tarkoittaa joukon ryhmän kuvaamista ja yksikköbitille joukon elementin kertominen luvulla on kuvaus joukosta asettaa . $QR_{N}$ $J_{N}\backslash QR_{N}$
$\mathbb {Z} _{N}^{\ast }$ $QR_{N}$ $QR_{N}$ $y$ $QR_{N}$ $J_{N}\backslash QR_{N}$

Viitteet

Mao V. Moderni kryptografia : teoria ja käytäntö / käännös. D. A. Klyushina - M .: Williams , 2005. - 768 s. — ISBN 978-5-8459-0847-6

Julkisen avaimen salausjärjestelmät

Algoritmit

Kokonaislukujen faktorointi	Benalon kryptojärjestelmä Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskreetti logaritmi	BLS Cramer - Shoup Diffie-Hellman-protokolla DSA ECDH Käyrä 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Salatun avaimen vaihto ElGamalin kaava allekirjoitusmalli MQV Schnorrin kaava SPEKE SRP STS
Kryptografia ristikoilla	NTRUEncrypt NTRUSign Oppimiseen perustuva avainten vaihto virheineen Allekirjoituspohjainen koulutus, jossa virheitä kehässä AUTUUS Uusi toivo
Muut	AE CEILIDH EPOC Piilotettu kenttäyhtälöt IES Lamportin allekirjoitus McEliece Merkle-Hellmanin selkärepun salausjärjestelmä Naccache-Stern selkäreppujen salausjärjestelmä Kolmivaiheinen protokolla XTR

Teoria

Diskreetti logaritmi elliptisellä käyrällä
Elliptinen kryptografia
Hash-pohjainen kryptografia
Ei-kommutatiivinen kryptografia
RSA ongelma
Yksisuuntainen toiminto salaisella sisäänkäynnillä

Standardit

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvanttisalaus

Aiheet

Sähköinen allekirjoitus
OAEP
Sormenjälki
PKI
luottamuksen verkko
Avaimen koko
Identiteettiin perustuva kryptografia
Postkvanttisalaus
OpenPGP-kortti