ElGamal kriptosistema

ElGamal kriptosistema yra viešo rakto kriptosistema. Jos saugumas remiasi diskretaus logaritmo problemos sprendimo sudėtingumu.

Raktų parinkimo algoritmas

Pasirenkame didelį pirminį skaičių $p\,$, ir tegu $\alpha\,$ yra generojantis grupę $Z_p^*\,$ elementas. Pasirenkame skaičių $a\,$, $1 \le a \le p-2\,$, suskaičiuojame $\alpha^a \pmod{p}\,$.

Viešas raktas: $K_v = <p, \alpha, \alpha^a>\,$

Privatus raktas: $K_p = <a>\,$

Šifravimas/dešifravimas

Tegu $B$ nori perduoti $m \in \{0, 1, \ldots, p-1\}\,$ – pranešimą $A\,$. $B\,$ pasirenka atsitiktinai skaičių $k\,$, $1 \le k \le p-2\,$ ir apskaičiuoja $\gamma = \alpha^k\ mod\ p\,$, $\delta=m(\alpha^a)^k\ mod\ p\,$. Gautas šifras $c = (\gamma, \delta)\,$. $B\,$ perduoda $c\,$ $A\,$.

$A\,$ dešifruoja šifrą $c\,$ taip:

1. naudojant privatų raktą $a\,$, suskaičiuoja $\gamma^{p-a-1}\ mod\ p\,$
2. apskaičiuoja $(\gamma^{-a})\delta \ mod\ p\,$ ir atstato $m\,$.

Pastaba: $\gamma^{-a}\delta \equiv \alpha^{-ak}m\alpha^{ak} \equiv m \pmod{p}\,$

Literatūra

• A. Menezes, P. van Oorschot, S. Vanstone, 1996, Handbook of Applied Cryptography

Kitos viešo rakto kriptosistemos

• Rivest-Shamir-Adleman kriptosistema, RSA
• Merkle-Hellman kriptosistema
• Rabin kriptosistema