Cramer–Shoup kryptosystém

Systém Cramer – Shoup je šifrovací algoritmus  veřejného klíče . První algoritmus, který se ukázal jako odolný vůči útokům na základě adaptivně zvoleného šifrovaného textu . Navrhli Ronald Kramer a Victor Shoup v roce 1998. Zabezpečení algoritmu je založeno na diskriminačním předpokladu Diffie–Hellman . Jedná se o rozšíření schématu ElGamal , ale na rozdíl od schématu ElGamal je tento algoritmus neovladatelný(Hacker nemůže nahradit šifrovaný text jiným šifrovaným textem, který by byl dešifrován na text související s originálem, tj. byl by nějakou jeho funkcí). Této robustnosti je dosaženo použitím univerzální jednosměrné hashovací funkce a dodatečných výpočtů, jejichž výsledkem je šifrovaný text, který je dvakrát větší než schéma ElGamal.

Zvolený útok šifrovaného textu

Kryptografický útok, při kterém kryptoanalytik shromažďuje informace o šifře uhodnutím šifrového textu a jeho dešifrováním pomocí neznámého klíče. Kryptanalytik může použít dešifrovač několikrát, aby získal dešifrovaný šifrovaný text. Pomocí přijatých dat se může pokusit obnovit tajný klíč pro dešifrování. Útok pomocí šifrovaného textu může být adaptivní nebo neadaptivní.

Bylo dobře známo, že mnoho široce používaných kryptosystémů bylo vůči takovému útoku zranitelné, a po mnoho let se věřilo, že útok je nepraktický a má pouze teoretický význam. Věci se začaly měnit na konci 90. let, zvláště když Daniel Bleichenbacher předvedl praktický útok na SSL servery založený na šifrovaném textu pomocí formy šifrování RSA .

Neadaptivní útok

Při neadaptivním útoku kryptoanalytik nepoužívá výsledky předchozích dešifrování, to znamená, že šifrované texty jsou vybrány předem. Takové útoky se nazývají útoky v době oběda (polední čas nebo CCA1).

Adaptivní útok

V případě adaptivního útoku kryptoanalytik adaptivně vybere šifrovaný text, který závisí na výsledcích předchozích dešifrování (CCA2).

Odolnost vůči adaptivnímu útoku je vidět na příkladu hry:

• Algoritmus generování klíče se spouští v šifrovacím schématu s odpovídající délkou klíče zadanou jako vstup.
• Protivník předá dešifrovacímu orákulu řadu libovolných požadavků, čímž dešifruje šifrované texty podle svého výběru.
• Protivník vybere dvě zprávy a pošle je šifrovacímu orákulu.
• Šifrovací orákulum náhodně vybere bit , poté zašifruje , který je předán protivníkovi (hod mincí pro výběr bitu je protivníkovi skrytý).
• Protivník opět zadává řadu libovolných požadavků na dešifrovací orákulum s jediným omezením, že požadavek se musí lišit od zprávy, kterou obdržel od šifrovacího orákula.
• Protivník udává bit – očekávanou hodnotu bitu zvoleného šifrovacím orákulem v kroku 4. Jestliže , pak se převaha protivníka považuje za rovna .

Problém diskriminace Diffie-Hellmana

Existuje několik ekvivalentních formulací problému diskriminace Diffie-Hellman. Ten, který budeme používat, vypadá takto.

Dovolit být skupina pořadí , kde je velké prvočíslo. Také  - . A existují dvě distribuce:

• Rozdělení náhodných čtveřic .
• Rozdělení čtyřnásobků , kde - jsou náhodné, a pro náhodné .

Algoritmus, který řeší problém Diffie-Hellman, je pravděpodobnostní algoritmus , který dokáže efektivně rozlišovat mezi dvěma uvedenými distribucemi. To znamená, že algoritmus, který bere jedno ze dvou rozdělení jako vstup, by měl vrátit 0 nebo 1 a také má tendenci k 0.

Problém diskriminace Diffie-Hellman je obtížný, pokud žádný takový polynomiální pravděpodobnostní algoritmus neexistuje.

Základní schéma

Mějme skupinu pořadí , kde je velké prvočíslo. Zprávy jsou prvky . Používáme také obecnou rodinu jednosměrných hašovacích funkcí, které mapují dlouhé bitové řetězce na prvky , kde  — .

Generování klíčů

Algoritmus generování klíčů funguje následovně:

• Alice generuje náhodné a náhodné prvky
• Alice počítá .
• Hašovací funkce je vybrána z univerzální rodiny jednosměrných hašovacích funkcí. Veřejný klíč je , soukromý klíč je .

Šifrování

Zpráva dána . Šifrovací algoritmus funguje následovně

• Bob si náhodně vybere .
• Bob vypočítá následující hodnoty:
  • ;
  • ;
  • , kde je univerzální jednosměrná hašovací funkce;
  • ;
• Bob pošle šifrovaný text Alici.

Dešifrování

Po obdržení šifrovaného textu a použití soukromého klíče :

• Alice počítá .
• Alice zkontroluje stav . Pokud podmínka není splněna, protokol se ukončí selháním dešifrování. V opačném případě se zobrazí zpráva .

Správnost protokolu

Zkontrolujme si správnost šifrovacího schématu (dešifrování zašifrované zprávy dává stejnou zprávu). Vzhledem k tomu a máme . Také a . Proto je kontrola dešifrování úspěšná a zobrazí se původní zpráva .

Zjednodušený diagram

Rozdíly od základního schématu

Chcete-li dosáhnout zabezpečení proti neadaptivním útokům (a pouze jim), můžete výrazně zjednodušit protokol bez použití . Při šifrování používáme a při dešifrování kontrolujeme, že .

Příklad zjednodušeného obvodu

Řekněme, že máme skupinu objednávek . V souladu s tím  - .