Exponenciální šifra

Exponenciální šifra je polyalfabetická šifra, která je velmi odolná vůči kryptoanalýze. Byla představena v roce 1978.

Princip

Exponenciání šifra je založena na elementárních principech umocňování obohacených o modulární aritmetiku. Její bezpečnost je zajišťena problémem diskrétního logaritmu, což je úloha přibližně stejně obtížná jako faktorizace.

Mějme zvolený šifrovací klíč e (nesoudělný s modulem). Pokud modulárně tímto klíčem umocňujeme blok OT, tak se jedná o výpočetně velmi jednoduchou operaci. Opačná operace - nalezení základu z umocněného čísla (diskrétní logaritmus) je pro útočníka velmi obtížný problém. Protože ale dešifrující strana zná e, tak nalezne dešifrovací klíč d podle vzorce "d*e ≡ 1 mod (m-1)". Tímto klíčem blok ŠT opět umocní a získá OT. Pokud si kroky šifrování a dešifrování rozepíšeme rozepíšeme, tak s využitím malé Fermatovy věty získáme:


\\vert c^d \\vert _{m} = \\vert (p^e)^d \\vert _{m} = \\vert p^{e \\cdot d} \\vert _{m} = \\vert p^{k \\cdot (m-1) + 1} \\vert _{m} = \\vert {p^{(m-1)}}^k \\cdot p  \\vert _{m} = \\vert p \\vert _{m}
c - blok ŠT
p - blok OT
m - modulo
d - dešifrovací klíč

Šifrování

  • Seskupíme OT do n-tic písmen.
  • Písmena přepíšeme na odpovídající kód (A => 00, B => 01, C => 02 ... Z => 25).
  • Zvolíme velikost bloku. (s = 2)
  • Kódy čísel zřetězíme do bloků („ZABA“ => 2500 0100).
  • Zvolíme modul m (m je prvočíslo), tak že m > 2525 („ZZ“, kdyby byl menší, tak by modulo poškodilo informaci (nešlo by jednoznačně dešifrovat)). (m = 2633 (blok ŠT bude mít 4 cifry))
  • Zvolíme šifrovací klíč e, tak že gcd(e, m) = 1. (e = 29)
  • Postupně převádíme OT (po blocích p) podle předpisu c = |pe|m
    • |250029|2633 = 0094
    • |010029|2633 = 0701
  • ŠT = 0094 0701

Dešifrování

  • Známe ŠT = 0094 0701, m = 2633, e = 29
  • Dopočítáme dešifrovací klíč d podle pravidla d*e ≡ 1 mod (m-1) například použitím rozšířeného Euklidova algoritmu. (d = 2269)
  • Spočítáme OT pomocí předpisu p = |c^d|m.
    • |00942269|2633 = 2500 => „ZA“
    • |07012269|2633 = 0100 => „BA“
  • OT = ZABA







Doporučujeme