ElGamal
Wikipedia
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.
[muokkaa] 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 = gx.
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 c1 = gy ja .
Roope lähettää Liisalle salakielisen viestin (c1,c2).
Salauksen purku toimii seuraavasti:
Liisa laskee ryhmän G alkion .
Nyt .
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.
[muokkaa] 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. Dekryptauksessa käytetty laskukaava voidaan nimittäin kirjoittaa muotoon .
Toisin kuin RSA-menetelmässä, laskentaa ei voida nopeuttaa kiinalaista jäännöslausetta käyttäen.