Exponenciální šifra

Exponenciální šifra je polyalfabetická šifra. Šifra je velmi odolná vůči kryptoanalýze. Je založena na principu modulárního umocňování. Bezpečnost šifry je zajištěna složitostí řešení diskrétního logaritmu.

Princip

Definujme modul m jako prvočíslo. Zvolme šifrovací klíč e jako celé kladné číslo nesoudělné s m-1. Šifrovaný text (dále jen ŠT) získáme umocněním bloku otevřeného textu (dále jen OT) modulárně umocněného klíčem. Bezpečnost šifry je zajištěna tím, že opačná operace (nalézt základ umocněného čísla) je pro útočníka výpočetně složitý problém.

Při dešifrování je znám šifrovací klíč e. Dešifrovací klíč d lze spočítat pomocí vzorce $d*e\equiv 1{\pmod {m-1}}$. OT text se dešifruje pomocí umocnění ŠT dešifrovacím klíčem d. Matematicky lze dešifrování popsat s využitím malé Fermatovy věty jako

$|c^{d}|_{m}=|(p^{e})^{d}|_{m}=|p^{ed}|_{m}=|p^{k(m-1)+1}|_{m}=|{p^{(m-1)}}^{k}*p|_{m}=|p|_{m}$

• c - blok ŠT
• p - blok OT
• m - modulo
• e - šifrovací klíč
• d - dešifrovací klíč
• $ed=k(m-1)+1$, kde k je nějaké celé číslo

Šifrování

Převod OT do ŠT probíhá v následujících krocích.

• Seskupíme OT do n-tic písmen. Jako OT si v tomto příkladě volíme OT = WIKI. OT seskupíme do dvojic písmen.
• Písmena převedeme do číselného ekvivalentu (A => 00, B => 01, ..., Y => 24, Z => 25).
• Zvolíme velikost bloku.
  • Protože písmena jsou zakódována maximálně pomocí dvou číslic, tak velikost bloku musí být násobkem dvou.
  • V příkladě voláme blok velikosti s = 2. Proto velikost zakódovaného bloku bude 4 číslice.
• Kódy čísel zřetězíme do bloků („WIKI“ => 2208 1008).
• Zvolíme modul m (m je prvočíslo), tak že m > 2525. (m = 2647)
  • Číslo 2525 reprezentuje maximální hodnotu bloku (písmena ZZ).
  • Kdyby bylo modulo m menší než 2525, tak by se poškodila přenášená informace. Tudíž by nešlo ŠT jednoznačně dešifrovat.
• Zvolíme šifrovací klíč e, tak že gcd(e, m-1) = 1. (e = 31)
• Po blocích převádíme OT podle předpisu $c=|p^{e}|_{m}$ na ŠT.
  • $|2208^{31}|_{2647}=2048$
  • $|1008^{31}|_{2647}=1044$
• ŠT = 2048 1044

Dešifrování

Převod ŠT do OT probíhá v následujících krocích.

• Známe ŠT, modulo i šifrovací klíč. (ŠT = 2048 1044, m = 2647, e = 31)
• Dešifrovací klíč dopočítáme d pomocí pravidla $d*e\equiv 1{\pmod {m-1}}$. (d = 1195)
  • K výpočtu lze použít například rozšířený Eukleidův algoritmus.
• Spočítáme OT podle předpisu $p=|c^{d}|_{m}$.
  • $|2048^{1195}|_{2647}=2208$
  • $|1044^{1195}|_{2647}=1008$
• OT = WIKI