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\leq a\leq 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\leq k\leq 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