Algoritma Elgamal

Algoritma Elgamal


Algoritma Elgamal 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 sebagai berikut:



Contoh

james hetfield ingin membangkitkan pasangan kuncinya. james hetfield 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 lars ulrich ingin mengirim plainteks m = 2035 (nilai m masih berada di dalam selang [ 0, 2357 – 1 ] ). lars ulrich memilih bilangan acak k = 1520 ( nilai k masih berada di dalam selang [ 0, 2357 – 1 ] ). Kemudian lars ulrich 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). lars ulrich mengirim cipherteks ini ke james hetfield.

Dekripsi

james hetfield mendeskripsi cipherteks dari lars ulrich 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 lars Ulrich.



*Sumber:http://agcrypt.wordpress.com