Kryptosystém Goldwasser - Micali

Goldwasser-Micali Cryptosystem ( GM ) je kryptografický systém s veřejným klíčem, který vyvinuli Shafi Goldwasser a Silvio Micali v roce 1982 . GM je první pravděpodobnostní šifrovací schéma s veřejným klíčem, které je prokazatelně bezpečné za standardních kryptografických předpokladů. GM kryptosystém je však neefektivní, protože šifrovaný text může být stokrát delší než zašifrovaná zpráva. Aby dokázali bezpečnostní vlastnosti kryptosystému, zavedli Goldwasser a Micali široce používaný pojem sémantické bezpečnosti .

Goldwasser a Micali získali v roce 2012 Turingovu cenu za vytvoření pravděpodobnostního kryptosystému jako průkopnické dílo, které mělo významný dopad na moderní kryptografii .

Základy

Koncept odolnosti proti útoku IND-CPA byl poprvé navržen Goldwasserem a Micalim. Tento koncept nazvali sémantická persistence. Spočívá v tom, že šifrovaný text neumožňuje uniknout žádné užitečné informace o otevřeném textu (kromě délky samotného otevřeného textu) žádnému útočníkovi s polynomiálně omezenými výpočetními prostředky. Goldwasser a Micali zjistili, že v mnoha aplikacích mohou zprávy obsahovat a priori informace, které jsou užitečné pro organizaci útoků. Šifrovaný text může například obsahovat pouze jeden jednoduchý pokyn (například „koupit“ nebo „prodat“ nebo jméno jednoho z více kandidátů při hlasování). Goldwasser a Micali poukázali na to, že kryptosystémy s veřejným klíčem založené na přímé aplikaci jednosměrných funkcí s tajemstvím zpravidla velmi slabě skrývají obsah takových zpráv.

Vlastnost (sémantická perzistence). Všechny prvky otevřeného textu, které lze efektivně vypočítat z daného šifrového textu, lze efektivně vypočítat i bez něj.

Goldwasser a Micali navrhli pravděpodobnostní schéma šifrování , které má tuto vlastnost. Šifruje celou zprávu bit po bitu a veškerá složitost spojená s nalezením jediného zašifrovaného bitu v textu c spočívá v kontrole, zda číslo c patří do množiny nebo množiny.

Popis algoritmu

Generování klíčů

K nastavení klíčových parametrů musí Alice provést následující operace:

1. Vyberte dvě náhodná čísla a , splňující bitovou podmínku
2. Vypočítejte hodnotu
3. Extrahujte náhodné celé číslo , které splňuje podmínku ( Jacobiho symboly ) (Tak , ale .)
   
4. Popište pár jako veřejný klíč a udržujte pár v tajnosti jako soukromý klíč.

Šifrování

Chcete-li poslat řetězec Alici , Bob provede následující:

{ }

Bob pošle zprávu Alici

Dešifrování

Po přijetí n-tice Alice provede následující operace:

{

}

Časová složitost algoritmu

Chcete-li zašifrovat zprávu sestávající z bitů, musíte provést bitové operace. Tento výraz je odhadem časové složitosti algoritmu. Stupeň rozšíření tohoto algoritmu je roven : jeden bit prostého textu odpovídá bitu šifrovaného textu. Protože výpočet Legendreho symbolu modulo a modulo za předpokladu, že musí být provedeny bitové operace, jsou k dešifrování n-tice vyžadovány bitové operace . Tento výraz je odhadem časové složitosti dešifrování.

Síla GM kryptosystému

Šifrovací algoritmus v kryptosystému GM lze považovat za bezchybný randomizovaný algoritmus: náhodné operace v šifrovacím algoritmu nemohou zkreslit šifrovaný text a zároveň mají následující důležité vlastnosti.

Nulové bity ve zdrojovém textu jsou rovnoměrně rozmístěny v sadě a jedničky v sadě . Obě distribuce jsou jednotné, protože pro nulový bit obsažený v původním textu znamená kvadratura mapování skupiny na množině a pro jednotkový bit je vynásobení prvku množiny číslem mapováním z množiny na množinu. nastavit .

Reference

• Mao V. Moderní kryptografie : Teorie a praxe / přel. D. A. Klyushina - M. : Williams , 2005. - 768 s. — ISBN 978-5-8459-0847-6