Kriptografi - Algoritma Elgamal

Algoritma Asimetris ElGamal

Achmad Fauzi - Medan, 03 Mei 2014

Algoritma ElGamal

Algoritma ElGamal ditemukan pada tahun 1985 oleh ilmuwan Mesir yaitu Taher ElGamal. Algoritma ElGamal merupakan algoritma berdasarkan konsep kunci publik. Algoritma ini pada umumnya digunakan untuk digital signature, namun kemudian dimodifikasi sehingga bisa digunakan untuk enkripsi dan dekripsi.

Algoritma kriptografi kunci publik ElGamal merupakan algoritma blok chipper yaitu algoritma yang melakukan proses enkripsi pada blok-blok plainteks yang kemudian menghasilkan blok-blok chipertext, yang nantinya blok-blok chipertext tersebut akan didekripsi kembali dan hasilnya kemudian digabungkan menjadi plainteks semula.

Keamanan algoritma ElGamal terletak pada kesulitan perhitungan logaritma diskrit pada modulo prima yang besar, sehingga upaya untuk menyelesaikan masalah logaritma ini menjadi sulit untuk dipecahkan.

Algoritma ini memiliki kelebihan yaitu pembangkitan kunci yang menggunakan logaritma diskrit dan metode enkripsi dekripsi yang menggunakan proses komputasi yang besar sehingga hasil enkripsinya berukuran dua kali dari ukuran semula. Kekurangan algoritma ini adalah membutuhkan resource yang besar karena chipertext yang dihasilkan dua kali panjang plaintext serta membutuhkan processor yang mampu untuk melakukan komputasi yang besar untuk perhitungan logaritma perpangkatan besar. 

Untuk proses dekripsi, algoritma ini membutuhkan waktu yang lebih lama karena kompleksitas proses dekripsinya yang rumit. Dibutuhkan dua kali komputasi karena ukuran chiperteks yang lebih
besar dibandingkan plainteksnya.

Besar – Besaran dalam algoritma ElGamal
 

Besar-besaran yang digunakan didalam algoritma ElGamal adalah sebagai berikut :
 

1. Bilangan prima, p (bersifat public atau tidak rahasia)
2. Bilangan acak, g (dimana g < p dan bersifat public atau tidak rahasia)
3. Bilangan acak, x (dimana x < p dan bersifat private atau rahasia)
4. Bilangan acak, k (dimana k < p dan bersifat private atau rahasia)
5. m merupakan plainteks dan bersifat private/rahasia
6. a dan b merupakan pasangan chiperteks hasil enkripsi bersifat private atau tidak rahasia
 

2.2.1 Proses Pembentukan kunci Algoritma ElGamal
Proses pembentukan kunci merupakan proses penentuan suatu bilangan yang kemudian akan digunakan sebagai kunci pada proses enkripsi dan dekripsi pesan. Kunci untuk enkripsi dibangkitkan dari nilai p, g, y sedangkan kunci untuk dekripsi terdiri dari nilai x, p. Masing-masing nilai mempunyai persyaratan yang harus dipenuhi. 

Langkah-langkah dalam pembuatan kunci adalah sebagai berikut :

1. Pilih sembarang bilangan prima p, dengan syarat p > 255.
2. Pilih bilangan acak g dengan syarat g < p.
3. Pilih bilangan acak x dengan syarat 1 ≤ x ≤ p – 2.
4. Hitung y = g^x mod p.
 

Kunci public nya adalah y, g, p sedangkan kunci private nya adalah x. nilai y, g, dan p tidak dirahasiakan sedangkan nilai x harus dirahasiakan karena merupakan kunci privat untuk mendekripsi plainteks
 

2.2.2 Proses Enkripsi Algoritma ElGamal
Proses enkripsi merupakan proses mengubah pesan asli (plaintext) menjadi pesan rahasia (chipertext). Pada proses ini digunakan kunci public (p, g, y). 

Langkah-langkah dalam mengenkripsi pesan adalah sebagai berikut :

a. Potong plaintext menjadi blok-blok m1, m2, m3, m4, …, nilai setiap blok di dalam selang [0, p – 1].
b. Ubah nilai blok pesan ke dalam nilai ASCII.
c. Pilih bilangan acak k, dengan syarat 1 ≤ k ≤ p – 1 sebanyak m.
d. Setiap blok m dienkripsi dengan rumus sebagai berikut :
a. a = gki mod p.
b. b = yki . m mod p.
e. Susun chipertext dengan urutan a1, b1, a2, b2, …, an, bn.
Pasangan a dan b adalah chipertext untuk blok pesan m. Hasil yang didapat dari proses enkripsi berupa pesan rahasia (chipertext).
 

2.2.3 Proses Dekripsi Algoritma ElGamal
 

Proses dekripsi merupakan proses mengubah pesan rahasia (chipertext) menjadi pesan asli (plaintext). Pada proses ini digunakan kunci pribadi (x, p).

Langkah-langkah dalam mendekripsi pesan adalah sebagai berikut :

a. Hitung plaintext m dengan persamaan rumus sebagai berikut :
a. mi = bi.ai^p-1-x mod p.
b. Nilai mi yang didapat dalam bentuk ASCII kemudian diubah menjadi plainteks.
c. Susun plaintext dengan urutan m1, m2, m3, …, mn.
Hasil yang didapat dari proses dekripsi berupa pesan asli (plaintext).

Contoh perhitungan manual proses pembentukan kunci, proses enkripsi, dan dekripsi algoritama ElGamal :
 

Perhitungan Pembentukan Kunci.

Misalkan A membangkitkan pasangan kunci dengan memilih bilangan :
 

p = 257
g = 11
x = 13
 

Kemudian p, g, x digunakan untuk menghitung y :
 

y = gx mod p
y = 1113 mod 257
y = 22
 

jadi kunci public A adalah y = 22, g = 11, p = 257 dan kunci private A adalah x =13, p = 257.
 

Perhitungan Enkripsi
Misalkan B ingin mengirim plainteks “ENKRIPSI” kepada A, kemudian setiap karakter plainteks tersebut diubah kedalam bentuk ASCII sehingga menghasilkan tabel sebagai berikut :
 

Plainteks ASCII

E 69
N 78
K 75
R 82
I 73
P 80
S 83
I 73
 

Kemudian nilai ASCII tersebut dimasukkan kedalam blok-blok nilai m secara berurutan, sehingga menjadi : 

m1 = 69, m2 = 78, m3 = 75, m4 =82, m5 = 73, m6 = 80, m7 = 83, m8 = 73.

mn Nilai
m1 69
m2 78
m3 75
m4 82
m5 73
m6 80
m7 83
m8 73

Kemudian B memilih bilangan acak k untuk masing-masing nilai m dimana nilai ki ini bernilai 0 < k < p -1. Sehingga diambil nilai acak k untuk masing-masing nilai m sebagai berikut :

mn Nilai ki
m1 69 58
m2 78 178
m3 75 251
m4 82 62
m5 73 137
m6 80 27
m7 83 256
m8 73 173
 

Kemudian B menghitung :
 

Perhitungan a :
 

a = g^k mod p
 

Nilai m1 :
a1 = gk mod p
a1 = 1158 mod 257
a1 = 30
 

Nilai m2 :
a2 = gk mod p
a2 = 11178 mod 257
a2 = 137
 

Nilai m3 :
a3 = gk mod p
a3 = 11251 mod 257
a3 = 73
 

Nilai m4 :
a4 = gk mod p
a4 = 1162 mod 257
a4 = 17
 

Nilai m5 :
a5 = gk mod p
a5 = 11137 mod 257
a5 = 190
 

Nilai m6 :
a6 = gk mod p
a6 = 1127 mod 257
a6 = 184
 

Nilai m7 :
a7 = gk mod p
a7 = 11256 mod 257
a7 = 1
 

Nilai m8 :
a8 = gk mod p
a8 = 11173 mod 257
a8 = 235
 

Perhitungan bi :
 

bi = yk. m mod p
 

Nilai m1 :
b1 = yk m mod p
b1 = 2258.69 mod 257
b1 = 201
 

Nilai m2 :
b2 = yk m mod p
b2 = 22178.78 mod 257
b2 = 82
 

Nilai m3 :
b3 = yk m mod p
b3 = 22251.75 mod 257
b3 = 147
 

Nilai m4 :
b4 = yk m mod p
b4 = 2262.82 mod 257
b4 = 220
 

Nilai m5 :
b5 = yk m mod p
b5 = 22137.73 mod 257
b5 = 16

Nilai m6 :
b6 = yk m mod p
b6 = 2227.80 mod 257
b6 = 203
 

Nilai m7 :
b7 = yk m mod p
b7 = 22256.83 mod 257
b7 = 83

Nilai m8 :
b8= yk m mod p
b8 = 22173.73 mod 257
b8 = 249
 

Setelah mendapatkan nilai a dan b, hasil perhitungan tersebut disusun dengan pola :

a1, b1, a2, b2, a3,b3, a4, b4, a5, b5, a6, b6, a7, b7, a8, b8.
 

Sehingga membentuk chiperteks : 

30 201 137 82 73 147 17 220 190 16 184 203 1 83 235 249.

Perhitungan Dekripsi
A mendekripsikan chiperteks dari B dengan melakukan perhitungan dengan rumus sebagai berikut :
 

mi = bi.ai p-1-xmod p
 

Nilai m1 :
m1 = bi.ai p-1-xmod p
m1 = 201.30257-1-13 mod 257
m1 = 69
 

Nilai m2 :
m2 = bi.ai p-1-xmod p
m2 = 82.137257-1-13 mod 257
m2 = 78
 

Nilai m3 :
m3 = bi.ai p-1-xmod p
m3 = 147.73257-1-13 mod 257
m3 = 75
 

Nilai m4 :
m4 = bi.ai p-1-xmod p
m4 = 220.17257-1-13 mod 257
m4 = 82
 

Nilai m5 :
m5 = bi.ai p-1-xmod p
m5 = 16.190257-1-13 mod 257
m5 = 73
 

Nilai m6 :
m6 = bi.ai p-1-xmod p
m6 = 203.184257-1-13 mod 257
m6 = 80

Nilai m7 :
m7 = bi.ai^p-1-xmod pm7 = 83.1257-1-13 mod 257
m7 = 83

Nilai m8 :
m8 = bi.ai^p-1-xmod p
m8 = 249.235257-1-13 mod 257
m8 = 73

Setelah mendapatkan nilai mi, masing-masing nilai m hasil dekripsi menjadi kode ASCII diubah kembali menjadi karakter. Dengan hasil sebagai berikut :

69, 78, 75, 82, 73, 80, 83, 73.
 

Kemudian kode ASCII tersebut diubah menjadi plainteks dengan hasil sebagai berikut :
 

ASCII Plainteks

69 E78 N75 K82 R73 I80 P83 S73 I

Sehingga hasil dekripsi membentuk plainteks “ENKRIPSI”, sama dengan plainteks sebelum di enkripsi. 

Sumber : http://hendra-blacksilver.blogspot.com/2013/02/algoritma-asimetris-elgamal.html