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ų ${\displaystyle p\,}$, ir tegu ${\displaystyle \alpha \,}$ yra generojantis grupę ${\displaystyle Z_{p}^{*}\,}$ elementas. Pasirenkame skaičių ${\displaystyle a\,}$, ${\displaystyle 1\leq a\leq p-2\,}$, suskaičiuojame ${\displaystyle \alpha ^{a}{\pmod {p}}\,}$.

Viešas raktas: ${\displaystyle K_{v}=<p,\alpha ,\alpha ^{a}>\,}$

Privatus raktas: ${\displaystyle K_{p}=<a>\,}$

Šifravimas/dešifravimas

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

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

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

Pastaba: ${\displaystyle \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