Šifrovací ElGamal , nebo šifrování El Gamal (nebo systém El Gamal ) je protokol asymetrické kryptografie vynalezený Taher ElGamal v roce 1984 a postaven z problému diskrétního logaritmu .
Tento protokol používá svobodný software GNU Privacy Guard, jehož poslední verze implementují dokonce i svou verzi na eliptické křivky . Na rozdíl od šifrování RSA nikdy nebylo chráněno patentem .
Zakládající článek Tahera Elgamala představuje šifrovací protokol , ale také digitální podpis , který navzdory své podobnosti (oba jsou postaveny na problému diskrétního logaritmu ) nelze zaměňovat. Společnosti Tento článek pouze s šifrovacím protokolem .
Algoritmus je popsán pro konečnou cyklickou skupinu, ve které je obtížný problém s rozhodnutím Diffie-Hellman (DDH). Podrobnější informace jsou uvedeny v části Odolnost proti útokům CPA .
Můžeme si všimnout, že DDH je silnější pracovní hypotéza než diskrétní logaritmus, protože platí, pokud je problém diskrétního logaritmu někdy obtížný. Existují také skupiny, kde je problém DDH snadný, ale kde neexistuje efektivní algoritmus pro řešení diskrétního logaritmu .
Jelikož se jedná o asymetrické šifrovací schéma , kryptosystém se skládá ze tří ( pravděpodobnostních ) algoritmů : GenClefs , Encrypt a Decrypt .
Pro ilustraci budeme předpokládat, že Bob chce poslat zprávu Alici . Ale tato zpráva obsahuje citlivé informace, takže Bob nechce, aby jim někdo jiný než Alice rozuměl. Bob tedy zašifruje jeho zprávu.
Protože asymetrická šifrovací schémata jsou obecně pomalejší než jejich symetrické analogy, šifrování ElGamal se v praxi často používá jako součást hybridního šifrování , jako je jeho specifikace PGP.
Jedním ze způsobů pohledu na toto šifrovací schéma je vytvoření paralely s protokolem výměny klíčů Diffie-Hellman . Šifrovací algoritmus pak spočívá v odeslání zprávy šifrované pomocí jednorázového maskou pod sdíleným klíčem , který může být vypočítána podle Alici, protože ona má (viz obrázek na protější straně).
Prvním krokem v šifrovacím schématu je vytvoření páru klíčů: veřejného klíče a tajného klíče . První bude použit k šifrování zpráv a druhý k jejich dešifrování.
Bob má tedy přístup k veřejnému klíči Alice . Aby mohl zašifrovat zprávu zakódovanou jako prvek skupiny , Bob začíná nakreslením náhodného čísla a použije jej k pokrytí zprávy při výpočtu . Aby bylo možné Alice na dešifrování zprávy, bude Bob přidat do této části obsahu zprávy o nebezpečí: .
Nakonec bude šifra složena z těchto dvou částí : a Bob pošle Alici.
Díky přístupu do a do může Alice tak vypočítat:
A proto je schopen zprávu najít .
Pohled na veřejné informace ; uvědomujeme si, že jsou viditelné pouze prvky, nikoli exponenty (zde x a s ). Neformálně si můžeme všimnout, že problém diskrétního logaritmu lze interpretovat jako skutečnost, že je obtížné najít například tajnou informaci, která by umožnila najít zprávu.
Přesněji řečeno, je to Diffie-Hellmann (nebo DDH ) rozhodovací problém, který umožňuje zaručit sémantickou bezpečnost schématu.
Demonstrace SníženíZa předpokladu, že máme protivníka proti sémantické bezpečnosti šifrování ElGamal, který vyhrává s nezanedbatelnou pravděpodobností ε . Poté bude možné postavit proti DDH protivníka , což by bylo v rozporu s předpokládanou obtížností tohoto problému. Tato redukce, kterou jsme právě popsali, vytvoří bezpečnostní důkaz schématu.
K vybudování tohoto oponenta, který bude dále označován jako „ redukce “, se předpokládá získání trojitého DDH : jeho účelem je pak rozhodnout, zda nebo se nezanedbatelnou pravděpodobností. K tomu má rozhraní s výše popsaným protivníkem tváří v tvář sémantické bezpečnosti kryptosystému ElGamal.
Snížení proto pošle veřejný klíč protivníkovi proti ElGamalu . Při vytváření výzvy pro oponenta proti sémantické bezpečnosti kryptosystému bude redukce odeslána jako šifrovaná: pro dle jeho výběru. Pokud je triplet někdy trojicí DDH , to znamená, že , pak by byl vytvořen jako platná šifra pro ElGamal s ohledem na veřejný klíč . Na druhou stranu, pokud je exponent náhodný, pak soupeř proti ElGamalu nebude schopen odlišit dvě zprávy výzvy jiným způsobem než reakcí na náhodu.
Musíme jen odpovědět na „1“ (odpovídá skutečnosti, že vyzyvatel pro DDH poslal trojici DDH), pokud náš soupeř uspěje, a „0“ (odpovídá skutečnosti, že vyzyvatel pro DDH poslal trojnásobný náhodný) jinak.
AnalýzaNyní budeme omezovat na tu výhodu vyhrát naší redukce z výhoda e údajného soupeře proti našemu plánu.
Začneme tím, že máme dva případy: buď výzva zaslaná naším vyzyvatelem je skutečný triplet DDH , nebo je to triplet nakreslený jednotně.
Máme tedy výhodu, která zůstává významná: k dosažení stejného zabezpečení mezi DDH a naším kryptosystémem stačí, aby problém DDH zůstal zabezpečený s dalším bezpečnostním bitem.
V modelech s útočníkem s větším výkonem, například pod vybranými šifrovacími útoky, není kryptosystém ElGamal bezpečný kvůli své tvárnosti ; skutečně, vzhledem k šifře zprávy , můžeme sestrojit šifru , která bude pro zprávu platná .
Tato tvárnost (jedná se o multiplikativní homomorfismus ) na druhé straně umožňuje použít ji například pro elektronické hlasování .
Existují však varianty, které zajišťují zabezpečení proti vybraným šifrovým útokům, jako je kryptosystém Cramer-Shoup, který lze považovat za rozšíření šifry ElGamal.
Pro příklad můžeme vzít skupinu s generátorem g = 5 ( Varování : toto není bezpečná skupina, tyto hodnoty byly vzaty pouze k vytvoření jednoduchého příkladu).
Možný veřejný klíč by proto mohl být :, a jako tajný klíč .
Protože šifrování je pravděpodobnostní algoritmus , existují různé možné výstupy pro stejnou zprávu. Možná šifra pro zprávu 42 by tedy mohla být (58086963, 94768547) , ale také (83036959, 79165157) pro rizika r rovna 6689644 a 83573058 .
Pokud však provedeme výpočet pro naše dvě čísla, dostaneme 42 na výstupu.