Lähdekoodi sivulle ElGamal

{{lähteetön}}
'''ElGamal''' on [[julkisen avaimen salaus]]menetelmä, joka perustuu [[Diffie-Hellman]] avaimenvaihtojärjestelmään. Menetelmä perustuu logaritmien laskentaan ja sen on esittänyt Taher Elgamal vuonna 1985.<ref>{{Verkkoviite | osoite = https://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf | nimeke = A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms | tiedostomuoto = PDF | tekijä = Taher Elgamal | ajankohta = heinäkuu 1985 | viitattu = 13.5.2024 | kieli = {{en}} }}</ref>

ElGamal-menetelmää käyttävät mm. [[GNU Privacy Guard]] -ohjelmisto, [[PGP]]:n uudemmat versiot ja monet muut salausjärjestelmät. [[DSA (algoritmi)|DSA]] (Digital Signature Algorithm) on [[ElGamal-allekirjoitus]]menetelmä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 <math>G</math>. Olkoon <math>q</math> ryhmän <math>G</math> 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 <math>G</math> 
[[primitiivinen alkio|primitiivisen alkion]] <math>g</math>. Primitiivisen alkion ominaisuus on se, että jokainen syklisen ryhmän <math>G</math> alkio voidaan esittää tämän alkion potenssina. Tämän eksponentin laskemista kutsutaan ryhmän <math>G</math> [[diskreetti logaritmi|diskreetin logaritmin probleemaksi]].

Liisa valitsee satunnaisen luvun <math>x</math> joukosta <math>\lbrace 0,1,...,q-1\rbrace</math>.

Liisa laskee ryhmän <math>G</math> alkion <math>h = g^x</math>.

Liisa julkaisee käyttämänsä syklisen ryhmän <math>G</math>, sen kertaluvun <math>q</math>, primitiivisen alkion <math>g</math> ja 
laskemansa alkion <math>h</math>. Nämä muodostavat hänen julkisen avaimensa. Luvun <math>x</math> 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 <math>G</math> alkioksi <math>m</math> käyttäen jotain yksinkertaista ja tunnettua koodausta (vaikkapa ASCII-koodia). 
 
Roope valitsee satunnaisen alkion <math>y</math> lukujoukosta <math>\lbrace 0,1,...,q-1\rbrace</math>.

Tämän jälkeen hän laskee ryhmän <math>G</math> alkiot <math>c_1=g^y</math> ja 
<math>c_2=m\cdot h^y</math>.

Roope lähettää Liisalle salakielisen viestin <math>(c_1,c_2)</math>.

Salauksen purku toimii seuraavasti:

Liisa laskee ryhmän <math>G</math> alkion <math>c_2(c_1^x)^{-1}</math>.

Nyt
<math> c_2(c_1^x)^{-1} = \frac{m\cdot h^y}{g^{xy}} = \frac{m\cdot g^{xy}}{g^{xy}} = m </math>.

Ryhmän <math>G</math> kertaluvun <math>q</math> 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 [[potenssiinkorotusalgoritmi|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 <math>c_2(c_1^x)^{-1}=c_2c_1^{-x}=c_2c_1^{q-x}</math>.

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

== Lähteet ==
{{Viitteet}}

{{Kryptografiset algoritmit}}
[[Luokka:Salausalgoritmit]]