ElGamal

Kohteesta Wikipedia
Loikkaa: valikkoon, hakuun

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[muokkaa | muokkaa wikitekstiä]

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

Avainten generointi tapahtuu seuraavasti:

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

Liisa valitsee satunnaisen luvun joukosta .

Liisa laskee ryhmän alkion .

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

Roope valitsee satunnaisen alkion lukujoukosta .

Tämän jälkeen hän laskee ryhmän alkiot ja .

Roope lähettää Liisalle salakielisen viestin .

Salauksen purku toimii seuraavasti:

Liisa laskee ryhmän alkion .

Nyt .

Ryhmän kertaluvun 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[muokkaa | muokkaa wikitekstiä]

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 .

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