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(\mathrm{mod}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,\dots ,p-1\}$ – pranešimą $A$. $B$ pasirenka atsitiktinai skaičių $k$, $1\le k\le p-2$ ir apskaičiuoja $\gamma ={\alpha }^{k}modp$, $\delta =m({\alpha }^a{)}^{k}modp$. 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}modp$
2. apskaičiuoja $({\gamma }^{-a})\delta modp$ ir atstato $m$.

Pastaba: ${\gamma }^{-a}\delta \equiv {\alpha }^{-ak}m{\alpha }^{ak}\equiv m(\mathrm{mod}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