Kryptosystém Goldwasser – Micali - Goldwasser–Micali cryptosystem

The Kryptosystém Goldwasser – Micali (GM) je asymetrický šifrovací algoritmus klíče vyvinutý uživatelem Shafi Goldwasser a Silvio Micali v roce 1982. GM se vyznačuje tím, že je první pravděpodobnostní schéma šifrování veřejného klíče, které je prokazatelně bezpečný za standardních kryptografických předpokladů. Nejedná se však o efektivní kryptosystém, protože šifry mohou být několik stokrát větší než původní prostý text. Aby dokázali bezpečnostní vlastnosti kryptosystému, navrhli Goldwasser a Micali široce používanou definici sémantická bezpečnost.

Základ

Kryptosystém GM je sémanticky bezpečné na základě předpokládané neřešitelnosti kvadratický problém reziduaity modulo kompozitní N = pq kde p, q jsou velké připraví. Tento předpoklad uvádí, že vzhledem k (X, N) je obtížné určit, zda X je kvadratický zbytek modulo N (tj., X = y² mod N pro některé y), když Jacobi symbol pro X je +1. Kvadratický problém zbytku lze snadno vyřešit s ohledem na faktorizaci N, zatímco nová kvadratická rezidua mohou být generována jakoukoli stranou, a to i bez znalosti této faktorizace. Kryptosystém GM využívá tuto asymetrii šifrováním jednotlivých bitů prostého textu buď jako náhodné kvadratické zbytky, nebo jako zbytky modulo N, vše se symbolem kvadratického zbytku +1. Příjemci používají faktorizaci N jako tajný klíč a dešifrujte zprávu testováním kvadratické rezidua přijatých hodnot šifrovacího textu.

Protože Goldwasser – Micali produkuje hodnotu velikosti přibližně |N| k zašifrování každého bitu prostého textu vede šifrování GM k podstatnému rozšíření šifrovacího textu. Aby se zabránilo faktorizace útoků, doporučuje se |N| být několik stovek bitů nebo více. Schéma tedy slouží hlavně jako důkaz konceptu a efektivnější prokazatelně bezpečné schémata jako např Elgamal byly vyvinuty od roku.

Protože šifrování se provádí pomocí pravděpodobnostního algoritmu, může daný prostý text pokaždé, když je zašifrován, vytvářet velmi odlišné šifrovací texty. To má významné výhody, protože brání protivníkovi v rozpoznávání zachycených zpráv jejich porovnáním se slovníkem známých šifrových textů.

Definice schématu

Goldwasser – Micali se skládá ze tří algoritmů: pravděpodobnostní algoritmus generování klíčů, který vytváří veřejný a soukromý klíč, pravděpodobnostní šifrovací algoritmus a deterministický dešifrovací algoritmus.

Schéma závisí na rozhodnutí, zda je daná hodnota X je čtvercový mod N, vzhledem k faktorizaci (str, q) z N. Toho lze dosáhnout pomocí následujícího postupu:

Vypočítat X_str = X mod str, X_q = X mod q.
Li ${ displaystyle x_ {p} ^ {(p-1) / 2} equiv 1 { pmod {p}}}$ a ${ displaystyle x_ {q} ^ {(q-1) / 2} equiv 1 { pmod {q}}}$ , pak X je kvadratický zbytek modN.

Generování klíčů

Modul použitý v šifrování GM je generován stejným způsobem jako v RSA kryptosystém. (Vidět RSA, podrobnosti generování klíče.)

Alice generuje dvě odlišné velké prvočísla str a q, náhodně a nezávisle na sobě.
Alice počítá N = p q.
Pak najde nějaké zbytky X takové, že Legendární symboly uspokojit ${ displaystyle left ({ frac {x} {p}} right) = left ({ frac {x} {q}} right) = - 1}$ a tudíž Jacobi symbol ${ displaystyle left ({ frac {x} {N}} right)}$ je +1. Hodnota X lze například najít výběrem náhodných hodnot a testováním dvou symbolů Legendre. Li str, q = 3 mod 4 (tj. N je Blum integer ), pak hodnota N - 1 je zaručeno, že má požadovanou vlastnost.

The veřejný klíč skládá se z (X, N). Tajným klíčem je faktorizace (str, q).

Šifrování zpráv

Předpokládejme, že si Bob přeje poslat zprávu m Alice:

Bob nejprve kóduje m jako řetězec bitů (m₁, ..., m_n).
Za každý kousek ${ displaystyle m_ {i}}$ , Bob generuje náhodnou hodnotu ${ displaystyle y_ {i}}$ ze skupiny jednotek moduloNnebo ${ displaystyle gcd (y_ {i}, N) = 1}$ . Vydá hodnotu ${ displaystyle c_ {i} = y_ {i} ^ {2} x ^ {m_ {i}} { pmod {N}}}$ .

Bob pošle šifrovací text (C₁, ..., C_n).

Dešifrování zprávy

Alice přijímá (C₁, ..., C_n). Může se vzchopit m pomocí následujícího postupu:

Pro každého ipomocí primární faktorizace (str, q), Alice určuje, zda je hodnota C_i je kvadratický zbytek; pokud ano, m_i = 0, jinak m_i = 1.

Alice odešle zprávu m = (m₁, ..., m_n).

Vlastnosti zabezpečení

Existuje jednoduchý snížení od rozbití tohoto kryptosystému po problém s určením, zda je náhodná hodnota modulo N se symbolem Jacobi +1 je kvadratický zbytek. Pokud je to algoritmus A rozbije kryptosystém, aby zjistil, zda je daná hodnota X je kvadratický zbytek modulo N, testujeme A zjistit, zda může rozbít kryptosystém pomocí (X,N) jako veřejný klíč. Li X tedy není zbytkem A by měl fungovat správně. Pokud však X je zbytek, pak každý „ciphertext“ bude jednoduše náhodný kvadratický zbytek, takžeA nemůže být správný více než v polovině času. Kromě toho tento problém je náhodně samo-redukovatelné, což zajišťuje, že pro daný N, každý veřejný klíč je stejně bezpečný jako každý jiný veřejný klíč.

Kryptosystém GM má homomorfní vlastnosti, v tom smyslu, že pokud C₀, C₁ jsou šifrování bitů m₀, m₁, pak C₀C₁ modN bude šifrování ${ displaystyle m_ {0} oplus m_ {1}}$ . Z tohoto důvodu se kryptosystém GM někdy používá ve složitějších kryptografických primitivech.

Reference

S. Goldwasser, S. Micali (1982). "Pravděpodobné šifrování a jak hrát mentální poker, utajení všech dílčích informací". Proc. 14. symposium o teorii práce na počítači: 365–377. doi:10.1145/800070.802212.
S. Goldwasser, S. Micali (1984). "Pravděpodobné šifrování". Journal of Computer and System Sciences. 28 (2): 270–299. doi:10.1016/0022-0000(84)90070-9.

Viz také

Kryptosystém Blum – Goldwasser