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

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

Berikut langkah-langkah proses algoritma elgamal

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

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 :

1. Potong plaintext menjadi blok-blok m1, m2, m3, m4, …, nilai setiap blok di dalam selang [0, p – 1].
2. Ubah nilai blok pesan ke dalam nilai ASCII.
3. Pilih bilangan acak k, dengan syarat 1 = k = p – 1 sebanyak m.
4. Setiap blok m dienkripsi dengan rumus sebagai berikut :
   a = gki mod p
   b = yki . m mod p
5. 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).

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 :

1. Hitung plaintext m dengan persamaan rumus sebagai berikut :
   mi = bi.ai^p-1-x mod p.
2. Nilai mi yang didapat dalam bentuk ASCII kemudian diubah menjadi plainteks.
3. Susun plaintext dengan urutan m1, m2, m3, …, mn..

Maka Hasil yang didapat dari proses dekripsi berupa pesan asli (plaintext).

Contoh Perhitungan Algoritma Elgamal :

Berikut Contoh perhitungan manual proses pembentukan kunci algoritma elgamal, proses enkripsi, dan dekripsi :

Langkah I : Pembentukan Kunci Algoritma Elgamal

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.

Langkah II : Perhitungan Enkripsi Algoritma Elgamal

Misalkan B ingin mengirim plainteks "ENKRIPSI" kepada A, kemudian setiap karakter plainteks tersebut diubah kedalam bentuk ASCII sehingga menghasilkan 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..
untuk caranya, lihat lagi langkah-langkah enkripsi diatas.

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 sbb:
30 201 137 82 73 147 17 220 190 16 184 203 1 83 235 249.

Sekarang akan dikembalikkan ke plainteks, berikut perhitungannya

Langkah III : Perhitungan Dekripsi Algoritma Elgamal

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

mi = bi.ai p-1-xmod p

Lihat lagi Langkah-langkah Untuk Menghitung Dekripsi di atas....

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.

Begitulah langkah-langkah perhitungan algoritma elgamal untuk enkripsi dan dekripsi file teks, untuk test demo program-nya dapat melihat link di bawah.

Screenshot Program

Page : Menentukkan Key & Proses Enkripsi

 

Page : Proses Dekripsi