Asymetrická šifra ElGamal přímo vychází z Diffie-Hellmanova protokolu pro výměnu klíčů. Její bezpečnost je postavena na problému řešení diskrétního logaritmu.

Šifra ElGamal

Šifra ElGamal vychází z Diffie–Hellmanova protokolu výměny klíčů a byla představena Taherem Elgamalem v roce 1985. Na rozdíl od Diffie–Hellmanova protokolu nepřenáší jen jednu zprávu, která se později slouží jako klíč symetrické šifry, ale může sloužit jako standardní šifrovací algoritmus pro přenos libovolného počtu zpráv. Jeho bezpečnost je založena ryze na problému diskrétního logaritmu (tj. neuplatňuje se problém faktorizace celých čísel).

Princip

Předpokládejme, že máme velké číslo p (nejlépe prvočíslo o minimálně 512 bitech), které určuje tzv. řád multiplikativní cyklické grupy. Číslo p musí navíc splňovat požadavek, že u čísla (p-1) jsou prvočísla v kanonickém rozkladu na prvočísla relativně velká. Dále máme číslo g, které je tzv. generátorem multiplikativní cyklické grupy. Aby tak bylo, musí číslo g z matematického hlediska splňovat tuto podmínku (pokud je p prvočíslo):

g ∈ {2, 3, ..., p-2}, ∀q ∈ P, q∣(p-1) platí g(p-1)/q mod p ≠ 1

kde P značí množinu všech prvočísel.

Inicializace

Předpokládáme, že Alice započne komunikaci. Musí provést následující kroky

  1. Alice vygeneruje dvojici p a g (řád a generátor cyklické grupy).

  2. Alice vygeneruje tajné přirozené číslo x, kde 1 < x < (p-1). A vypočte číslo h, což je výsledek výpočtu:

    h = gx mod p

    (Zde je pointa bezpečnosti šifry, vyčíslení diskrétního logaritmu, který by určil tajné x, je extrémně časově náročný)

  3. Alice zveřejní (zašle přes nezabezpečený kanál) čísla h, g a p, tato čísla představují veřejný klíč Alice. Privátní klíč Alice je číslo x.

Šifrování

Předpokládejme, že Bob obdrží veřejný klíč alice (čísla h, g a p) a chystá se ji odeslat zašifrovanou zprávu.

  1. Bob vygeneruje tajné přirozené číslo y, kde 1 < y < (p-1). A vypočte číslo c1, což je výsledek výpočtu:

    c1 = gy mod p

  2. Bob vypočítá společné tajné číslo s pomocí výpočtu:

    s = hy mod p

  3. Bob chce (celou dobu) odeslat tajnou zprávu m, kde 1 < m < p-1. Vypočte tedy číslo c2 jako:

    c2 = ms mod p

  4. Bob odešle Alici dvojici (c1, c2).

Dešifrování

Poté, co Alice obdrží dvojici (c1, c2) provede dešifrování, tj. získání zprávy m, následujícím způsobem:

  1. Alice vypočítá společné tajné číslo s pomocí výpočtu:

    s = c1x mod p

  2. Alice vypočítá multiplikativní inverzi s-1 mod p.

  3. Alice vypočítá dešifruje zprávu m pomocí výpočtu:

    m = c2s-1 mod p

Programování

Upravte ukázku u Diffie–Hellmanovy výměny klíčů tak, aby z ní byla šifra ElGamal.