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.
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 .
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).
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:
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:
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.
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 — .
Algoritmus generování klíčů funguje následovně:
Zpráva dána . Šifrovací algoritmus funguje následovně
Po obdržení šifrovaného textu a použití soukromého klíče :
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 .
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 .
Řekněme, že máme skupinu objednávek . V souladu s tím - .
Generování klíčůAlgoritmus generování klíčů funguje následovně:
Zpráva dána . Šifrovací algoritmus funguje následovně
Po obdržení šifrovaného textu a použití soukromého klíče :
Kryptosystém Cramer-Shope je odolný vůči útokům založeným na adaptivně zvoleném šifrovém textu za následujících podmínek:
Důkaz : Abychom dokázali větu, budeme předpokládat, že existuje protivník, který může porušit protokol, a ukážeme, že pokud je splněna podmínka hashovací funkce, dostaneme rozpor s podmínkou v Diffie-Hellmanově problému. Vstup do našeho pravděpodobnostního algoritmu je dán z rozdělení nebo . Na povrchní úrovni bude konstrukce vypadat takto: postavíme simulátor, který vytvoří společnou distribuci skládající se z crackerovy vize kryptosystému po sérii útoků a skrytého bitu b generovaného generačním orákulem (není součástí crackerovo vidění, před ním skryté). Myšlenka důkazu: ukážeme, že pokud je vstup distribucí , pak bude simulace úspěšná a protivník bude mít netriviální výhodu v uhodnutí náhodného bitu b. Ukážeme také, že pokud je vstup distribucí z , pak vize nepřítele nezávisí na a , a proto bude převaha nepřítele zanedbatelná (menší než inverzní polynom). Odtud můžeme sestavit rozlišovací znak distribuce a : spustíme simulátor kryptosystému (tisky ) a cracker (tisky ) současně a tiskne , pokud a jinak.
Schéma simulace generování klíčů je následující:
Je vidět, že generování klíče simulátoru se liší od generování klíče v protokolu (tam ).
Simulace dešifrování . Postupuje se stejně jako v protokolu, s tím rozdílem, že
Simulace šifrování . Zadaným vstupem simulátor vybere náhodnou hodnotu , vypočítá a odešle výstup . Důkaz věty nyní vyplyne z následujících dvou lemmat.
Lemma 1. Pokud je simulátoru přiděleno rozdělení od , pak společné rozdělení útočníkovy vize kryptosystému a skrytého bitu je statisticky nerozeznatelné od skutečného útoku na kryptosystém.
Lemma 2. Pokud simulátor dostane distribuci od , pak distribuce skrytého bitu nezávisí na distribuci crackerova vidění.