pengukuran running time dari setiap perlakuan. Ulangan setiap perlakuan dilakukan sebanyak 10 kali untuk masing-masing RSA dan RSACRT. Lingkungan Penelitian Perangkat keras dan perangkat lunak yang digunakan adalah sebagai berikut. a. Perangkat lunak: sistem operasi Windows XP Professional Edition dan aplikasi bahasa pemrograman Java, b. Perangkat keras: Prosesor Intel Core Duo.
HASIL DAN PEMBAHASAN Analisis Algoritma Pada penelitian ini dilakukan analisis terhadap algoritma RSA dan RSA-CRT. Algoritma tersebut dapat dibagi menjadi tiga bagian utama, yaitu algoritma pembangkitan kunci, algoritma enkripsi, dan algoritma dekripsi. Adapun subrutin-subrutinnya diacu dari Menezes. Masing-masing algoritma tersebut dapat dilihat pada analisis berikut. 1. Analisis Subrutin RSA dan RSA-CRT 1.1 Analisis Subrutin Primality Test Pada subrutin ini RSA menggunakan algoritma Miller-Rabin. Algoritma Miller-Rabin adalah sebagai berikut. (a) x ;= am mod n; (b) If (x ≡ 1 mod n) return ”n is prime” and halt; (c) For (j = 0, 1, ..., k-1) (d) If (x ≡ -1 mod n) return ”n is prime” and halt; (e) Else x := x2 mod n; (f) Return ”n is composite” and halt; Subrutin Primality Test menggunakan algoritma modular exponentiation, sehingga kompleksitasnya adalah O((lg n)3). (Menezes et al. 1996). 1.2 Analisis Subrutin Euclid Subrutin Euclid berfungsi untuk menentukan gcd antara 2 bilangan bulat a dan b. Algoritma subrutin Euclid adalah sebagai berikut. (a) If b = 0 Then (b) Euclid a (c) Else (d) Euclid (b, a mod b) Proses ini dilakukan dengan menggunakan algoritma perkalian, sehingga kompleksitasnya adalah O((lg n)2). (Menezes et al. 1996).
1.3 Analisis Subrutin Extended Euclid Subrutin Extended Euclid digunakan untuk mencari kunci pribadi. Algoritma subrutin Extended Euclid adalah sebagai berikut. (a) If b = 0 Then (b) return (a, 1, 0) (c) (d1, x1, y1) Extended Euclid (b, a, mod b) (d) (d, x, y) (d1, y1, x1 - a/b y1) (e) return (d, x, y) Subrutin Extended Euclid juga menggunakan algoritma perkalian, sama seperti pada subrutin Euclid, sehingga kompleksitasnya adalah O((lg n)2). (Menezes et al. 1996). 1.4 Analisis Subrutin Modular Exponentiation Algoritma Modular Exponentiation digunakan untuk melakukan operasi modular, ab mod n. Algoritmanya adalah sebagai berikut. (a) d 1 (b) Andaikan (b1, b2 , ... bk-1, bk) adalah representasi biner dari b (c) Untuk i 1 sampai k lakukan (d) d (d*d) mod n (e) Jika bi = 1 maka (f) d (d*a) mod n (g) Modular Exponentiation d Algoritma Modular Exponentiation mempunyai kompleksitas sebesar O((lg n)3) (Menezes et al. 1996). 2. Analisis Algoritma RSA 2.1 Analisis Algoritma Pembangkitan Kunci (a) Pilih dua bilangan prima, p dan q secara acak dan terpisah untuk setiap p dan q. (b) Hitung n = p x q. (c) Hitung (n) = (p-1) (q-1). (d) Pilih bilangan bulat antara satu dan (1<e<) yang juga merupakan coprime dari . Coprime yang dimaksud adalah bilangan terbesar yang dapat membagi e dan untuk menghasilkan nilai 1 (pembagi ini dinyatakan dengan gcd. (e) Hitung d, dimana d e-1 mod (n). Pada baris (a), diperlukan algoritma MillerRabin untuk menentukan prima tidaknya suatu bilangan, sehingga kompleksitasnya sebesar O((lg n)3). Baris (b) dan (c) merupakan
perkalian biasa, sehingga kompleksitasnya adalah O((lg n)2). Baris (d) menggunakan subrutin Euclid, sehingga kompleksitasnya adalah O((lg n)2). Baris (e) menggunakan subrutin Extended Euclid yang mempunyai kompleksitas sebesar O((lg n)2). Jadi total secara keseluruhan, kompleksitas algoritma pembangkitan kunci pada RSA adalah O((lg n)3). 2.2 Analisis Algoritma Enkripsi Diagram alir proses enkripsi pada algoritma RSA dapat dilihat pada Gambar 2.
Plaintext
Kunci Publik (n,e)
Proses Enkripsi Pesan
Ciphertext
Gambar 2 Proses enkripsi pesan pada RSA Proses enkripsi pesan pada RSA adalah menghitung C, dimana C = Me (mod n), dengan e adalah eksponen enkripsi, M adalah plaintext, C adalah ciphertext, dan n adalah modulus. Proses ini dilakukan menggunakan algoritma modular exponentiation, sehingga kompleksitasnya adalah O((lg n)3). 2.3 Analisis Algoritma Dekripsi Diagram alir proses dekripsi pada algoritma RSA dapat dilihat pada Gambar 3.
Gambar 3 Proses dekripsi pesan pada RSA Proses dekripsi pesan pada RSA adalah menghitung M, dimana M = Cd (mod n), dengan d adalah eksponen dekripsi, M adalah plaintext, C adalah ciphertext, dan n adalah modulus. Proses ini dilakukan menggunakan algoritma modular exponentiation, sehingga kompleksitasnya adalah O((lg n)3). 3. Analisis Algoritma RSA-CRT 3.1 Analisis Algoritma Pembangkitan Kunci (a) Pilih bilangan prima p dan q secara acak, sehingga gcd (p-1, q-1) = 2. (b) Hitung n = p x q. (c) Pilih 2 bilangan bulat dp dan dq secara acak, sehingga gcd (dp, p-1) = 1, gcd (dq, q-1) = 1dan dp == dq mod 2. (d) Cari suatu nilai d sehingga d == dp mod p-1 dan d == dq mod q-1. (e) Hitung e = d-1 (mod (n)). Pada baris (a) menggunakan algoritma Miller-Rabin, sehingga kompleksitasnya adalah O((lg n)3). Baris (b) merupakan perkalian biasa, sehingga kompleksitasnya adalah O((lg n)2). Pada baris (c), dp Є Z* p-1 dan dq Є Z* q-1. Didapat O((lg (p-1) 2) + (lg (q-1)2)) = O((lg (n/2))2 . Baris (d) merupakan operasi modular biasa, sehingga didapat, O((lg (p-1)) + (lg (q1))) = O((lg (n/2)). Baris (e) menggunakan subrutin Extended Euclid yang mempunyai kompleksitas sebesar O((lg n)2). Jadi total secara keseluruhan, kompleksitas algoritma pembangkitan kunci pada RSA-CRT adalah O((lg n)3). 3.2 Analisis Algoritma Enkripsi Diagram alir proses enkripsi pada algoritma RSA-CRT dapat dilihat pada Gambar 4.
mempunyai kompleksitas sebesar O((lg (n/2))2). Pada baris (c) dapat diperoleh, O((lg p) ((lg (n/2))2 ) = O((lg (n/2))3). Jadi total secara keseluruhan, kompleksitas algoritma dekripsi pada RSA-CRT adalah O((lg (n/2))3).
Gambar 4 Proses enkripsi pesan pada RSACRT Proses enkripsi pesan pada RSA-CRT adalah menghitung C, dimana C = Me (mod n), dengan e adalah eksponen enkripsi, M adalah plaintext, C adalah ciphertext, dan n adalah modulus. Proses ini dilakukan menggunakan algoritma modular exponentiation, sehingga kompleksitasnya adalah O((lg n)3). 3.3 Analisis Algoritma Dekripsi Diagram alir proses dekripsi pada algoritma RSA-CRT dapat dilihat pada Gambar 5.
Gambar 5 Proses dekripsi pesan pada RSACRT Algoritma dekripsi pada RSA-CRT adalah sebagai berikut. (a) Mp = Cdp mod p dan Mq = Cdq mod q (b) v = (Mq – Mp) p_inv_q mod q (c) M = Mp + pv Pada baris (a) menggunakan algoritma modular exponentiation, sehingga di dapat, O(((lg p)3) + ((lg q)3)) = O((lg (n/2))3). Baris (b)
Analisis Keamanan Kekuatan algoritma RSA terletak pada tingkat kesulitan memfaktorkan modulus n. Jika n berhasil difaktorkan menjadi p dan q, maka (n) = (p-1) (q-1) dapat dihitung. Selanjutnya, karena kunci enkripsi e tidak rahasia, maka kunci dekripsi d dapat dihitung dari persamaan d e-1 mod (n). Algoritma RSA dikatakan aman jika penyerang sulit memfaktorkan modulus n menjadi p dan q. Untuk n yang besar dengan faktor prima yang besar juga, akan sulit untuk memfaktorkannya. Hal ini yang menjadi alasan mengapa RSA bertumpu kepada faktorisasi bilangan bulat. Nilai p dan q panjangnya lebih dari 100 digit. Dengan demikian hasil kali n = p x q akan lebih dari 200 digit. Usaha untuk memfaktorkan bilangan bulat 200 digit menjadi faktornya sangat besar. Ada beberapa serangan terhadap implementasi RSA. Serangan-serangan ini umumnya mengeksploitasi kelemahan dalam cara RSA digunakan, bukan merusak algoritma RSA. Berikut ini adalah beberapa serangannya, yang secara teori dapat dilakukan. 1. Brute force Diberikan c = me mod n, coba semua nilai kunci d ; 0 ≤ e ≤ (n) untuk memenuhi m = cd mod n. Dalam prakteknya, │K│ = (n) ≈ 2500 ruang kunci yang begitu besar tidak memungkinkan untuk menemukan d. 2. Mencari (n) Diberikan n, e, c = me mod n. Cari (n) dan hitung d = e-1 mod (n). menghitung (n) dipercaya sesulit memfaktorkan n. 3. Langsung mencari nilai d Diberikan n, e, c = me mod n. Cari nilai d dan hitung m = cd mod n. menghitung d dipercaya sesulit memfaktorkan n. 4. Memfaktorkan n Diberikan n, e, c = me mod n, faktor p x q = n, kemudian hitung : (n) = (p-1) (q-1) e = d-1 mod (n) m = cd mod n Sangat sulit mefaktorkan n. Tabel 1 berikut adalah waktu yang diperlukan untuk memfaktorkan n. (Menezes et al. 1996).
Tabel 1 Waktu MIPS untuk faktorisasi n Desimal
Bit
100 110 120 129 130 140
332 365 398 428 431 465
Waktu MIPS 7 75 830 5000 1000 2000
155
512
8000
Algoritma QS QS QS QS GNFS GNFS GNFS
Keterangan : QS = Quadratic Sieve GNFS = Generalized Number Field Sieve Analisis Hasil Implementasi Implementasi algoritma RSA dan RSA-CRT dilakukan dengan menggunakan bahasa pemrograman Java. Hal ini didasarkan atas pertimbangan bahwa Java mampu membangkitkan bilangan besar. Class yang dipakai adalah BigInteger. Java memperlakukan BigInteger sebagai string, sehingga tidak akan terjadi overflow. Sistem diimplementasikan dengan menggunakan metode client-server. Tampilan program client dan server dapat dilihat pada Lampiran 1 dan Lampiran 2. Untuk dapat berkomunikasi, server membuka koneksi terlebih dahulu. Setelah itu, client juga membuka koneksinya. Tampilan saat melakukan koneksi pada client dan server dapat dilihat pada Lampiran 3 dan Lampiran 4. Sebelum pengiriman pesan dimulai, kunci dibangkitan terlebih dahulu. Contoh pembangkitan kunci dapat dilihat pada Lampiran 7. Ada dua algoritma yang tersedia, yaitu RSA dan RSA-CRT. Pengiriman pesan dalam satu waktu hanya bisa memilih salah satu diantara kedua algoritma tersebut. Contoh pengiriman pesannya dapat dilihat pada Lampiran 5 dan Lampiran 6. Dari hasil implementasi ini dilakukan pengukuran waktu enkripsi dan dekripsi, serta membandingkan waktu enkripsi dan dekripsi dari RSA dan RSA-CRT. Nilai e (eksponen enkripsi) yang dipakai adalah 65537, nilai eksponen ini dianjurkan supaya waktu komputasinya bisa cepat dan kemanan tetap terjaga. Contoh plaintext, ciphertext, dan hasil dekripsi masing-masing dapat dilihat pada Lampiran 8, Lampiran 9, dan Lampiran 10. Tujuan dari membandingkan waktu enkripsi dan dekripsi kedua algoritma ini adalah untuk
membuktikan bahwa penambahan CRT pada algoritma RSA berdampak pada meningkatnya kecepatan waktu dekripsi. Penambahan CRT tidak berdampak pada waktu enkripsi, jadi secara teori waktu enkripsi RSA dan RSA-CRT relatif sama. Pengukuran dilakukan dengan menggunakan 10 ukuran file teks yang berbeda dalam selang 1764 byte sampai dengan 21168 byte sebagai obyek kajian, dengan perulangan untuk setiap perlakuan sebanyak 10 kali. Hasil pengukuran waktu enkripsi dan dekripsi pada RSA dan RSA-CRT dapat dilihat pada Tabel 2, Tabel 3, Tabel 4, dan Tabel 5. Tabel 2 Hasil pengukuran waktu enkripsi RSA NO
Ukuran File (byte)
1 2 3 4 5
1764 3528 5292 8820 10584
Waktu Enkripsi (ms) 21.8 36 54.6 101.6 112.6
6
12348
125
7 8
14112 15876
134.5
9
17640
170.3
10 21168 Waktu Rata-rata (ms)
135.8 181.2 107.34
Tabel 3 Hasil pengukuran waktu dekripsi RSA NO
Ukuran File (byte)
1 2 3 4 5 6 7 8 9
1764 3528 5292 8820 10584 12348 14112 15876 17640
10 21168 Waktu Rata-rata (ms)
Waktu Dekripsi (ms) 610.8 1401.7 2348.3 3814.4 3995.3 4411 5162.5 5689.2 6511.1 8173.6 4211.79
Tabel 4 Hasil pengukuran waktu enkripsi RSACRT NO
Ukuran File (byte)
1 2 3 4 5
1764 3528 5292 8820 10584
Waktu Enkripsi (ms) 20.4 38.9 73.6 104.6 121.8
6 7
12348 14112
134.1 148.5
8
15876
149.9
9
17640
151.6
10 21168 Waktu Rata-rata (ms)
dekripsi RSA adalah 4211.79 ms, sedangkan pada RSA-CRT adalah 1372.44 ms. Dari data ini, dapat diperoleh bahwa RSA-CRT pada percobaan dengan 10 kali pengulangan, 3 kali lebih cepat dari RSA. Penambahan CRT pada RSA terbukti mampu mempercepat proses dekripsi. Rincian waktu eksekusi dekripsi pada RSA dan RSA-CRT dapat dilihat pada Lampiran 12 dan Lampiran 14. Pada RSA-CRT, perhitungan modulo p dan modulo q dipecah menggunakan CRT. Hal inilah yang menyebabkan komputasi dekripsi pada RSA-CRT menjadi lebih cepat dibandingkan pada RSA. Perbandingan waktu enkripsi dan dekripsi pada RSA dan RSA-CRT terhadap ukuran file dapat dilihat pada Gambar 6 dan Gambar 7.
168.6 111.2
Tabel 5 Hasil pengukuran waktu dekripsi RSACRT NO
Ukuran File (byte)
1 2 3 4 5 6 7 8 9
1764 3528 5292 8820 10584 12348 14112 15876 17640
10 21168 Waktu Rata-rata (ms)
Waktu Enkripsi (ms) 317 626.5 845.5 1243.8 1357.7 1374.9 1503 1726.4 2353.2
Gambar 6 Grafik hubungan waktu enkripsi RSA dan RSA-CRT terhadap ukuran file Dari gambar 6, dapat terlihat bahwa waktu enkripsi RSA dan RSA-CRT tidak berbeda jauh. Algoritma enkripsi pada RSA-CRT sama dengan RSA, yaitu C = Me (mod n).
2376.4 1372.44
Berdasarkan Tabel 2 dan Tabel 4, waktu rata-rata enkripsi RSA dan RSA-CRT masingmasing adalah 107.34 ms dan 111.2 ms. Nilai ini bisa dikatakan hampir sama. Penambahan CRT tidak berpengaruh pada enkripsi. Hal ini dikarenakan penambahan CRT dilakukan pada dekripsi saja bukan pada enkripsi. Seiring meningkatnya ukuran file, waktu enkripsi juga mengalami peningkatan. Rincian waktu eksekusi enkripsi pada RSA dan RSA-CRT dapat dilihat pada Lampiran 11 dan Lampiran 13. Dari data Tabel 3 dan Tabel 5, dapat dilihat bahwa waktu rata-rata dekripsi pada RSA-CRT lebih cepat dibandingkan pada RSA. Waktu
Gambar 7 Grafik hubungan waktu dekripsi RSA dan RSA-CRT terhadap ukuran file Pada Grafik 7, jelas terlihat waktu komputasi RSA lebih lambat dibandingkan RSA-CRT. RSA-CRT mengalami peningkatan waktu komputasi dekripsi yang relatif rendah, sedangkan RSA mengalami peningkatan waktu komputasi dekripsi yang lebih pesat. Hal ini
