ElGamal

Malline:Lähteetön ElGamal on julkisen avaimen salausmenetelmä, joka perustuu Diffie-Hellman avaimenvaihtojärjestelmään. Menetelmä perustuu logaritmien laskentaan ja sen on esittänyt Taher Elgamal vuonna 1985.^[1]

ElGamal-menetelmää 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-allekirjoitusmenetelmän variantti, mutta sitä ei tule sekoittaa ElGamal-algoritmiin.Malline:Lähde

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 ${0, 1, . . ., q - 1}$ .

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 ${0, 1, . . ., q - 1}$ .

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^{x y}} = \frac{m \cdot g^{x y}}{g^{x y}} = 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}$ .