Algoritma Elgamal

Algoritme Elgamal merupakan salah satu algoritma kriptografi kunci publik yang dibuat oleh Taher ElGamal pada tahun 1984. Algoritme ini pada umumnya digunakan untuk digital signature, tetapi kemudian dimodifikasi sehingga juga bisa digunakan untuk enkripsi dan dekripsi. 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.

Algoritme 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 komersial.

Skema ElGamal memerlukan sepasang kunci yang dibangkitkan dengan memilih sebuah bilangan prima p dan dua buah bilangan random g dan x. Nilai g dan x lebih kecil dari p yang memenuhi persamaan: y = g^x mod p

Dari persamaan tersebut y, g dan p merupakan kunci publik dan x adalah kunci rahasia.

Proses enkripsi merupakan proses mengubah pesan asli (plaintext) menjadi pesan rahasia (ciphertext). Pada proses ini digunakan kunci publik (p, g, y). Langkah-langkah dalam mengenkripsi pesan adalah sebagai berikut:

Potong plaintext menjadi blok-blok m1, m2, …, nilai setiap blok di dalam selang [0, p – 1].

Ubah nilai blok pesan ke dalam nilai ASCII.Pilih bilangan acak k, dengan syarat 1 ≤ k ≤ p – 2.

Setiap blok m dienkripsi dengan rumus sebagai berikut:

gamma (γ) = gk mod p. (1)

delta (δ) = ykm mod p. (2)

Susun ciphertext dengan urutan γ1,δ1, γ2,δ2,…,γn,δn. Pasangan γ dan δ adalah cipherteks untuk blok pesan m. Hasil yang didapat dari proses enkripsi berupa pesan rahasia (ciphertext).

Proses dekripsi merupakan proses mengubah pesanrahasia (ciphertext) menjadi pesan asli (plaintext). Padaproses ini digunakan kunci pribadi (x, p).

Langkah-langkah dalam mendekripsi pesan adalah sebagai berikut:

Penentuan nilai gamma dan delta. Nilai gamma (γ) diperoleh dari ciphertext dengan urutan ganjil sedangkan delta (δ) dengan urutan genap.

Hitung plaintext m dengan persamaan rumus berikut:

m = δ. γ(p-1-x) mod p (3)

Ubah nilai m yang didapat kedalam nilai ASCII.

Susun plaintext dengan urutan m1,m2,…,mn.

• ElGamal, Taher (1985). "A public key cryptosystem and a signature scheme based on discrete logarithms" (PDF). Advances in cryptology: Proceedings of CRYPTO 84. Lecture Notes in Computer Science. 196. Santa Barbara, California, United States: Springer-Verlag. hlm. 10–18. doi:10.1007/3-540-39568-7_2. 
• A. J. Menezes; P. C. van Oorschot; S. A. Vanstone. "Chapter 8.4 ElGamal public-key encryption" (PDF). Handbook of Applied Cryptography. CRC Press. 
• Dan Boneh (1998). The Decision Diffie–Hellman Problem. Lecture Notes in Computer Science. 1423. hlm. 48–63. CiteSeerX 10.1.1.461.9971 . doi:10.1007/BFb0054851. ISBN 978-3-540-64657-0. 

Templat:Cryptography navbox