Algoritma

FLOWCHART & SOURCE CODE
ELGAMAL
Sampai akhir tahun 1970, hanya ada sistem kriptografi simetri. Karena sistem kriptografi simetri menggunakan kunci yang sama untuk enkripsi dan dekripsi, maka hal ini mengimplikasikan dua pihak yang berkomunikasi saling mempercayai. Konsep sistem kriptografi kunci-publik ditemukan oleh Diffie dan Hellman yang mempresentasikan konsep ini pada Tahun 1976. Ide dasar dari sistem kriptografi kunci-publik adalah bahwa kunci kriptografi dibuat sepasang, satu kunci untuk enkripsi dan satu kunci untuk dekripsi. Kunci untuk enkripsi bersifat publik (tidak rahasia) – sehingga dinamakan kunci publik (public-key) – sedangkan kunci dekripsi bersifat rahasia – sehingga dinamakan kunci rahasia (private key atau secret key). Kunci-kunci ini dipilih sedemikian sehingga – secara praktek – tidak mungkin menurunkan kunci rahasia dari kunci publik. Sistem kriptografi kunci-publik cocok untuk kelompok pengguna di lingkungan jaringan komputer. Setiap pengguna jaringan mempunyai kunci publik dan kunci rahasia yang bersuaian. Kunci publik, karena tidak rahasia, biasanya disimpan di dalam basisdata kunci yang dapat diakses oleh pengguna lain. Jika ada pengguna yang hendak berkirim pesan ke pengguna lainnya, maka ia ia perlu mengetahui kunci publik penerima pesan melalui basisdata kunci ini lalu menggunakannya untuk mengenkripsi pesan. Hanya penerima pesan yang berhak yang dapat mendekripsi pesan karena ia mempunyai kunci rahasia. Dengan sistem kriptografi kunci publik, tidak diperlukan pengiriman kunci rahasia melalui saluran komunikasi khusus sebagaimana pada sistem kriptografi simetri. Meskipun kunci publik diumumkan ke setiap orang di dalam kelompok, namun kunci publik perlu dilindungi agar otentikasinya terjamin (misalnya tidak diubah oleh orang lain).

Algoritma ElGamal
Algoritma Elgamal merupakan salah satu algoritma kriptografi kunci-publik yang dibuat oleh Taher ElGamal pada tahun 1984. Algoritma in pada umumnya digunakan untuk digital signature, namun kemudian dimodifikasi sehingga juga bisa digunakan untuk enkripsi dan deskripsi. ElGamal digunakan dalam perangkat lunak sekuriti yang dikembangkan oleh GNU, program PGP, dan pada sistem sekuriti lainnya. Kekuatan algoritma ini terletak pada sulitnya menghitung logaritma diskrit.
Algoritma Elgamal tidak dipatenkan. Tetapi, algoritma ini didasarkan pada algoritma Diffie – Hellman, sehingga hak paten algoritma Diffie – Hellman juga mencakup algoritma ElGamal. Karena hak paten algoritma Diffie – Hellman berakhir pada bulan April 1997, maka algoritma ElGamal dapat diimplementasikan untuk aplikasi komersil.
Besaran-besaran yang digunakan di dalam algoritma ElGamal:
1. Bilangan prima, p (tidak rahasia)
2. Bilangan acak, g ( g < p) (tidak rahasia)
3. Bilangan acak, x (x < p) (rahasia)

4. M (plainteks) (rahasia)

5. a dan b (cipherteks) (tidak rahasia)

Prosedur Membuat Pasangan Kunci
• Pilih sembarang bilangan prima p.
• Pilih dua buah bilangan acak, g dan x, dengan syarat g < p dan 1 ≤ x ≤ p – 2.
• Hitung y = gx mod p.
Kunci publik adalah y, kunci rahasia adalah x. Nilai g dan p tidak dirahasiakan dan dapat diumumkan kepada anggota kelompok.
Enkripsi
• Plainteks disusun menjadi blok-blok m1, m2, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam rentang 0 sampai p – 1.
• Pilih bilangan acak k, yang dalam hal ini 0 £ k £ p – 1, sedemikian sehingga k relatif prima dengan p – 1.
• Setiap blok m dienkripsi dengan rumus
a = gk mod p
b = ykm mod p
Pasangan a dan b adalah cipherteks untuk blok pesan m. Jadi, ukuran cipherteks dua kali ukuran plainteksnya.
Dekripsi
Untuk mendekripsi a dan b digunakan kunci rahasia, x, dan plainteks m diperoleh kembali dengan persamaan
m = b/ax mod p
Catatlah bahwa karena
ax º gkx (mod p)
maka
b/ax º ykm/ax
º gxkm/gxk
º m (mod p)
yang berarti bahwa plainteks dapat ditemukan kembali dari pasangan cipherteks a dan b.
Flowchart

Source Code

Contoh
Siti ingin membangkitkan pasangan kuncinya. Siti memilih p = 2357, g = 2, dan x = 1751. Kemudian menghitung :
y = gx mod p = 21751 mod 2357 = 1185
Jadi kunci publiknya ( y = 1185, g = 2, p = 2357 ) dan kunci privatnya ( x = 1751, p = 2357 ).
Enkripsi
Misalkan Ahmad ingin mengirim palinteks m = 2035 (nilai m masih berada di dalam selang [ 0, 2357 – 1 ] ). Ahmad memilih bilangan acak k = 1520 ( nilai k masih berada di dalam selang [ 0, 2357 – 1 ] ). Kemudian Ahmad menghitung
a = gk mod p = 21520 mod 2357 = 1430
b = ykm mod p = 11851520 × 2035 mod 2357 = 697
Jadi, cipherteks yang dihasilkan adalah (1430, 697). Ahmad mengirim cipherteks ini ke Siti.
Dekripsi
Siti mendeskripsi cipherteks dari Ahmad dengan melakukan perhitungan sebagai berikut :
1/ax = (ax)– 1 = a p – 1 – x mod p = 1430605 mod 2357 = 872
m = b/ax mod p = 697 × 872 mod 2357 = 2035
Plainteks yang didekripsi, 2035, sama dengan plainteks yang dikirim oleh Ahmad.