Algoritma El-Gamal

Algoritma El-Gamal 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 El-Gamal 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.

Paten

  • Algoritma ElGamal tidak dipatenkan. Tetapi, algoritma ini didasarkan pada algoritma Diffie-Hellman, sehingga hak paten algoritam Diffie-Hellman juga mencakup algoritma Untunglah hak paten algoritma Diffie-Hellman berakhir pada bulan April 1997, sehingga algoritma ElGamal dapat diimplementasikan untuk aplikasi komersil.

Besaran-besaran yang digunakan di dalam algoritma ElGamal adalah:

  1. Bilangan prima, (tidak rahasia)
  2. Bilangan acak, p)        (tidak rahasia)
  3. Bilangan acak, (p)         (rahasia, kunci privat)
  4. gx mod (tidak rahasia, publik)
  5. (plainteks)                           (rahasia)
  6. dan (cipherteks) (tidak rahasia)
  1. embentukan Kunci
    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 = gx mod pDari persamaan tersebut y, g dan p merupakan kunci publik dan x adalah kunci rahasia.
  2. Proses Enkripsi
    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.
    1. Potong plaintext menjadi blok-blok m1, m2, …, 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 – 2.
    4. Setiap blok m dienkripsi dengan rumus sebagai berikut.
      gamma (γ) = gk mod p. (1)
      delta (δ) = ykm mod p. (2)
    5. 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).
  3. Proses Dekripsi
    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.
    1. Penentuan nilai gamma dan delta. Nilai gamma (γ) diperoleh dari ciphertext dengan urutan ganjil sedangkan delta (δ) dengan urutan genap.
    2. Hitung plaintext m dengan persamaan rumus berikut.
      m = δ. γ(p-1-x) mod p (3)
    3. Ubah nilai m yang didapat kedalam nilai ASCII.
    4. Susun plaintext dengan urutan m1,m2,…,mn.

Contoh Kasus :

KeteranganNilai
Pesan(plaintext)hello android
Nilai (p,g,y,x)(383, 148, 295, 338)
Nilai kk1 = 319, k2= 259, k3 = 353, k4 = 105, k5 = 267, k6= 279,k7 = 190, k8 = 252, k9 = 60, k10 = 87, k11 = 360, k12 =139,k13 = 48

Proses Pembentukan Kunci : 

Berikut contoh manual pembentukan kunci untuk proses enkripsi dan dekripsi. Misalkan pengirim memilih p = 2903, g = 5, dan x = 1751. Kemudian menghitung : y = gx mod p = 51751 mod 2903 = 771

Diperoleh kunci publik ( y  , g , p ) = ( 771, 5, 2903 ) dan kunci privatnya x = 1751. Kunci publik ( 771, 5, 2903 )  inilah yang diberikan penerima kepada pemberi pesan. Kunci rahasia  tetap dipegang oleh penerima dan tidak boleh ada yang mengetahui selain dirinya sendiri.

Proses Enkripsi :

Langkah-langkah  penyelesaian  proses  enkripsi  secara manual adalah sebagai berikut:

Diketahui :

Plaintext :  “hello android”

Nilai p = 383, g = 148 dan y = 295.

Nilai k1 = 319, k2 = 259, k3 = 353, k4 = 105, k5 = 267, k6 = 279, k7 = 190, k8 = 252, k9 = 60, k10 = 87, k11 = 360, k12 = 139, k13 = 48

Jawab :

  • Ubah pesan  asli (plaintext)  ke dalam  ASCII
    h=104, e=101, l=108, l=108 , o=111, spasi=32, a=97, n=110, d=100, r=114, o=111, i=105, d=100
    sehingga nilai pesan ASCII adalah sebagai berikut :
    m1=104, m2=101, m3=108, m4=108 , m5=111, m6=32, m7=97, m8=110, m9=100, m10=114, m11=111, m12=105, m13=100
    Table Konversi ASCIIiCharacterPlaintext miACSII1hm11042em21013lm31084lm41085om51116“spaci”m6327am7978nm81109dm910010rm1011411om1111112im1210513dm13100
  • Hitung gamma (γ) dengan rumus γ= gk mod p
    γ1= 148319 mod 383,
    γ2= 148259mod 383,
    γ3= 148353 mod 383,
    γ4= 148105 mod 383,
    γ5= 148267 mod 383,
    γ6= 148279 mod 383 dst..
    Sehingga Hasilnya:γ1 = 197γ7 = 339γ2 = 122γ8 = 31γ3 = 85γ9 = 168γ4 = 379γ10 = 37γ5 = 340γ11 = 38γ6 = 269γ12 = 356γ13 = 144
  • Hitung delta dengan rumus δ  = yk. m mod p
    δ1     =  295319. 104 mod 383 = 158
    δ2     =  295259. 101 mod 383 = 2
    δ3     =  295353. 108 mod 383 = 300
    δ4     =  295105. 108 mod 383 = 336
    dst…
    Hasilnya :δ1 = 158δ7 = 99δ2 = 2δ8 = 153δ3 = 300δ9 = 292δ4 = 336δ10 = 113δ5 = 250δ11 = 367δ6 = 98δ12 = 345δ13 = 8
  • Susun hasil perhitungan gamma (γ ) dan delta (δ)
    Ciphertext : 197, 158, 122, 2, 85, 300, 379, 336, 340, 250, 269, 98, 339, 99, 31, 153, 168, 292, 37, 113, 38, 367, 356, 345, 144, 8

Posted

in

by

Tags:

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *