ElGamal

ElGamal-algoritmi on epäsymmetrinen julkisen avaimen salausalgoritmi, joka perustuu Diffie-Hellman avaimenvaihtojärjestelmään. Sen on esittänyt Taher Elgamal vuonna 1984. ElGamal-algoritmia käyttävät mm. GNU Privacy Guard -ohjelmisto, PGP:n uudemmat versiot ja monet muut salausjärjestelmät. DSA (Digital Signature Algorithm) on ElGamal -signatuuriskeeman variantti, mutta sitä ei tule sekoittaa ElGamal-algoritmiin.

ElGamal voidaan määrittää missä tahansa syklisessä ryhmässä G. Sen turvallisuus riippuu diskreetin logaritmin laskemisesta ryhmässä G.

Algoritmi

ElGamal koostuu kolmesta komponentista: avainten generointi, salausalgoritmi ja salauksen purkualgoritmi.

Avainten generointi tapahtuu seuraavasti:

Liisa valitsee jonkin syklisen ryhmän $G$. Olkoon $q$ ryhmän $G$ kertaluku eli alkioiden lukumäärä. Tämä kertaluku määrää Liisan käyttämän salakirjoitusjärjestelmän avaimen pituuden.

Seuraavaksi Liisa etsii jonkin ryhmän $G$ primitiivisen alkion $g$. Primitiivisen alkion ominaisuus on se, että jokainen syklisen ryhmän $G$ alkio voidaan esittää tämän alkion potenssina. Tämän eksponentin laskemista kutsutaan ryhmän $G$ diskreetin logaritmin probleemaksi.

Liisa valitsee satunnaisen luvun $x$ joukosta $\lbrace 0,1,...,q-1\rbrace$.

Liisa laskee ryhmän $G$ alkion $h=g^{x}$.

Liisa julkaisee käyttämänsä syklisen ryhmän $G$, sen kertaluvun $q$, primitiivisen alkion $g$ ja laskemansa alkion $h$. Nämä muodostavat hänen julkisen avaimensa. Luvun $x$ Liisa pitää salaisena avaimenaan.

Salausalgoritmi toimii seuraavasti:

Oletetaan, että Roope haluaa lähettää Liisalle salaisen viestin käyttäen Liisan julkistamaa salakirjoitusjärjestelmää.

Roope konvertoi aluksi viestinsä ryhmän $G$ alkioksi $m$ käyttäen jotain yksinkertaista ja tunnettua koodausta (vaikkapa ASCII-koodia).

Roope valitsee satunnaisen alkion $y$ lukujoukosta $\lbrace 0,1,...,q-1\rbrace$.

Tämän jälkeen hän laskee ryhmän $G$ alkiot $c_{1}=g^{y}$ ja $c_{2}=m\cdot h^{y}$.

Roope lähettää Liisalle salakielisen viestin $(c_{1},c_{2})$.

Salauksen purku toimii seuraavasti:

Liisa laskee ryhmän $G$ alkion $c_{2}(c_{1}^{x})^{-1}$.

Nyt $c_{2}(c_{1}^{x})^{-1}={\frac {m\cdot h^{y}}{g^{xy}}}={\frac {m\cdot g^{xy}}{g^{xy}}}=m$.

Ryhmän $G$ kertaluvun $q$ määräämää avaimen pituutta pitemmät viestit joudutaan pilkkomaan avaimen pituutta pienempiin osiin.

ElGamal-järjestelmää käytetään kuitenkin varsinaisten viestien salaamisen sijasta yleensä ns. avaimenvaihtojärjestelmänä. Tällöin lyhyt symmetrisen salauksen salakirjoitusjärjestelmän avain vaihdetaan ElGamal-järjestelmää käyttäen ja näin vaihdettua avainta käytetään sitten varsinaisten pitempien viestien salaamiseen.

Tehokkuus

Viestin salaamiseen ElGamal-järjestelmää käyttäen tarvitaan kaksi potenssiinkorotusta. Nämä potenssiinkorotukset voidaan kuitenkin laskea toisistaan riippumatta. Viestin purkamiseen tarvitaan kuitenkin vain yksi potenssiinkorotus. Desiferoinnissa käytetty laskukaava voidaan nimittäin kirjoittaa muotoon $c_{2}(c_{1}^{x})^{-1}=c_{2}c_{1}^{-x}=c_{2}c_{1}^{q-x}$.

Toisin kuin RSA-menetelmässä, laskentaa ei voida nopeuttaa kiinalaista jäännöslausetta käyttäen.