Cryptosystem Goldwasser - Micali

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. december 13-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Goldwasser-Micali Cryptosystem ( GM ) egy nyilvános kulcsú kriptográfiai rendszer , amelyet Shafi Goldwasser és Silvio Micali fejlesztett ki 1982 -ben . A GM az első nyilvános kulcsú valószínűségi titkosítási séma , amely a szabványos kriptográfiai feltételezések mellett bizonyíthatóan biztonságos . A GM titkosítási rendszer azonban nem hatékony, mivel a titkosított szöveg több százszor hosszabb lehet, mint a titkosított üzenet. A kriptorendszer biztonsági tulajdonságainak bizonyítására Goldwasser és Micali bevezette a szemantikai biztonság széles körben használt fogalmát .

Goldwasser és Micali 2012 - ben elnyerték a Turing-díjat egy valószínűségi titkosítási rendszer létrehozásáért, mint úttörő munkát, amely jelentős hatást gyakorolt a modern kriptográfiára .

Alapok

Az IND-CPA támadásokkal szembeni ellenállás koncepcióját először Goldwasser és Micali javasolta. Ezt a fogalmat szemantikai perzisztenciának nevezték. Ez abban rejlik, hogy a titkosított szöveg nem engedi, hogy a nyílt szöveggel kapcsolatos hasznos információk (kivéve magának a nyílt szövegnek a hosszát) kiszivárogjanak a polinomiálisan korlátozott számítási erőforrásokkal rendelkező támadókhoz. Goldwasser és Micali úgy találta, hogy sok alkalmazásban az üzenetek eleve olyan információkat tartalmazhatnak, amelyek hasznosak a támadások megszervezéséhez. Például a rejtjelezett szöveg csak egy egyszerű utasítást tartalmazhat (például "vegyen" vagy "eladjon", vagy szavazáskor a több jelölt egyikének nevét). Goldwasser és Micali rámutattak arra, hogy a nyilvános kulcsú titkosítási rendszerek, amelyek az egyirányú funkciók közvetlen alkalmazásán alapulnak titokban, általában nagyon gyengén elrejtik az ilyen üzenetek tartalmát.

Tulajdonság (szemantikai perzisztencia). Minden egyszerű szöveges elem, amely egy adott rejtjelezett szövegből hatékonyan kiszámítható, hatékonyan kiszámítható anélkül.

Goldwasser és Micali egy valószínűségi titkosítási sémát javasoltak, amely rendelkezik ezzel a tulajdonsággal. A teljes üzenetet bitenként titkosítja, és a c szövegben egyetlen titkosított bit megtalálásával járó bonyolultság annak ellenőrzése, hogy a c szám a halmazhoz vagy a halmazhoz tartozik-e. $QR_{N}$ $J(N)=\left\{x\in \mathbb {Z} _{N}^{\ast },\left({\frac {x}{N))\right)=1\right \}$

Az algoritmus leírása

Kulcsgenerálás

A kulcsparaméterek beállításához Alice - nek a következő műveleteket kell végrehajtania:

Válasszon két véletlen számot és , a bitfeltételnek megfelelően $p$ $q$ $|p|=|q|$
Számítsa ki az értéket $N = pq$
Vonjunk ki egy véletlenszerű egész számot , amely kielégíti a feltételt ( Jacobi szimbólumok ) (Így , de .) $y$ $\left({\frac {y}{p}}\right)=\left({\frac {y}{q}}\right)=-1$
$y\in J(N)$ $y\notin QR_{N}$
Írja le a párt nyilvános kulcsként, és őrizze meg a párt titkos kulcsként. $(N,y)$ $(p,q)$

Titkosítás

Ha karakterláncot szeretne küldeni Alice -nek , Bob a következőket teszi: $m=b_{1}b_{2}\dots b_{l}$
$for(i=1,2\pontok,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 üzenetet küld Alice-nek $E_{N}(m)\leftarrow (c_{1},c_{2}\dots ,c_{l}).$

Dekódolás

Miután megkapta a tuple -t , Alice a következő műveleteket hajtja végre: $(c_{1},c_{2},\dots ,c_{l})$
$for(i=1,2\pontok,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}).$

Az algoritmus időbeli összetettsége

A bitekből álló üzenet titkosításához bitenkénti műveleteket kell végrehajtania . Ez a kifejezés az algoritmus időbeli összetettségének becslése. Ennek az algoritmusnak a kiterjesztésének mértéke egyenlő : a sima szöveg egy bitje a titkosított szöveg egy bitjének felel meg. Mivel a Legendre szimbólum modulo és modulo számítása feltette , hogy bitenkénti műveleteket kell végrehajtani , bitenkénti műveletekre van szükség a leíró megfejtéséhez . Ez a kifejezés a visszafejtés időbonyolultságának becslése. $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})$

A GM kriptorendszer erőssége

A GM titkosítási rendszerben a titkosítási algoritmus egy hibamentes randomizált algoritmusnak tekinthető: a titkosítási algoritmus véletlenszerű műveletei nem torzíthatják el a rejtjelezett szöveget, ugyanakkor a következő fontos tulajdonságokkal rendelkeznek.

A forrásszöveg nulla bitjei egyenletesen oszlanak el a halmazban , egyesek pedig a halmazban . Mindkét eloszlás egységes, mivel az eredeti szövegben található nulla bitre a négyzetre vonás a csoport leképezését jelenti a halmazon , egységbit esetén pedig a halmaz egy elemének számmal való szorzása a halmazból a meg . $QR_{N}$ $J_{N}\backslash QR_{N}$
$\mathbb {Z} _{N}^{\ast }$ $QR_{N}$ $QR_{N}$ $y$ $QR_{N}$ $J_{N}\backslash QR_{N}$

Hivatkozások

Mao V. Modern kriptográfia : Elmélet és gyakorlat / ford. D. A. Klyushina - M .: Williams , 2005. - 768 p. — ISBN 978-5-8459-0847-6

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya