Cramer-Shoup kryptosystem

Cramer – Shoup-systemet er en  offentlig nøglekrypteringsalgoritme . Den første algoritme, der viste sig modstandsdygtig over for angreb baseret på adaptivt valgt chiffertekst . Designet af Ronald Kramer og Victor Shoup i 1998. Algoritmens sikkerhed er baseret på Diffie-Hellman-diskriminationsantagelsen . Det er en udvidelse af ElGamal-ordningen , men i modsætning til ElGamal-ordningen er denne algoritme uoverskuelig(En hacker kan ikke erstatte chifferteksten med en anden chiffertekst, der ville blive dekrypteret til en tekst relateret til originalen, dvs. være en funktion af den). Denne robusthed opnås ved brug af en universel envejs-hash-funktion og yderligere beregninger, hvilket resulterer i en chiffertekst, der er dobbelt så stor som ElGamal-ordningen.

Valgt chiffertekstangreb

Et kryptografisk angreb, hvor en kryptoanalytiker indsamler information om en chiffer ved at gætte chifferteksten og dekryptere den med en ukendt nøgle. Kryptanalytikeren kan bruge dekryptering flere gange for at få den dekrypterede chiffertekst. Ved hjælp af de modtagne data kan han forsøge at gendanne den hemmelige nøgle til dekryptering. Et chiffertekstangreb kan være adaptivt eller ikke-adaptivt.

Det var velkendt, at mange udbredte kryptosystemer var sårbare over for et sådant angreb, og i mange år mente man, at angrebet var upraktisk og kun af teoretisk interesse. Tingene begyndte at ændre sig i slutningen af ​​1990'erne, især da Daniel Bleichenbacher demonstrerede et praktisk chiffertekstbaseret angreb på SSL -servere ved hjælp af en form for RSA -kryptering .

Ikke-adaptivt angreb

I et ikke-adaptivt angreb bruger kryptanalytikeren ikke resultaterne af tidligere dekrypteringer, det vil sige, at chiffertekster er valgt på forhånd. Sådanne angreb kaldes frokostangreb (frokosttid eller CCA1).

Adaptivt angreb

I tilfælde af et adaptivt angreb vælger kryptoanalytikeren adaptivt en chiffertekst, der afhænger af resultaterne af tidligere dekrypteringer (CCA2).

Modstandsdygtighed over for adaptive angreb kan ses på eksemplet med spillet:

• Nøglegenereringsalgoritmen lanceres i krypteringsskemaet med den tilsvarende nøglelængde leveret som input.
• Modstanderen fremsætter en række vilkårlige anmodninger til dekrypteringsoraklet og dekrypterer således de chiffertekster, han selv vælger.
• Modstanderen vælger to beskeder og sender dem til krypteringsoraklet.
• Chifferoraklet vælger tilfældigt en bit og krypterer derefter , som sendes til modstanderen (møntkastet for at vælge bit er skjult for modstanderen).
• Modstanderen fremsætter igen en række vilkårlige anmodninger til dekrypteringsoraklet med den eneste begrænsning, at anmodningen skal være forskellig fra den besked, den modtog fra krypteringsoraklet.
• Modstanderen giver en bit - den forventede værdi af biten valgt af krypteringsoraklet i trin 4. Hvis , så anses modstanderens overlegenhed for at være lig med .

Diffie-Hellman-diskriminationsproblemet

Der er flere tilsvarende formuleringer af Diffie-Hellman-diskriminationsproblemet. Den, vi skal bruge, ser sådan ud.

Lade være en gruppe af orden , hvor er et stort primtal. Også  - . Og der er to fordelinger:

• Fordeling af tilfældige firdobler .
• Fordelingen af ​​firdobler , hvor - er tilfældige, og for tilfældige .

En algoritme, der løser Diffie-Hellman-problemet, er en probabilistisk algoritme , der effektivt kan skelne mellem de anførte to distributioner. Det vil sige, at en algoritme, der tager en af ​​de to fordelinger som input, skal returnere 0 eller 1, og har også en tendens til 0.

Diffie-Hellman-diskriminationsproblemet er svært, hvis der ikke eksisterer en sådan polynomiel probabilistisk algoritme.

Grundlæggende skema

Lad os have en rækkefølge , hvor er et stort primtal. Beskeder er elementer . Vi bruger også en generisk familie af envejs-hash-funktioner, der kortlægger lange bitstrenge til elementer , hvor  — .

Nøglegenerering

Nøglegenereringsalgoritmen fungerer som følger:

• Alice genererer tilfældige og tilfældige elementer
• Alice beregner .
• En hash-funktion vælges fra den universelle familie af envejs-hash-funktioner. Den offentlige nøgle er , den private nøgle er .

Kryptering

Meddelelse givet . Krypteringsalgoritmen fungerer som følger

• Bob vælger tilfældigt .
• Bob beregner følgende værdier:
  • ;
  • ;
  • , hvor er en universel envejs-hash-funktion;
  • ;
• Bob sender chifferteksten til Alice.

Dekryptering

Efter at have modtaget chifferteksten og brugt den private nøgle :

• Alice beregner .
• Alice tjekker tilstanden . Hvis betingelsen ikke er opfyldt, afsluttes protokollen med dekrypteringsfejl. Ellers vises en meddelelse .

Protokol korrekthed

Lad os tjekke rigtigheden af ​​krypteringsskemaet (dekryptering af den krypterede besked giver den samme besked). I betragtning af det og , har vi . Også og . Derfor lykkes dekrypteringskontrollen, og den oprindelige meddelelse vises .

Forenklet diagram

Forskelle fra grundskemaet

For at opnå sikkerhed mod ikke-adaptive angreb (og kun dem), kan du forenkle protokollen betydeligt uden at bruge . Ved kryptering bruger vi , og ved dekryptering tjekker vi at .

Et eksempel på et forenklet kredsløb

Lad os sige, at vi har en rækkefølge . Følgelig  - .