Kryptosystem Goldwasser - Micali
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. december 2019; checks kræver 3 redigeringer .Goldwasser-Micali Cryptosystem ( GM ) er et kryptografisk system med offentlig nøgle udviklet af Shafi Goldwasser og Silvio Micali i 1982 . GM er det første probabilistiske krypteringsskema med offentlig nøgle, der beviseligt er sikkert under standard kryptografiske antagelser. GM-kryptosystemet er imidlertid ineffektivt, fordi chifferteksten kan være hundredvis af gange længere end den krypterede meddelelse. For at bevise et kryptosystems sikkerhedsegenskaber introducerede Goldwasser og Micali det meget brugte begreb semantisk sikkerhed .
Goldwasser og Micali blev tildelt Turing-prisen i 2012 for skabelsen af et probabilistisk kryptosystem som et banebrydende arbejde, der har haft en betydelig indflydelse på moderne kryptografi .
Grundlæggende
Konceptet om modstand mod et IND-CPA- angreb blev først foreslået af Goldwasser og Micali. De kaldte dette begreb semantisk vedholdenhed. Det ligger i det faktum, at chifferteksten ikke tillader nogen nyttig information om klarteksten (bortset fra længden af selve klarteksten) at lække til enhver angriber med polynomielt begrænsede computerressourcer. Goldwasser og Micali fandt ud af, at meddelelser i mange applikationer kan indeholde a priori - oplysninger, der er nyttige til at organisere angreb. For eksempel kan chifferteksten kun indeholde én simpel instruktion (f.eks. "køb" eller "sælg", eller navnet på en af flere kandidater ved afstemning). Goldwasser og Micali har påpeget, at offentlige nøglekryptosystemer baseret på direkte anvendelse af envejsfunktioner med en hemmelighed som regel meget svagt skjuler indholdet af sådanne meddelelser.
Ejendom (semantisk persistens). Alle almindelige tekstelementer, der kan beregnes effektivt ud fra en given chiffertekst, kan beregnes effektivt uden den.
Goldwasser og Micali har foreslået et probabilistisk krypteringsskema , der har denne egenskab. Den krypterer hele beskeden bit for bit, og al den kompleksitet, der er forbundet med at finde en enkelt krypteret bit i teksten c , er at kontrollere, om nummeret c tilhører sættet eller sættet
Beskrivelse af algoritmen
Nøglegenerering
For at indstille nøgleparametrene skal Alice udføre følgende handlinger:
- Vælg to tilfældige tal og , der opfylder bitbetingelsen
- Beregn værdi
- Udtræk et tilfældigt heltal , der opfylder betingelsen ( Jacobi-symboler ) (Således , men .)
- Beskriv parret som en offentlig nøgle, og hold parret hemmeligt som en privat nøgle.
Kryptering
For at sende en streng til Alice gør Bob følgende:
{ }
Bob sender en besked til Alice
Dekryptering
Efter at have modtaget tuple , udfører Alice følgende operationer:
{
}
Tidskompleksitet af algoritmen
For at kryptere en meddelelse, der består af bits, skal du udføre bitvise handlinger. Dette udtryk er et skøn over algoritmens tidskompleksitet. Graden af udvidelse af denne algoritme er lig med : en bit af den almindelige tekst svarer til en bit af chifferteksten.
Da beregningen af Legendre-symbolet modulo og modulo forudsatte, at bitvise operationer skal udføres , er bitvise operationer påkrævet for at dechifrere tuplen . Dette udtryk er et skøn over tidskompleksiteten af dekryptering.
Styrken af GM-kryptosystemet
Krypteringsalgoritmen i GM-krypteringssystemet kan betragtes som en fejlfri randomiseret algoritme: tilfældige operationer i krypteringsalgoritmen kan ikke forvrænge chifferteksten og har samtidig følgende vigtige egenskaber.
Nul bits i kildeteksten er jævnt fordelt over sættet og enere over sættet . Begge fordelinger er ensartede, fordi for den nulbit, der er indeholdt i den originale tekst, betyder kvadrering en afbildning af gruppen på sættet , og for en enhedsbit er multiplikation af et element i mængden med et tal en afbildning fra mængden til sæt .
Referencer
- Mao V. Moderne kryptografi : Teori og praksis / oversættelse. D. A. Klyushina - M. : Williams , 2005. - 768 s. — ISBN 978-5-8459-0847-6