Kryptosystem Goldwasser - Micali

Goldwasser-Micali Cryptosystem ( GM ) är ett kryptografiskt system med offentlig nyckel utvecklat av Shafi Goldwasser och Silvio Micali 1982 . GM är det första probabilistiska krypteringsschemat med offentlig nyckel som bevisligen är säkert under standardkryptografiska antaganden. GM-kryptosystemet är dock ineffektivt eftersom chiffertexten kan vara hundratals gånger längre än det krypterade meddelandet. För att bevisa säkerhetsegenskaperna hos ett kryptosystem introducerade Goldwasser och Micali det allmänt använda begreppet semantisk säkerhet .

Goldwasser och Micali tilldelades 2012 års Turing Award för skapandet av ett probabilistiskt kryptosystem som ett banbrytande arbete som har haft en betydande inverkan på modern kryptografi .

Grunderna

Konceptet med motstånd mot en IND-CPA- attack föreslogs först av Goldwasser och Micali. De kallade detta begrepp semantisk uthållighet. Det ligger i det faktum att chiffertexten inte tillåter att någon användbar information om klartexten (förutom längden på klartexten själv) läcker till någon angripare med polynomiellt begränsade datorresurser. Goldwasser och Micali fann att i många applikationer kan meddelanden innehålla a priori- information som är användbar för att organisera attacker. Till exempel kan chiffertexten bara innehålla en enkel instruktion (till exempel "köp" eller "sälj", eller namnet på en av flera kandidater när man röstar). Goldwasser och Micali har påpekat att kryptosystem med offentlig nyckel baserade på direkt tillämpning av envägsfunktioner med en hemlighet, i regel mycket svagt döljer innehållet i sådana meddelanden.

Egenskap (semantisk persistens). Alla klartextelement som kan beräknas effektivt från en given chiffertext kan beräknas effektivt utan den.

Goldwasser och Micali har föreslagit ett probabilistiskt krypteringsschema som har denna egenskap. Den krypterar hela meddelandet bit för bit, och all komplexitet som är förknippad med att hitta en enda krypterad bit i texten c kontrollerar om numret c hör till mängden eller mängden

Beskrivning av algoritmen

Nyckelgenerering

För att ställa in nyckelparametrarna måste Alice utföra följande operationer:

1. Välj två slumpmässiga tal och , som uppfyller bitvillkoret
2. Beräkna värde
3. Extrahera ett slumpmässigt heltal som uppfyller villkoret ( Jacobi-symboler ) (Därmed , men .)
   
4. Beskriv paret som en offentlig nyckel och håll paret hemligt som en privat nyckel.

Kryptering

För att skicka en sträng till Alice gör Bob följande:

{ }

Bob skickar ett meddelande till Alice

Dekryptering

Efter att ha fått tuppeln utför Alice följande operationer:

{

}

Algoritmens tidskomplexitet

För att kryptera ett meddelande som består av bitar måste du utföra bitvisa operationer. Detta uttryck är en uppskattning av algoritmens tidskomplexitet. Graden av expansion av denna algoritm är lika med : en bit av ren text motsvarar en bit av chiffertexten. Eftersom beräkningen av Legendre-symbolen modulo och modulo förutsatt att bitvisa operationer måste utföras , krävs bitvisa operationer för att dechiffrera tupeln . Detta uttryck är en uppskattning av tidskomplexiteten för dekrypteringen.

Styrka hos GM-kryptosystemet

Krypteringsalgoritmen i GM-krypteringssystemet kan betraktas som en felfri randomiserad algoritm: slumpmässiga operationer i krypteringsalgoritmen kan inte förvränga chiffertexten och har samtidigt följande viktiga egenskaper.

Noll bitar i källtexten är jämnt fördelade över uppsättningen och ettor över uppsättningen . Båda fördelningarna är enhetliga, eftersom för nollbiten som finns i originaltexten betyder kvadrering en mappning av gruppen på mängden , och för en enhetsbit är multiplicering av ett element i mängden med ett tal en mappning från mängden till mängden ställ in .

Referenser

• Mao V. Modern kryptografi : Teori och praktik / övers. D. A. Klyushina - M . : Williams , 2005. - 768 sid. — ISBN 978-5-8459-0847-6