8
BAB 2 LANDASAN TEORI
Bab ini akan membahas tinjauan teoritis yang berkaitan dengan algoritma kriptografi ElGamal dan algoritma kompresi Elias Gamma Code.
2.1 Kriptografi Kriptografi mempunyai peranan penting dalam dunia komputer. Hal ini disebabkan karena banyaknya informasi rahasia yang disimpan dan dikirim melalui media-media komputer. Informasi- informasi ini biasanya berisikan dokumen-dokumen penting dan data keuangan dari suatu instansi yang tidak ingin dibaca oleh orang yang tidak berhak atas informasi tersebut. Oleh karena itu ilmu kriptografi setiap saat selalu dikembangkan oleh orang untuk dapat menjaga fasilitas – fasilitas tersebut.
2.1.1 Defenisi Kriptografi Menurut Rinaldi Munir dalam skripsi Yuli Andri, 2009 : Kriptografi (cryptography) berasal dari Bahasa Yunani: “cryptós” artinya “secret” (rahasia), sedangkan “gráphein” artinya “writing” (tulisan). Jadi, kriptografi berarti “secret writing” (tulisan rahasia). Kriptografi adalah ilmu mengenai teknik enkripsi dimana data diacak menggunakan suatu kunci enkripsi menjadi sesuatu yang sulit dibaca oleh seseorang yang tidak memiliki kunci dekripsi (Kromodimoeljo, 2009).
Secara umum, kriptografi merupakan teknik pengamanan informasi yang dilakukan dengan cara mengolah informasi awal (plainteks) dengan suatu kunci tertentu menggunakan suatu metode enkripsi tertentu sehingga menghasilkan suatu informasi
9
baru (cipherteks) yang tidak dapat dibaca secara langsung. Cipherteks tersebut dapat dikembalikan menjadi informasi awal (plainteks) melalui proses dekripsi. Urutan proses kriptografi secara umum dapat dilihat pada Gambar 2.1.
Ciphertext
Plaintext Enkripsi
Plaintext Dekripsi
Gambar 2.1. Urutan proses kriptografi (Widyartono, A. 2011).
2.1.2 Sejarah Kriptografi Sebagian besar sejarah kriptografi merupakan bagian dari kriptografi klasik, yaitu metode kriptografi yang menggunakan kertas dan pensil atau menggunakan alat bantu mekanik yang sederhana. Kriptografi klasik secara umum dikelompokkan menjadi dua kategori, yaitu algoritma transposisi (transposition cipher) dan algoritma substitusi (substitution cipher). Algoritma transposisi adalah algoritma yang mengubah susunan-susunan huruf di dalam pesan, sedangkan algoritma substitusi yaitu mengganti setiap huruf atau kelompok huruf dengan sebuah huruf atau kelompok huruf yang lain. Algoritma substitusi paling awal dan paling sederhana adalah Caesar Cipher, yang digunakan oleh raja Yunani kuno, Julius Caesar. Disaat Julius Caesar ingin mengirimkan sebuah pesan rahasia kepada seorang jenderal di medan perang. Pesan tersebut akan dikirimkan melalui seorang kurir. Karena tingkat kerahasiaan pesan yang tinggi, maka Julius Caesar tidak mau mengambil resiko jika pesan tersebut sampai ke tangan musuh. Maka Caesar mensubstitusi pesan tersebut dengan cara mengganti hurufhuruf alfabet a menjadi d, b menjadi e, c menjadi f dan seterusnya. Sebelumnya kunci dari pesan tersebut telah diberitahu oleh Julius Caesar kepada jenderal yang akan menerima pesan tersebut. Dengan demikian, walaupun pesan tersebut jatuh ke pihak musuh, maka musuh tersebut tidak akan dapat membaca pesan tersebut.
10
Pada abad ke-20, kriptografi lebih banyak digunakan oleh kalangan militer. Pada perang dunia ke II, Pemerintah Nazi Jerman membuat mesin enkripsi yang dinamakan dengan Enigma. Mesin ini menggunakan beberapa buah rotor (roda berputar), dan melakukan proses enkripsi yang sangat rumit. Jerman percaya pesan akan dikirim melalui enigma tidak akan terpecahkan kode enkripsinya. Tetapi anggapan Jerman tersebut salah, setelah mempelajari mesin enigma bertahun-tahun, sekutu berhasil memecahkan kode-kode tersebut. Setelah Jerman mengetahui kode-kode mereka telah terpecahkan, kemudian enigma mengalami beberapa kali perubahan. Mesin Enigma dapat dilihat pada Gambar 2.2.
Gambar 2.2 Mesin enigma yang digunakan tentara Jerman ( Halim, A. 2013).
Perkembangan peralatan komputer digital memicu terbentuknya kriptografi modern. Dengan komputer digital, akan sangat mungkin untuk menghasilkan cipher yang lebih kompleks dan rumit. Kriptografi klasik pada umumnya dienkripsi karakter per karakter (menggunakan alfabet tradisional), sedangkan kriptografi modern beroperasi pada string biner. Kriptografi modern tidak hanya berkaitan dengan teknik menjaga kerahasisaan pesan, tetapi juga menghasilkan tanda tangan digital dan sertifikat digital.
11
2.1.3. Tujuan Kriptografi Kriptografi bertujuan untuk memberikan layanan keamanan (Kurniawan, Y.
2004)
sebagai berikut:
1. Kerahasiaan (Confidentiality) Layanan yang ditujukan untuk menjaga pesan tidak dapat dibaca oleh pihak-pihak yang tidak berhak. 2. Keutuhan Data (Integrity) Penerima harus dapat memeriksa apakah pesan telah dimodifikasi ditengah jalan atau tidak. Seorang penyusup seharusnya tidak dapat memasukkan tambahan ke dalam pesan, mengurangi atau mengubah pesan selama data berada diperjalanan. 3. Autentikasi (Message Authentication) Penerima pesan dapat memastikan keaslian pengirimnya. Penyerang tidak dapat berpura- pura sebagai orang lain. 4.
Menolak Penyangkalan (Nonrepudiation) Pengirim seharusnya tidak dapat mengelak bahwa dialah pengirim pesan yang sesungguhnya. Tanpa kriptografi, seseorang dapat mengelak bahwa dialah pengirim email yang sesungguhnya.
2.1.4 Terminologi dan Konsep Dasar Kriptografi Dalam bidang kriptografi akan ditemukan beberapa istilah atau terminologi. Isitilahistilah tersebut sangat penting untuk diketahui dalam memahami ilmu kriptografi. Oleh karena itu penulis akan menjelaskan beberapa istilah penting dalam bidang kriptografi yang akan sering penulis gunakan dalam tulisan penulis. Berikut merupakan istilah-istilah penting tersebut.
a. Plainteks dan Cipherteks Pesan merupakan data atau informasi yang dimengerti maknanya. Nama lain dari pesan adalah plainteks. Pesan tersebut dapat dikirim (melalui kurir, saluran telekomunikasi, dan
12
lain-lain) dan dapat juga disimpan dalam media penyimpanan (kertas, storage, dan lainlain). Pesan dapat berupa teks, video, gambar, dan lain-lain. Agar pesan tersebut tidak dapat dimengerti maknanya bagi pihak lain, maka pesan perlu disandikan ke bentuk lain yang tidak dapat dipahami. Bentuk pesan yang telah tersandikan tersebut dinamakan dengan cipherteks (ciphertext). Perbandingan plainteks dan cipherteks dapat dilihat pada Gambar 2.3
(a). Plainteks
(b). Cipherteks
Gambar 2.3 Perbandingan plainteks dan cipherteks ( Halim, A. 2013).
b.
Peserta Komunikasi Komunikasi data melibatkan pertukaran pesan antara dua entitas. Entitas yang
pertama adalah pengirim, yang berfungsi mengirim pesan kepada entitas lain. Entitas kedua adalah penerima, yang berfungsi menerima pesan yang dikirimkan. Entitas-entitas ini dapat berupa orang, mesin (komputer), kartu kredit dan sebagainya. Contohnya mesin ATM berkomunikasi dengan komputer server di bank. Pengirim ingin mengirimkan pesan dengan aman sampai ke penerima. Jadi solusinya adalah dilakukan penyandian terhadap pesan tersebut agar tidak diketahui pihak-pihak yang tidak berkepentingan terhadap pesan tersebut.
c.
Enkripsi dan Dekripsi
Proses penyandian pesan, dari plainteks ke cipherteks dinamakan dengan enkripsi (encryption) atau enchipering (standard nama menurut ISO 7498-2). Sedangkan proses mengembalikan pesan dari cipherteks ke plainteks dinamakan dengan dekripsi
13
(descryption) atau dechipering (standard nama menurut ISO 7498-2). Proses enkripsi dan dekripsi dapat diterapkan pada pesan yang dikirim ataupun pesan yang disimpan. Encryption of data in motion mengacu pada enkripsi pesan yang ditransmisikan melalui saluran komunikasi, sedangkan istilah encryption of data at-rest mengacu pada enkripsi pesan yang tersimpan di dalam storage.
d.
Kriptanalis dan Kriptologi
Kriptografi selalu memiliki perkembangan, karena kriptografi memiliki ilmu yang berlawan yang disebut dengan kriptanalisis. Kriptanalis (cryptanalysis) adalah ilmu dan seni untuk memecahkan cipherteks menjadi plainteks, tanpa memerlukan kunci yang digunakan. Pelakunya disebut dengan cryptanalyst. Jika seorang kriptopgrafer (istilah bagi
pelaku
kriptografi)
mentransformasikan
plainteks
ke
cipherteks
dengan
menggunakan kunci, maka sebaliknya seorang kriptanalis berusaha memecahkan cipherteks tersebut untuk menemukan plainteks atau kunci. Kriptologi (cryptology) adalah studi mengenai kriptografi dan kriptanalis. Hubungan antara kriptologi, kriptografi dan kriptanalis dapat dilihat pada Gambar 2.4.
Kriptologi
Kriptografi
Kriptanalis
Gambar 2.4 Hubungan antara kriptologi, kriptografi dan kriptografi (Kurniawan, Y. 2004)
2.1.5 Jenis Kriptografi Berdasarkan kunci enkripsi dan dekripsinya algoritma kriptografi terbagi menjadi dua bagian yaitu :
14
1. Kriptografi simetri Pada sistem algoritma simetris, kunci untuk proses enkripsi sama dengan kunci untuk proses dekripsi. Keamanan sistem algoritma simetris terletak pada kerahasiaan kunci. Istilah lain untuk algoritma simetris adalah kriptografi kunci privat (private key cryptography) atau kriptografi konvensional (conventional cryptography). Kriptografi simetri merupakan satu-satunya jenis kriptografi yang dikenal dalam catatan sejarah hingga tahun 1976. Semua algoritma kriptografi klasik termasuk ke dalam sistem kriptografi simetri. Skema Algoritma Simetri dapat dilihat pada Gambar 2.5
Kunci
Plainteks
A
Plainteks
Cipherteks
Enkripsi
Dekripsi
B
Gambar 2.5 Skema Algoritma Simetri (Halim, A. 2013)
Kriptografi simetri adalah kunci enkripsi sama dengan kunci dekripsi, yaitu K. Sebelum melakukan pengiriman pesan, pengirim dan penerima harus memilih suatu kunci tertentu yang sama untuk dipakai bersama, dan kunci ini haruslah rahasia bagi pihak yang tidak berkepentingan sehingga algoritma ini disebut juga algoritma kunci rahasia (secret-key algorithm). a. Kelebihan Kriptografi Simetri :
1. Proses enkripsi atau dekripsi kriptografi simetri membutuhkan waktu yang singkat. 2. Ukuran kunci simetri relatif lebih pendek.
15
3. Otentikasi pengiriman pesan langsung diketahui dari cipherteks yang diterima, karena kunci hanya diketahui oleh penerima dan pengirim saja. b. Kekurangan Kriptografi Simetri: 1. Kunci simetri harus dikirim melalui saluran komunikasi yang aman, dan kedua entitas yang berkomunikasi harus menjaga kerahasiaan kunci. 2. Kunci harus sering diubah, setiap kali melakasanakan komunikasi.
2. Kriptografi asimetri Berbeda dengan kriptografi kunci simetri, kriptografi kunci publik memiliki dua buah kunci yang berbeda pada proses enkripsi dan dekripsinya. Nama lain dari kunci asimetri ini adalah kriptografi kunci-publik (public-key cryptography). Kunci untuk enkripsi pada kriptografi asimetri ini tidak rahasia (diketahui oleh publik), sedangkan kunci untuk dekripsi bersifat rahasia (kunci privat). Entitas pengirim akan mengenkripsi dengan menggunakan kunci publik, sedangkan entitas penerima mendekripsi menggunakan kunci privat. Skema dari kriptografi asimetri dapat dilihat pada Gambar 2.6.
Gambar 2.6 Skema Algoritma Asimetri ( Halim, A. 2013) Kriptografi asimetri ini dapat dianalogikan seperti kotak surat yang terkunci dan memiliki lubang untuk memasukan surat. Setiap orang dapat memasukkan surat ke dalam kotak surat tersebut, tetapi hanya pemilik surat yang memiliki kunci dan yang dapat membuka kotak surat. Kunci publik dapat dikirim ke penerima melalui saluran yang sama dengan saluran yang digunakan untuk mengirim pesan, tidak perlu takut, karena
16
pihak yang tidak berkepentingan tidak akan dapat mendekripsi pesan tersebut, karena tidak memiliki kunci privat. a. Kelebihan kriptografi asimetri: 1.
Hanya kunci privat yang perlu dijaga kerahasiaanya oleh setiap entitas yang berkomunikasi. Tidak ada kebutuhan mengirim kunci privat sebagaimana pada kunci simetri.
2.
Pasangan kunci privat dan kunci publik tidak perlu diubah dalam jangka waktu yang sangat lama.
3.
Dapat digunakan dalam pengaman pengiriman kunci simetri.
4.
Beberapa algoritma kunci publik dapat digunakan untuk memberi tanda tangan digital pada pesan.
b. Kelemahan kriptografi asimetri : 1. Proses enkripsi dan dekripsi umumnya lebih lambat dari algoritma simetri, karena menggunakan bilangan yang besar dan operasi bilangan yang besar. 2. Ukuran cipherteks lebih besar daripada plainteks. 3. Ukuran kunci relatif lebih besar daripada ukuran kunci simetri.
2.2 Algoritma ElGamal Algoritma ini merupakan salah satu algoritma kriptografi asimetri. Pada subbab ini penulis akan membahas dasar-dasar dan prinsip kerja dari algoritma ElGamal itu sendiri.
2.2.1 Sejarah Algoritma ElGamal Algoritma ElGamal merupakan algoritma enkripsi kunci asimetris yang berdasarkan pada pertukaran kunci Diffe-Hellman. Algoritma ini diusulkan Taher Elgamal pada tahun 1984. Keamanan algoritma ini didasarkan pada kesulitan memecahkan masalah logaritma diskrit dalam grup. Sampai akhir tahun 1970, hanya ada sistem kriptografi simetri.
17
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). Logaritma ini disebut logaritma diskrit karena nilainya berhingga dan bergantung pada bilangan prima yang digunakan. Karena bilangan prima yang digunakan adalah bilangan prima yang besar, maka sangat sulit bahkan tidak mungkin menurunkan kunci privat dari kunci publik yang diketahui walaupun serangan dilakukan dengan menggunakan sumberdaya komputer yang sangat besar. Algoritma ElGamal mempunyai kunci publik berupa tiga pasang bilangan dan kunci rahasia berupa satu bilangan. Algoritma ini mempunyai kerugian pada cipherteksnya yang mempunyai panjang dua kali lipat dari plainteksnya. Akan tetapi, algoritma ini mempunyai kelebihan pada enkripsi. Untuk plainteks yang sama, algoritma ini memberikan cipherteks yang berbeda setiap kali plainteks dienkripsi. Algoritma ElGamal terdiri dari tiga proses, yaitu proses pembentukan kunci, proses enkripsi dan proses dekripsi. Algoritma ini merupakan cipher blok, yaitu melakukan proses enkripsi pada blok-blok plainteks dan menghasilkan blok-blok cipherteks yang kemudian dilakukan proses dekripsi dan hasilnya digabungkan. Besaran-besaran yang digunakan dalam pembangkitan kunci publik algoritma ElGamal (Taufiq, M. 2010) : 1. Bilangan prima, p (tidak rahasia) 2. Bilangan acak α sebagai akar primitf ( α < p) (tidak rahasia) 3. Bilangan acak a (a < p) (rahasia) 4. Blok plainteks M (plainteks) (rahasia) 5. y dan c (cipherteks) (tidak rahasia)
18
2.3 Landasan Matematika Algoritma ElGamal Dalam mempelajari sebuah algoritma kriptografi, sebaiknya kita memahami terlebih dahulu konsep-konsep dasar perhitungan matematis yang akan digunakan dalam suatu algoritma kriptografi tersebut.
2.3.1 Modulo Exponensial Modulo eksponensial sering digunakan dalam bidang kriptografi untuk menghitung hasil enkripsi maupun hasil dekripsi. Permasalahan pada operasi modulo adalah bagaimana menghitung xy (mod n) dengan n yang sangat besar. Terdapat beberapa cara untuk menghitung modulo eksponensial, antara lain adalah dengan cara iteratif. Function mod exp (x, y, n){ z =1 for (i=1; i ≤ y; i++){ z = x * z mod n } return z } Contoh : Tentukan hasil dari 25 mod 30 dengan cara iterasi! Diketahui nilai x = 2, y = 5 dan n = 30. z=1 i=1 z = 2 * 1 mod 30 = 2 i=2 z = 2 * 2 mod 30 = 4 i=3 z = 2 * 4 mod 30 = 8 i=4 z = 2 * 8 mod 30 = 16 i=5 z = 2 * 16 mod 30 = 2 berhenti
19
Maka hasil dari 25 mod 30 adalah 2. 2.3.2
Algoritma Euclidean
Algoritma ini digunakan untuk mencari nilai pembagi persekutuan terbesar (PBB) dari dua bilangan bulat. Algoritma ini didasarkan pada pernyataan bahwa ada dua buah bilangan bulat tak negatif yakni m dan n dimana nilai m ≥ n. Adapun tahap-tahap pada algoritma Euclidean adalah: 1. Jika n = 0 maka m adalah PBB (m, n); stop. Kalau tidak (yaitu n ≠ 0) lanjutkan ke langkah nomor 2. 2. Bagilah m dengan n dan misalkan sisanya adalah r. 3. Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulang kembali ke langkah nomor 1. Algoritma Euclidean dapat digunakan untuk mencari dua buah bilangan bulat yang relatif prima. Contoh : Tentukan gcd (108, 360) 360 mod 108 = 36 108 mod 36 = 0 (STOP) Jadi gcd (108, 360) = 36 Tentukan gcd (45, 13) 45 mod 13 = 6 13 mod 6 = 1 6 mod 1 = 0 (STOP) Jadi gcd (45, 13) = 1. Apabila GCD dari m & n = 1, maka m&n disebut Relatif prima.
2.3.3 Inversi Modulo Jika a dan n relatif prima dan n > 1, maka inversi dari a mod n dapat ditemukan. Inversi dari a (mod n), juga disebut inversi perkalian, dimana bilangan bulat a-1 sedemikian sehingga: aa-1 ≡ 1 (mod n)
20
Pembuktian dari persamaan diatas dapat dilihat dari definisi relatif prima diketahui bahwa GCD(a, n) = 1. Contoh: untuk inversi dari 7 (mod 11), penyelesaiannya dapat dilihat pada Tabel 2.1. Tabel 2.1. Penyelesaian contoh soal inversi modulo. a-1
a-1 x 7(mod 11)
1
1 x7 (mod11) = 7
2
2 x7 (mod11) = 3
3
3 x7 (mod11) = 10
4
4 x7 (mod11) = 6
5
5 x7 (mod11) = 2
6
6 x7 (mod11) = 9
7
7 x7 (mod11) = 5
8
8 x7 (mod11) = 1
Pada Tabel 2.1, iterasi berhenti ketika a-1a ≡ 1 (mod n) dan diperoleh a-1 = 8.
2.3.4 Bilangan Prima Bilangan positif p (p>1) disebut bilangan prima jika pembaginya hanya 1 dan p. Sebagai contoh bilangan 23 adalah bilangan prima karena ia hanya habis dibagi 1 dan 23. Karena bilangan prima harus lebih besar dari satu, maka barisan bilangan prima dimulai dari 2, yaitu 2, 3, 5 , 7, 11, 13, .... Seluruh bilangan prima adalah bilangan ganjil, kecuali dua yang merupakan bilangan genap. Sebuah bilangan bulat p > 1 disebut bilangan prima, jika bilangan tersebut hanya memiliki pembagi positif 1 dan p. Bilangan bulat yang lebih dari 1 yang bukan bilangan prima disebut bilangan komposit (Putra, E. 2013).
21
2.3.5 Bilangan Relatif Prima Dua buah bilangan bulat a dan b dikatakan relatif prima jika PBB atau GCD (greatest common divisor) dari a dan b bernilai 1. Contoh : 20 dan 3 relatif prima sebab PBB (20, 3) = 1. Begitu juga 7 dan 11 relatif prima karena PBB (7, 11) = 1. Tetapi 20 dan 5 tidak relatif prima sebab PBB (20, 5) = 5 ≠ 1.
2.3.6 Elemen Primitif Selain bilangan prima, dalam kriptografi ElGamal juga digunakan elemen primitif yang merupakan elemen pembangun dari grup Zp. Untuk mencari elemen ini digunakan 2
p=2q+1, dimana q merupakan bilangan prima. Jika elemen α memenuhi α mod p ≠ 1 dan q
α mod p ≠ 1, maka α merupakan elemen primitif (Jeffrey dkk, 2008).). Untuk mengetahui suatu bilangan merupakan elemen primitif atau tidak dapat dilakukan langkah-langkah sebagai berikut : 1. Input bilangan prima aman p ≥ 5. 2. Hitung q=
𝑝−1 2
2
q
3. Hitung α mod p dan α mod p. 2
4. Jika α mod p= 1, maka α bukan elemen primitif. q
5. Jika α mod p= 1, maka α bukan elemen primitif. 6. Jika tidak terpenuhi dua persyaratan di atas maka q merupakan elemen primitif. Misalkan p = 2579 yang merupakan bilangan prima aman. Oleh karena itu, dapat ditentukan bilangan prima 𝑞 =
2579−1 2
= 1289. Untuk menunjukkan bahwa suatu
bilangan bulat a merupakan elemen primitif Z
2579*,
harus ditunjukkan bahwa α2 𝑚𝑜𝑑
2579 ≠1 dan α1289𝑚𝑜𝑑 2579 ≠1. Berikut diberikan tabel perhitungan untuk beberapa nilai a yang diberikan.
22
Tabel 2.2. Perhitungan α2 mod 2579 dan α 𝟏𝟐𝟖𝟗 mod 2579
a
2
3
4
5
6
7
8
α2 𝒎𝒐𝒅 𝟐𝟓𝟕𝟗
4
9
16
25
36
49
64
1
1
1
2578
1
2578
α 𝟏𝟐𝟖𝟗𝒎𝒐𝒅 𝟐𝟓𝟕𝟗 2578
2.3.7 Fermat’s Little Theorem Fermat’s little theorem adalah suatu metode yang digunakan untuk menguji keprimaan suatu bilangan bulat. Teorema Fermat ditemukan oleh Pierre De Fermat merupakan seorang matematikawan Perancis pada tahun 1640. Meskipun dapat digunakan untuk mempermudah kalkulasi dalam kriptografi, peran terpenting dari Fermat's little theorem adalah sebagai dasar dari berbagai teknik enkripsi asimetris. Salah satu perhitungan matematis yang digunakan untuk menghasilkan bilangan prima adalah metode Fermat yang dapat dirumuskan sebagai berikut: Untuk bilangan prima p dan bilangan bulat a, ap≡ a (mod p) dan jika a tidak dapat dibagi oleh p, maka a
p-1
≡1 (mod p) (Kromodimoeljo, S. 2010). Di mana p adalah
bilangan bulat dan a adalah urutan bilangan yang lebih kecil dari p. Contoh penerapan metode Fermat adalah sebagai berikut: a. Bila p = 4 Maka 1 ≤a< 4, didapat a = {1, 2, 3} a
p-1
mod p 4-1
1
4-1
2
4-1
3
3
mod 4 = 1 mod 4 = 1 3
mod 4 = 2 mod 4 = 0 3
mod 4 = 3 mod 4 = 3
Jadi, angka 4 bukan merupakan bilangan prima sebab dalam pengecekan menggunakan metode Fermat didapat semua hasil dari urutan bilangan yang lebih kecil dari 4 terdapat nilai yang 0.
23
b. Bila p = 5 Maka 1 ≤a< 5, jadi didapat a = {1, 2, 3, 4} a 1 2 3 4
p-1 5-1 5-1 5-1 5-1
mod p 4
mod 5 = 1 mod 5 = 1 4
mod 5 = 2 mod 5 = 1 4
mod 5 = 3 mod 5 = 1 4 mod 5 = 4 mod 5 = 1
Jadi, angka 5 merupakan bilangan prima sebab dalam pengecekan menggunakan metode Fermat didapat semua hasil dari urutan bilangan yang lebih kecil dari 5 adalah 1. Untuk angka yang besar dengan jumlah nilai a yang banyak, hanya diambil beberapa angka sebagai contoh untuk dilakukan pengujian dengan metode Fermat.
2.4
Prinsip Kerja Algoritma ElGamal
2.4.1 Proses Pembangkitan Kunci Langkah-langkah dalam pembangkitan kunci 1. Pilih sembarang bilangan prima p ( disarankan bilangan prima yang bernilai besar agar aman dan uji bilangan prima tersebut dengan metode Fermat). Misalkan p = 271 2. Ambil bilangan α sebagai akar primitive mod p Misalkan α =107 3. Ambil bilangan acak a dengan syarat a harus berada dalam rentang 2≤a
24
1. Kunci publik (p,α,x) = (271, 107, 39) 2. Kunci privat (p,a)= (271, 96)
2.4.2 Proses Enkripsi Langkah-langkah dalam mengenkripsi pesan: 1. Terima kunci publik (p, α, x) = (271, 107, 39) 2. Plainteks m disusun menjadi blok-blok m1, m2, …, mp-1 sedemikian sehingga setiap blok merepresentasikan nilai di dalam rentang 0 sampai p – 1. 3.
Ubah nilai blok pesan ke dalam nilai ASCII. Ekspresikan pesan m1 = c = 99 (kode ASCII) sebagai bilangan
4. Ambil sebuah bilangan asli b < p-1 b = 50 5. Hitung y = αb mod p = 10750 mod 271 = 238 Hitung c = (m(xb mod p)) mod p = (99(3950 mod 271) mod 271 = 99.169 mod 271 = 200 Maka dari perhitungan di atas, kita mendapatkan nilai y dan c sebagai cipherteks nya yaitu (238, 200). Jadi, ukuran cipherteks dua kali ukuran plainteksnya. Proses diatas akan berulang untuk membaca semua blok pesan untuk menghasilkan cipherteks. 6. Kirim y = 238 dan c = 200 ke pemilik kunci publik.
2.4.3 Proses Dekripsi Langkah-langkah dalam mendekripsi pesan: 1.
Terima (y,c) dari sender = ( 238, 200)
25
2.
Hitung Z = yp-1-a mod p = 238 271-1-96 mod 271 = 238 174 mod 271 = 178 Hitung M = c.z mod p = 200. 178 mod 271 = 99. Karakter dalam ASCII adalah c. sesuai dengan plainteks yang
dikirim sender, yang berarti bahwa plainteks ditemukan kembali dari pasangan cipherteks y dan c. Kemudian menggabungkan lagi blok m1, m2, ….. menjadi plainteks yang utuh.
2.5
Defenisi Kompresi
Kompresi data adalah ilmu atau seni yang merepresentasikan informasi dalam bentuk yang lebih compact. Istilah kompresi tersebut diterjemahkan dari kata bahasa Inggris “compression” yang berarti pemampatan. Dalam bidang teknik, kompresi berarti proses memampatkan sesuatu yang berukuran besar sehingga menjadi kecil. Dengan demikian, kompresi data berarti proses untuk memampatkan data agar ukurannya menjadi lebih kecil (Komputer, W. 2003). Definisi kompresi data adalah proses yang mengkonversi sebuah masukan berupa aliran data (the source atau data asli mentah) menjadi suatu aliran data lain (the Output, aliran bit, atau aliran sudah dikompres) yang memiliki ukuran lebih kecil. Aliran data (stream) dapat berupa sebuah file atau buffer pada memori. Data dalam konteks kompresi data melingkupi segala bentuk digital dari informasi, yang dapat diproses oleh sebuah program komputer. Bentuk dari informasi tersebut secara luas dapat diklasifikasikan sebagai teks, suara, gambar dan video (Salomon,D. 2007). Tujuan kompresi data adalah untuk mempercepat dan menghemat biaya pengiriman data atau informasi tersebut. Disamping itu kompresi data juga memiliki
26
tujuan untuk dapat mengurangi ukuran data dan dapat disimpan pada media penyimpanan yang memiliki ukuran relatif kecil.
2.5.1 Penggolongan Algoritma Kompresi Secara garis besar terdapat 2 buah penggolongan algoritma kompresi data yaitu kompresi lossy, dan kompresi lossless (Merdiyan, M. 2005). 1. Kompresi Lossless merupakan metoda kompresi data yang memungkinkan data asli dapat disusun kembali dari data hasil kompresi maka rasio kompresi pun tidak dapat terlalu besar untuk memastikan semua data dapat dikembalikan ke bentuk semula. Contoh metode ini adalah Elias Gamma Code, Shannon-Fano Coding, Huffman Coding, Arithmetic Coding, Run Length Encoding, dan lain-lain. 2. Kompresi
Lossy adalah
suatu
metode
untuk
mengkompresi
data
dan
mendekompresinya. Data yang diperoleh mungkin berbeda dari data aslinya, tetapi perbedaan itu cukup dekat. Metode ini paling sering digunakan untuk kompres data multimedia (Audio file dan gambar). Format kompresi Lossy mengalami generation loss yaitu jika mengalami prose kompresi-dekompresi berulang kali maka akan menyebabkan kehilangan kualitas secara progresif. Contoh metode ini adalah Transform Coding, Wavelet, dan lain-lain.
2.5.2 Algoritma Elias Gamma Code Elias Gamma Code adalah sebuah algoritma kompresi yang dibuat oleh Peter Elias. Untuk membuat tabel kode Elias Gamma, Elias menambah panjang kode dalam unary (u). Dalam kode berikutnya, Eγ ditambahkan pada panjang kode (M) dalam biner (β). Dengan demikian, Elias Gamma Code, yang juga untuk bilangan bulat positif, sedikit lebih kompleks untuk dibangun (Salomon, D. 2007). Adapun aturan untuk mengkodekan sebuah bilangan dengan menggunakan Elias Gamma (Sukiman & Chandra, 2013) adalah sebagai berikut: 1. Tulis bilangan (n) tersebut dalam bentuk biner (β), hitung jumlah bit (M).
27
2. Kurangkan 1 dari jumlah bit yang ditulis pada langkah pertama dan tambahkan sesuai dengan banyaknya bilangan nol (u) diikuti oleh angka 1. 3. Gabungkan bilangan dalam bentuk biner (β) dengan kode dalam bentuk unar (u) dengan menghilangkan angka 1 didepan sehingga menghasilkan Eγ (n). Contoh pada bilangan integer 4 (n=4), maka : β(4) = 100 M=3 u (4) = 001 Eγ(4) = 100001 = 00001 Elias Gamma hanya dapat digunakan untuk mengkodekan bilangan bulat positif dan
mengasumsikan bahwa pengkodeaan Gamma hanya efisien untuk integer kecil
tetapi tidak cocok untuk integer yang besar, dimana kode terparameter dari Elias Code yang lain adalah Delta code lebih cocok digunakan. Tabel Elias Gamma Code dapat dilihat pada Tabel 2.3. Tabel 2.3. Tabel Elias Gamma Code n
β
M
Unary (u)
Eγ(n)
hapus angka 1 disebelah kiri dari hasil Eγ(n)
1
1
1
1
1
1
2
10
2
01
1 0 0 1
001
3
11
2
01
1011
4
100
3
001
100001
00001
5
101
3
001
100011
00011
6
110
3
001
101001
01001
7
111
3
001
101011
01011
8
1000
4
0001
10000001
0000001
9
1001
4
0001
10000011
0000011
10
1010
4
0001
10001001
0001001
11
1011
4
0001
10001011
0001011
12
1100
4
0001
10100001
0100001
Lanjutan Tabel 2.3. Tabel Elias Gamma Code
011
28
n
β
M
Unary (u)
Eγ(n)
hapus angka 1 disebelah kiri dari hasil Eγ(n)
13
1101
4
0001
10100011
0100011
14
1110
4
0001
10101001
0101001
15
1111
4
0001
10101011
0101011
16
10000
5
00001
1000000001
000000001
17
10001
5
00001
1000000011
000000011
18
10010
5
00001
1000001001
000001001
2.5.2.1 Konsep Kompresi Data
Untuk proses kompresi menggunakan Elias Gamma Code kita merujuk pada Tabel2.3. Dimana Elias Gamma ini hanya cocok diterapkan untuk bilangan desimal 1 hingga 15 karena pengkodean kelima belas bilangan ini hanya memerlukan jumlah bit 1 hingga 7 bit sehingga efisiensi penyimpanan di dapat. Proses kompresi sendiri didasarkan pada bahwa isi file akan dibaca secara per byte (8 bit) sehingga menghasilkan nilai pembacaan antara 0 hingga 255. Suatu metode pada kompresi data akan menghasilkan bit-bit (satuan terkecil pembentuk data) data baru yang lebih pendek dibandingkan oleh bit-bit data sebelum dikompresi. Bit-bit data yang lebih pendek tersebut biasanya tidak akan bisa dibaca oleh komputer sebelum dilakukan proses encoding. Pada proses encoding bit-bit data tersebut di-encode setiap delapan bitnya sehingga membentuk satu karakter yang dapat dibaca oleh komputer. Begitu juga sebaliknya, pada saat dekompresi bit-bit data tersebut didecode kembali agar membentuk bit-bit data semula yang akan digunakan dalam proses dekompresi. Karena pada saat proses dekompresi dibutuhkan bit-bit data sebelum diEncode untuk dapat dibaca kembali dalam proses dekompresi. Didalam komputer satu karakter direpresentasikan oleh bilangan ASCII (American Standard Code For Information Interchange) sebanyak delapan bit dalam bilangan biner. Jika ternyata jumlah bit-bit data tersebut bukan merupakan kelipatan delapan. Maka dibentuk variabel baru sebagai penambahan ke bit-bit data itu agar bit-bit data tersebut habis dibagi delapan. Variabel ini adalah padding dan flagging.
29
1. Padding Padding adalah penambahan bit 0 sebanyak kekurangan jumlah bit-bit data pada hasil proses kompresi sehingga jumlah keseluruhan bit-bit data tersebut merupakan kelipatan delapan (habis dibagi delapan). Contoh misalkan dihasilkan bit-bit data hasil kompresi yaitu 1001011. Terdapat 7 bit data dalam bilangan biner. Maka dilakukan penambahan bit 0 sebanyak 1 kali agar jumlah bit-bit data tersebut habis dibagi delapan. Sehingga bit bit data itu menjadi 10010110 setelah diberikan padding. 2. Flagging Flagging adalah penambahan bilangan biner sepanjang delapan bit setelah padding dimana flagging ini adalah sejumlah bilangan yang memberikan sebuah tanda bahwa terdapat n buah padding di dalam bit-bit data hasil dari kompresi. Penambahan flagging ini dimaksudkan untuk mempermudah dalam membaca bit-bit data hasil kompresi pada saat proses dekompresi. Contoh misalkan bit-bit data yang telah diberikan padding adalah10010110. Karena terdapat 1 bit penambahan padding maka flag nya adalah bilangan biner dari 1 dengan panjang 8 bit yaitu 00000001. Sehingga bit-bit datanya menjadi 1001011000000001 setelah diberikan flagging. Contoh : Berikut ini adalah contoh proses kompresi file teks dengan metode Elias Gamma Code. Terdapat file teks yang berisikan string “KUKU KAKI KAKAK KAKEKKU KAKU”. Untuk ukuran String dapat dilihat pada Tabel 2.4. Tabel 2.4. String yang Belum Dikompresi char
ASCII Code
ASCII Code (Binary)
Bit
Frek
Bit x Frek
K
75
01001011
8
13
104
A
65
01000001
8
5
40
U
85
01010101
8
4
32
Sp
32
00100000
8
4
32
30
Lanjutan Tabel 2.4. String yang Belum Dikompresi char
ASCII Code
ASCII Code (Binary)
Bit
Frek
Bit x Frek
I
73
01001001
8
1
8
E
69
01000101
8
1
8
Total
224
Berdasarkan kode ASCII, satu karakter bernilai delapan bit bilangan biner. Sehingga 35 karakter pada string mempunyai nilai biner sebanyak 224 bit. Sebelum melakukan proses kompresi, karakter tersebut diurutkan terlebih dahulu berdasarkan dari karakter yang memiliki frekuensi terbesar ke terkecil. Proses kompresi untuk Elias Gamma Code dapat dilihat pada Tabel 2.5 Tabel 2.5. String yang Sudah Dikompresi Dengan Elias Gamma Code char
Elias Gamma Code
Bit
Frek
Bit x Frek
K
1
1
13
13
A
001
3
5
15
U
011
3
4
12
Sp
00001
5
4
20
I
00011
5
1
5
E
01001
5
1
5
Total
70
Dapat dibentuk string bit dari string sebelum dikompresi yaitu “ KUKU KAKI KAKAK KAKEKKU
KAKU”
menjadi
string
bit
“1011101100001100110001100001100110011000011001101001110110000110011011” . Sebelum ditulis ke sebuah file hasil kompresi dilakukan penambahan bit-bit padding dan flagging diakhir String bit. Bit-bit itu dihasilkan dari panjang String bit itu sendiri apakah habis dibagi delapan dan berapa sisanya jika dibagi delapan. Karena jumlah String bit 70 tidak habis dibagi delapan dan sisanya 6. Maka dapat dibuat padding “00”
31
dan
adalah
flaggingnya
“00000010”
menjadi“1011101100001100110001100001100110011000011001101001110110000110 0110110000000010”. Sehingga total bit seluruhnya setelah penambahan padding dan flagging adalah 80 bit.
2.5.3. Pengukuran Kinerja Kompresi Data Pada suatu teknik yang digunakan dalam proses kompresi data terdapat beberapa faktor atau variabel yang biasa digunakan untuk mengukur kualitas dari suatu teknik kompresi data tersebut, yaitu: 1. Ratio of compression (Rc) Ratio of compression (Rc) adalah perbandingan antara ukuran data sebelum dikompresi dengan ukuran data setelah dikompresi. Rc =
𝒖𝒌𝒖𝒓𝒂𝒏 𝒅𝒂𝒕𝒂 𝒔𝒆𝒃𝒆𝒍𝒖𝒎 𝒅𝒊𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊 𝒖𝒌𝒖𝒓𝒂𝒏 𝒅𝒂𝒕𝒂 𝒔𝒆𝒕𝒆𝒍𝒂𝒉 𝒅𝒊𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊
(Salomon dan Motta, 2010)
Misalkan didapat sebuah nilai Ratio of compression sebesar 2.75. Itu berarti besar data sebelum kompresi adalah 2.75 kali lipat dari besar data setelah dikompresi. 2. Compression ratio (Cr) Compression ratio (Cr) adalah persentasi besar data yang telah dikompresi yang didapat dari hasil perbandingan antara ukuran data setelah dikompresi dengan ukuran data sebelum dikompresi. Cr =
𝒖𝒌𝒖𝒓𝒂𝒏 𝒅𝒂𝒕𝒂 𝒔𝒆𝒕𝒆𝒍𝒂𝒉 𝒅𝒊𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊 𝒖𝒌𝒖𝒓𝒂𝒏 𝒅𝒂𝒕𝒂 𝒔𝒆𝒃𝒆𝒍𝒖𝒎 𝒅𝒊𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊
x 100% (Salomon dan Motta, 2010)
Misalkan didapat sebuah nilai Compression ratio sebesar 35%. Itu berarti setelah dikompresi ukuran data adalah 35% dari data sebelum dikompresi.
32
3. Redundancy (Rd) Redundancy (Rd) adalah kelebihan yang terdapat di dalam data sebelum dikompresi. Jadi setelah data dikompresi dapat dihitung Redundancy data yaitu persentasi dari hasil selisih antara ukuran data sebelum dikompresi dengan data setelah dikompresi. 𝑹𝒅=𝟏𝟎𝟎%−𝑪𝒓(Salomon dan Motta, 2010) Misalkan didapat sebuah nilai Redundancy sebesar 14%. Itu berarti besarnya kelebihan data sebelum dikompresi adalah 14%.
