ElGamal

Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan.

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

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

Lähteet