ElGamal

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

Avainten generointi tapahtuu seuraavasti:

Liisa valitsee jonkin syklisen ryhmän ${\displaystyle G}$. Olkoon ${\displaystyle q}$ ryhmän ${\displaystyle 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 ${\displaystyle G}$ primitiivisen alkion ${\displaystyle g}$. Primitiivisen alkion ominaisuus on se, että jokainen syklisen ryhmän ${\displaystyle G}$ alkio voidaan esittää tämän alkion potenssina. Tämän eksponentin laskemista kutsutaan ryhmän ${\displaystyle G}$ diskreetin logaritmin probleemaksi.

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

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

Liisa julkaisee käyttämänsä syklisen ryhmän ${\displaystyle G}$, sen kertaluvun ${\displaystyle q}$, primitiivisen alkion ${\displaystyle g}$ ja laskemansa alkion ${\displaystyle h}$. Nämä muodostavat hänen julkisen avaimensa. Luvun ${\displaystyle 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 ${\displaystyle G}$ alkioksi ${\displaystyle m}$ käyttäen jotain yksinkertaista ja tunnettua koodausta (vaikkapa ASCII-koodia).

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

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

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

Salauksen purku toimii seuraavasti:

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

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

Ryhmän ${\displaystyle G}$ kertaluvun ${\displaystyle 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.

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