ANALISIS RSA DENGAN PENAMBAHAN CHINESE REMAINDER THEOREM UNTUK MEMPERCEPAT PROSES DEKRIPSI
NILAM AMALIA PUSPARANI G64102039
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2009
ANALISIS RSA DENGAN PENAMBAHAN CHINESE REMAINDER THEOREM UNTUK MEMPERCEPAT PROSES DEKRIPSI
Skripsi
sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh:
NILAM AMALIA PUSPARANI G64102039
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2009
ABSTRAK
NILAM AMALIA PUSPARANI. Analisis RSA dengan Penambahan Chinese Remainder Theorem untuk Mempercepat Proses Dekripsi. Dibimbing oleh Dr. Sugi Guritman dan Panji Wasmana, S.Kom., M.Si. RSA merupakan algoritma kunci publik yang keamanannya bertumpu pada kesulitan untuk memfaktorkan modulus n yang sangat besar, tetapi kelebihan ini mengakibatkan lambatnya waktu untuk menyelesaikan proses. Penambahan CRT pada RSA diperlukan untuk mengefisienkan kinerja RSA. Penelitian ini bertujuan untuk mempelajari kinerja RSA dari segi kecepatan dan keamanannya, serta menganalisis algoritmanya. Analisis kecepatan dilakukan dengan mengukur waktu kecepatan rata-rata enkripsi dan dekripsi RSA dan RSA-CRT. Analisis keamanan dilakukan melalui studi literatur. Dari hasil analisis algoritma, dapat ditarik kesimpulan bahwa RSA dan RSA-CRT memiliki kompleksitas yang sama untuk algoritma pembangkitan kunci dan proses enkripsi, yaitu O((lg n)3). Tetapi pada pembangkitan kunci RSA-CRT, ada bagian yang kompleksitasnya O((lg (n/2))2). Algoritma dekripsi RSA memiliki kompleksitas O((lg n)3), sedangkan RSA-CRT memiliki kompleksitas O((lg (n/2))3). Hasil ini dikuatkan oleh hasil implementasi yang memperoleh waktu dekripsi RSA-CRT yang lebih cepat dibandingkan waktu dekripsi RSA. Waktu rata-rata running time proses dekripsi RSA adalah 4211.79 ms, sedangkan pada RSA-CRT diperoleh running time rata-rata proses dekripsi 1372.44 ms. Kata kunci : RSA, RSA-CRT, Chinese Remainder Theorem.
Judul
: Analisis RSA dengan Penambahan Chinese Remainder Theorem untuk Mempercepat Proses Dekripsi
Nama
: Nilam Amalia Pusparani
NRP
: G64102039
Menyetujui: Pembimbing I,
Pembimbing II,
Dr. Sugi Guritman
Panji Wasmana, S.Kom., M.Si
NIP 131999582
NIP 132311917
Mengetahui: Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Dr. drh. Hasim, DEA NIP 131578806
Tanggal Lulus:
PRAKATA
Puji syukur diucapkan ke hadirat Allah SWT atas segala curahan rahmat dan karunia-Nya sehingga skripsi ini dapat diselesaikan. Skripsi ini merupakan hasil penelitian dengan bidang kajian Analisis RSA dengan Penambahan Chinese Remainder Theorem untuk Mempercepat Proses Dekripsi. Terima kasih kepada Bapak Dr. Sugi Guritman selaku pembimbing I yang telah banyak membantu dalam menyusun skripsi ini. Terima kasih juga diucapkan kepada Bapak Panji Wasmana, S.Kom., M.Si selaku pembimbing II yang telah banyak memberi saran, masukan, dan ide-ide. Ucapan terima kasih juga kepada Bapak Sony Hartono Wijaya, S.Kom, M.Kom selaku penguji yang telah banyak memberi saran dan masukan. Terima kasih juga diucapkan kepada: 1 Papa dan Mama yang selalu memberikan doa, nasihat, dukungan, semangat, dan kasih sayang yang luar biasa sehingga tugas akhir ini dapat terselesaikan. 2 Aa Galuh dan Teh Wita yang selalu memberikan semangat dan dukungan. 3 Kang Irfan Shidqon yang telah menyemangati dan menemani saat-saat tersulit dalam penyelesain tugas akhir ini. 4 Mba Anggun yang telah menjadi sahabat terbaik. 5 Mas Ifnu dan Dian yang telah banyak membantu disaat sedang susah. 6 Ardi, Erna, dan Zaki M yang telah menjadi sahabat yang menemani dalam suka dan duka. 7 Phia dan Hilma atas persahabatannya yang indah. 8 Setya yang sering membantu menjelaskan program dan menghilangkan virus di laptop. 9 Lana, Riza, dan Musa yang telah memberikan dukungan, inspirasi, dan membantu selama perkuliahan di IPB. 10 Martin, Jefry, dan Wikhdal yang telah bersedia menjadi pembahas seminar. 11 Teman-teman yang berada dalam satu bimbingan: Nurul, Fitri, Alfath, Adi, dan Kaspar atas kerjasamanya selama penelitian. 12 Teman-teman Ilkom angkatan 39 yang telah banyak membantu selama menjalani perkuliahan di IPB. 13 Departemen Ilmu Komputer, staf, dan dosen yang telah banyak membantu baik selama penelitian maupun pada masa perkuliahan. Kepada semua pihak lainnya yang telah memberikan kontribusi yang besar selama pengerjaan penelitian ini yang tidak dapat disebutkan satu-persatu, Penulis ucapkan terima kasih banyak. Semoga penelitian ini dapat memberikan manfaat.
Bogor, Januari 2009
Nilam Amalia Pusparani
RIWAYAT HIDUP
Penulis dilahirkan di Semarang pada tanggal 4 Mei 1985 dari ayah Endhay Kusnendar Mulyana Kontara dan ibu Iin Siti Djunaidah. Penulis merupakan anak kedua dari dua bersaudara. Tahun 2002 Penulis lulus dari SMUN 1 Jepara dan pada tahun yang sama lulus seleksi masuk IPB melalui jalur Undangan Seleksi Masuk IPB. Penulis memilih Program Studi Ilmu Komputer, Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam IPB. Pada tahun 2005 Penulis melakukan kegiatan praktek lapang di Seameo Biotrop (Southeast Asian Regional Centre for Tropical Biology) Bogor selama kurang lebih dua bulan.
DAFTAR ISI Halaman DAFTAR TABEL.......................................................................................................................................... vii DAFTAR GAMBAR...................................................................................................................................... vii DAFTAR LAMPIRAN .................................................................................................................................. vii PENDAHULUAN Latar Belakang............................................................................................................................................. 1 Tujuan Penelitian ......................................................................................................................................... 1 Ruang Lingkup ............................................................................................................................................ 1 TINJAUAN PUSTAKA Kriptografi ................................................................................................................................................... 1 Kriptanalisis................................................................................................................................................. 1 Kriptosistem................................................................................................................................................. 1 Fungsi Satu Arah Pintu Jebakan ................................................................................................................... 2 Enkripsi Kunci Publik .................................................................................................................................. 2 RSA (Rivest-Shamir-Adleman) .................................................................................................................... 2 Algoritma Euclid.......................................................................................................................................... 2 Relatif Prima................................................................................................................................................ 3 CRT (The Chinese Remainder Theorem) ...................................................................................................... 3 RSA-CRT (Rivest-Shamir-Adleman-Chinese Remainder Theorem) .............................................................. 4 Analisis Algoritma ....................................................................................................................................... 4 Analisis Uji Running Time............................................................................................................................ 4 METODE PENELITIAN Analisis Algoritma ....................................................................................................................................... 4 Analisis Keamanan....................................................................................................................................... 4 Analisis Hasil Implementasi ......................................................................................................................... 4 Spesifikasi Uji Implementasi ........................................................................................................................ 4 Lingkungan Penelitian.................................................................................................................................. 5 HASIL DAN PEMBAHASAN Analisis Algoritma ....................................................................................................................................... 5 1. Analisis Subrutin RSA dan RSA-CRT ...................................................................................................... 5 1.1 Analisis Subrutin Primality Test........................................................................................................... 5 1.2 Analisis Subrutin Euclid ...................................................................................................................... 5 1.3 Analisis Subrutin Extended Euclid ....................................................................................................... 5 1.4. Analisis Subrutin Modular Exponentiation.......................................................................................... 5 2. Analisis Algoritma RSA ........................................................................................................................... 5 2.1 Analisis Algoritma Pembangkitan Kunci.............................................................................................. 5 2.2 Analisis Algoritma Enkripsi................................................................................................................. 6 2.3 Analisis Algorirma Dekripsi ................................................................................................................ 6
Halaman 3. Analisis Algoritma RSA-CRT .................................................................................................................. 6 3.1 Analisis Algoritma Pembangkitan Kunci.............................................................................................. 6 3.2 Analisis Algoritma Enkripsi ................................................................................................................. 6 3.3 Analisis Algorirma Dekripsi ................................................................................................................ 7 Analisis Kemanan ........................................................................................................................................ 7 Analisis Hasil Implementasi ......................................................................................................................... 8 KESIMPULAN DAN SARAN Kesimpulan................................................................................................................................................ 10 Saran ......................................................................................................................................................... 10 DAFTAR PUSTAKA..................................................................................................................................... 10 LAMPIRAN .................................................................................................................................................. 11
DAFTAR TABEL Halaman 1
Waktu MIPS untuk Faktorisasi n ......................................................................................................... 7
2
Hasil pengukuran waktu enkripsi RSA ................................................................................................ 8
3
Hasil pengukuran waktu dekripsi RSA ................................................................................................ 8
4
Hasil pengukuran waktu enkripsi RSA-CRT........................................................................................ 8
5
Hasil pengukuran waktu dekripsi RSA-CRT........................................................................................ 9
DAFTAR GAMBAR Halaman 1
Teknik enkripsi menggunakan kunci publik......................................................................................... 2
2
Proses enkripsi pesan pada RSA.......................................................................................................... 6
3
Proses dekripsi pesan pada RSA.......................................................................................................... 6
4
Proses enkripsi pesan pada RSA-CRT ................................................................................................. 6
5
Proses dekripsi pesan pada RSA-CRT ................................................................................................. 7
6
Grafik hubungan waktu enkripsi RSA dan RSA-CRT terhadap ukuran file........................................... 9
7
Grafik hubungan waktu dekripsi RSA dan RSA-CRT terhadap ukuran file........................................... 9
DAFTAR LAMPIRAN Halaman 1
Tampilan client ................................................................................................................................. 12
2
Tampilan server................................................................................................................................ 12
3
Tampilan saat melakukan koneksi pada client.................................................................................... 13
4
Tampilan saat melakukan koneksi pada server................................................................................... 13
5
Contoh pengiriman pesan dari client ke server menggunakan algoritma RSA..................................... 14
6
Contoh pengiriman pesan dari server ke client menggunakan algoritma RSA-CRT ............................ 15
7
Hasil pembangkitan kunci ................................................................................................................. 16
8
Contoh plaintext ............................................................................................................................... 17
9
Ciphertext......................................................................................................................................... 18
10 Hasil proses dekripsi ......................................................................................................................... 20 11 Rincian waktu eksekusi enkripsi pada RSA ....................................................................................... 21 12 Rincian waktu eksekusi dekripsi pada RSA ....................................................................................... 21 13 Rincian waktu eksekusi enkripsi pada RSA-CRT............................................................................... 22 14 Rincian waktu eksekusi dekripsi pada RSA-CRT............................................................................... 22
PENDAHULUAN Latar Belakang Dalam era globalisasi sekarang ini, keamanan merupakan aspek yang sangat penting dalam transaksi informasi. Informasi yang dipertukarkan tidak semuanya terbuka bagi setiap orang. Informasi tersebut terkadang hanya ditujukan bagi kalangan tertentu saja dan dijaga kerahasiaanya dari orang lain. Teknik mengamankan informasi tersebut erat kaitannya dengan kriptografi. Kriptografi adalah studi teknik matematik yang berkaitan dengan aspek keamanan informasi seperti kerahasiaan, integritas data, autentikasi entitas, dan autentikasi asal data (Menezes et al. 1996). Dalam kriptografi, ada dua proses yang sangat penting, yaitu enkripsi dan dekripsi. Enkripsi merupakan proses mengubah pesan asli (plaintext) menjadi pesan yang dikodekan (ciphertext). Sedangkan dekripsi adalah proses mendapatkan plaintext dari ciphertext. Beberapa algoritma yang digunakan untuk enkripsi dan dekripsi pesan, misalnya Data Encryption Standard (DES), Triple-DES, Advanced Encryption Standard (AES), Blowfish, 3DES, RC5, RSA, dan lain sebagainya. RSA adalah sebuah algoritma pada enkripsi kunci publik yang dikembangkan oleh RivestShamir-Adleman. Algoritma ini menggunakan kunci yang berbeda untuk enkripsi dan dekripsi. Keamanan metode ini terletak pada kesulitan untuk memfaktorkan modulus n yang sangat besar, tetapi kelebihan ini mengakibatkan lambatnya waktu untuk menyelesaikan proses. Sedangkan RSA-CRT adalah RSA yang dimodifikasi dengan menggunakan CRT yang bertujuan untuk mempercepat proses dekripsi. Quadratic Sieve dan Generalized Number Field Sieve merupakan algoritma faktorisasi bilangan bulat yang dapat menyerang RSA. Untuk mengatasi hal ini, maka dipilih nilai n yang besar. Nilai n besar membutuhkan sumber daya yang besar juga, maka dari itu diperlukan RSA-CRT untuk mengefisiensikan kinerja RSA. Tujuan Tujuan dari penelitian ini adalah: 1. Mengimplementasikan skema enkripsi dan dekripsi RSA dan RSA-CRT. 2. Menganalisis tingkat keamanan serta waktu yang dibutuhkan untuk proses enkripsi dan dekripsi.
Ruang Lingkup Penelitian ini menggunakan RSA sebagai algoritma enkripsi dan dekripsi pesan dan penambahan CRT pada RSA-CRT. Modulus n yang digunakan sepanjang 1024 bit. Penelitian dititikberatkan pada analisis algoritma dan kinerja algoritma RSA dan RSACRT yang meliputi analisis keamanan melalui telaah pustaka dan analisis uji running time enkripsi dan dekripsi. Data yang digunakan dalam percobaan adalah file teks (.txt) dengan ukuran yang bervariasi dari 1764 byte sampai dengan 21168 byte.
TINJAUAN PUSTAKA Kriptografi Kriptografi adalah studi teknik matematik yang berkaitan dengan aspek keamanan informasi seperti kerahasiaan, integritas data, autentikasi entitas, dan autentikasi asal data (Menezes et al. 1996). Kriptografi dapat memenuhi kebutuhan umum suatu transaksi yaitu: 1. Kerahasiaan (confidentiality) dijamin dengan melakukan enkripsi (penyandian). 2. Keutuhan (integrity) atas data-data pembayaran dilakukan dengan fungsi hash satu arah. 3. Jaminan atas identitas dan keabsahan (authenticity) pihak-pihak yang melakukan transaksi dilakukan dengan menggunakan password atau sertifikat dijital. Sedangkan keautentikan data transaksi dapat dilakukan dengan tanda tangan dijital. 4. Transaksi dapat dijadikan barang bukti yang tidak bisa disangkal (nonrepudiation) dengan memanfaatkan tanda tangan digital dan sertifikat dijital. Kriptanalisis Kriptanalisis adalah suatu ilmu dan seni membuka (breaking) ciphertext. Orang yang melakukannya disebut kriptanalis (Stallings 2003). Kriptosistem Kriptosistem adalah suatu fasilitas untuk mengkonversikan plaintext ke ciphertext dan sebaliknya. Proses enkripsi dan dekripsi diatur oleh satu atau beberapa kunci kriptografi. Secara umum, kunci-kunci yang digunakan untuk proses pengenkripsian dan pendekripsisan tidak perlu identik, tergantung pada sistem yang digunakan (Stallings 2003).
Fungsi Satu Arah Pintu Jebakan Fungsi satu arah pintu jebakan adalah fungsi satu arah f : A B yang apabila diberikan informasi ekstra, maka perhitungan mencari nilai x A, diketahui y B sehingga y = f(x), menjadi mudah (Guritman 2003). Enkripsi Kunci Publik Pada enkripsi kunci publik, satu kunci digunakan untuk enkripsi dan satu kunci digunakan untuk dekripsi. Kunci enkripsi disediakan untuk umum, sedangkan kunci dekripsi harus dijaga kerahasiannya. Pengirim dan penerima pesan harus mempunyai satu dari pasangan kunci yang cocok. Algoritma ini mempunyai karakteristik yang penting yaitu secara perhitungan tidak layak menentukan kunci dekripsi dari kunci enkripsi (Stallings 2003). Berikut ini adalah hal-hal yang dibutuhkan supaya keamanan enkripsi kunci publik tetap terjaga. 1. Salah satu kunci harus dijaga kerahasiannya. 2. Pesan tidak dapat di-dechipher jika tidak ada informasi ekstra. 3. Kunci yang lain tidak bisa ditentukan walaupun dilengkapi dengan pengetahuan mengenai algoritma, salah satu kunci, dan contoh-contoh dari ciphertext. Misalkan {Ee/e K} adalah himpunan semua transformasi enkripsi dan {Dd/d K} adalah himpunan semua transformasi dekripsi yang terkait, dimana K adalah ruang kunci. Pasangan transfromasi (Ee, Dd) mempunyai sifat bahwa diketahui Ee dan sembarang c C, secara perhitungan tidak layak dapat menentukan m M sehingga Ee(m) = c. Diasumsikan bahwa transformasi enkripsi Ee adalah fungsi satu arah pintu jebakan, sehingga kunci dekripsi d dapat dihitung dari e yang ditambahkan informasi ekstra.
Dalam penggunaan model enkripsi ini, kunci yang digunakan berbeda untuk enkripsi dan dekripsi. Digambarkan pada Gambar 1, pembangkitan kunci akan menghasilkan dua buah kunci, yaitu kunci enkripsi dan kunci dekripsi. Kunci enkripsi dapat diketahui oleh umum, sedangkan kunci dekripsi dijaga kerahasiannya. RSA (Rivest-Shamir-Adleman) RSA adalah sebuah algoritma pada enkripsi kunci publik yang dikembangkan oleh RivestShamir-Adleman. Algoritma ini menggunakan kunci publik untuk enkripsi dan kunci pribadi untuk dekripsi. Keamanan metode ini terletak pada kesulitan untuk memfaktorkan modulus n yang sangat besar, tetapi kelebihan ini mengakibatkan lambatnya waktu untuk menyelesaikan proses. Algoritma ini memberikan tujuan kerahasiaan dan penandaan dijital. Keamanan bertumpu kepada kompleksitas problem faktorisasi bilangan bulat. Tiga tahapan dari algoritma RSA adalah pembangkitan kunci, enkripsi, dan dekripsi. Enkripsi adalah proses mengubah pesan asli (plaintext) menjadi pesan yang dikodekan (ciphertext), sedangkan dekripsi adalah proses mendapatkan plaintext dari ciphertext (Stallings 2003). Pembangkitan kuncinya adalah sebagai berikut. 1. Pilih dua bilangan prima, p dan q secara acak dan terpisah untuk setiap p dan q. Hitung n = p x q. 2. Hitung (n) = (p-1) (q-1). 3. 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 (greatest common divisor). 4. Hitung d, dimana d e-1 mod (n). Enkripsi pada RSA adalah sebagai berikut. 1. Plaintext : M < n. 2. Ciphertext : C = Me (mod n). Dekripsi pada RSA adalah sebagai berikut. 1. Ciphertext : C. 2. Plaintext : M = Cd (mod n).
Gambar 1 Teknik enkripsi menggunakan kunci publik.
Algoritma Euclid Algoritma Euclid merupakan salah satu teknik dalam teori bilangan yang berfungsi untuk menentukan gcd dari dua bilangan bulat positif (Stallings 2003). Jika a, b +, maka
dengan algoritma pembagian berlaku langkahlangkah berikut ini. Langkah ke-1 a = q1b + r1 0< r1
Aa;Bb if B = 0 return A = gcd (a, b) R = A mod B AB BR goto 2
Algoritma Euclid dapat diperluas sehingga tidak hanya menghasilkan gcd dari dua bilangan bulat a dan b, tetapi juga menghasilkan bilangan bulat x dan y yang memenuhi ax + by = d. Prosedur berikut merupakan algoritma Euclid yang diperluas. procedure gcd (a, b : bilangan bulat positif, positif, a b) begin if b = 0 then begin d := a, x := 1, y := 0
return (d, x, y) end x2 := 1, x1 := 0, y2 := 0, y1 := 1 while b > 0 do begin q:=a/b, r:=a–qb, x:=x2–qx1, y:= y2qy1 a:=b, b:=r, x2:=x1, x1:=x, y2:=y1, y1:=y end d := a, x := x2, y := y2 return (d, x, y) end Relatif Prima Dua buah bilangan a dan b disebut relatif prima apabila gcd (a, b) = 1. Sebagai contoh bilangan 7 dan 11 adalah relatif prima, karena pembagi 7 dan 1 adalah 7, sedangkan pembagi 11 adalah 1 dan 11, sehingga gcd (7, 11) = 1 (Cornel et al. 1990) CRT (The Chinese Remainder Theorem) CRT adalah suatu pernyataan tentang kongruensi simultan. Misalkan n1, ..., nk adalah bilangan bulat positif yang setiap pasangnya adalah coprime (yang artinya gcd (ni, nj) = 1 untuk setiap i ≠ j). Untuk setiap bilangan bulat a1, ..., ak, selalu ada bilangan bulat x yang merupakan penyelesaian dari sistem kongruensi simultan (Wells 1992). (a) x_solves_it=true; (b) for(i= 1; i <= k; i++) (c) if(x % n[i] != a[i] % n[i]) (d) x_solves_it=false; Suatu penyelesaian x dapat ditemukan dengan cara sebagai berikut. Untuk setiap i, bilangan bulat ni dan n/ni adalah coprime, dan menggunakan ekstensi algoritma Euclid kita dapat menemukan bilangan bulat r dan s sehingga r ni + s n/ni = 1. Jika kita menentukan ei = s n/ni, maka untuk j ≠ i sebagai berikut. (a) for (i= 1; i <= k; i++) (b) {r, s}= ExtendedEuclid( n[i], n / n[i] ); (c) e[i]= s * n / n[i]; (d) for(j= 1; j <= k; j++) (e) if (j != i) (f) assert(e[i]%n[i]==1&&e[i]%n[j]==0); Penyelesaian dari sistem kongruensi simultan ini adalah: (a) for(i= 1; i <= k; i++)
(b)
x += a[i] * e[i];
RSA-CRT (Rivest-Shamir-Adleman-Chinese Remainder Theorem) RSA-CRT adalah RSA yang dimodifikasi dengan penambahan CRT sehingga menghasilkan waktu dekripsi yang lebih cepat dibandingkan RSA tanpa CRT. Pembangkitan kuncinya adalah sebagai berikut. 1. Pilih bilangan prima p dan q secara acak, sehingga gcd (p-1, q-1) = 2. 2. Hitung n = p x q. 3. Pilih 2 bilangan bulat dp dan dq secara acak, sehingga gcd (dp, p-1) = 1, gcd (dq, q-1) = 1dan dp == dq mod 2. 4. Cari suatu nilai d sehingga d == dp mod p-1 dan d == dq mod q-1. 5. Hitung e = d-1 (mod (n)). Enkripsi pada RSA-CRT adalah sebagai berikut. 1. Plaintext : M < n. 2. Ciphertext : C = Me (mod n). Dekripsi pada RSA-CRT adalah sebagai berikut. 1. Mp = Cdp mod p dan Mq = Cdq mod q. 2. v = (Mq – Mp) p_inv_q mod q. 3. M = Mp + pv. Analisis Algoritma Analisis algoritma dilakukan untuk menduga besarnya sumber daya waktu yang dibutuhkan untuk sembarang ukuran input n (Cormen et al. 1990). Kompleksitas, T(n), didefinisikan sebagai waktu yang dibutuhkan oleh suatu algoritma untuk menyelesaikan proses dengan input berukuran n. Berdasarkan waktu eksekusi program T(n), dapat ditentukan growth rate-nya, yaitu laju pertumbuhan waktu terhadap variasi ukuran input. Sebagai contoh, analisis suatu algoritma menghasilkan T(n) = an2 + bn + c, dengan a, b, dan c adalah suatu konstanta, maka dapat dikatakan growth rate algoritma tersebut adalah n2 yang merupakan bagian paling signifikan pada polinomial an 2 + bn + c. Nilai-nilai konstanta a, b, dan c tergantung pada jenis komputer dan platform bahasa pemrograman yang hanya dapat ditentukan melalui percobaan eksekusi program. Kompleksitas komputasi dari suatu algoritma memberikan gambaran umum bagaimana perubahan T(n) terhadap n. Kompleksitas waktu ini tidak dipengaruhi oleh faktor-faktor nonteknis implementasi seperti
bahasa pemrograman ataupun sarana perangkat lunak tertentu. Dalam platform uji yang seragam, suatu algoritma dengan growth rate yang rendah, misalkan log n atau n log n, lebih cepat jika dibandingkan dengan algoritma yang memiliki growth rate lebih besar, misalnya n 2, n3, n!, dan nn. Analisis Uji Running Time Running time dari suatu algoritma didefinisikan sebagai ukuran operasi primitif atau tahapan proses yang dieksekusi (Cormen et al. 1990). Jika ditinjau pada sisi waktu, maka running time dapat didefinisikan sebagai ukuran waktu total yang dibutuhkan untuk melakukan seluruh operasi primitif atau tahapan proses yang dieksekusi. Pada penelitian ini, algoritma RSA dan RSA-CRT dievaluasi (diukur) berdasarkan keadaan running time untuk waktu rata-rata.
METODE PENELITIAN Analisis Algoritma Pada tahap ini dilakukan analisis terhadap kompleksitas algoritma RSA dan RSA-CRT yang meliputi: a. kompleksitas algoritma pembangkitan kunci, b. kompleksitas algoritma enkripsi, dan c. kompleksitas algoritma dekripsi. Analisis Keamanan Pada tahap ini dilakukan analisis keamanan algoritma RSA dan RSA-CRT melalui telaah pustaka dari berbagai literatur. Literatur diambil dari buku, makalah, dan internet. Analisis Hasil Implementasi Pada tahap ini dilakukan analisis uji running time terhadap hasil implementasi enkripsi dan dekripsi algoritma RSA dan RSA-CRT. Hal-hal yang diamati adalah: a. Waktu yang diperlukan untuk melakukan enkripsi pada RSA dan enkripsi pada RSACRT serta hubungannya terhadap ukuran file yang berbeda. b. Waktu yang diperlukan untuk melakukan dekripsi pada RSA dan dekripsi pada RSACRT serta hubungannya terhadap ukuran file yang berbeda. Spesifikasi Uji Implementasi Uji implementasi dilakukan dengan menggunakan 10 ukuran file teks yang berbeda dalam selang 1764 byte sampai dengan 21168 byte sebagai obyek kajian, dilanjutkan dengan
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
memungkinkan dekripsi pada RSA-CRT lebih dari 3 kali lebih cepat dari RSA.
KESIMPULAN DAN SARAN Kesimpulan Algoritma RSA merupakan algoritma kunci publik yang keamanannya bertumpu pada kompleksitas problem faktorisasi bilangan bulat. Akibat dari kompleksitas ini, kecepatan RSA menjadi lambat. CRT ditambahkan pada algoritma dekripsi RSA untuk mempercepat proses dekripsi. Eksponensial enkripsi di sarankan bernilai kecil untuk mempercepat proses enkripsi, tetapi juga memberikan jaminan keamanan, maka dari itu dipilih e = 65537. Dari hasil analisis algoritma, dapat ditarik kesimpulan bahwa RSA dan RSA-CRT memiliki kompleksitas yang sama untuk algoritma pembangkitan kunci dan enkripsi, yaitu O((lg n)3). Tetapi pada pembangkitan kunci RSA-CRT, ada bagian yang kompleksitasnya O((lg (n/2))2). Algoritma dekripsi RSA memiliki kompleksitas O((lg n)3), sedangkan RSA-CRT memiliki kompleksitas O((lg (n/2))3). Hal ini membuktikan bahwa waktu dekripsi RSA-CRT lebih cepat dibandingkan RSA. Dari hasil analisis keamanan diperoleh kesimpulan bahwa keamanan RSA bertumpu pada problem faktorisasi bilangan bulat yang sangat bergantung pada panjang modulus yang dipilih. Panjang bit kunci yang dipakai pada penelitian ini adalah 1024 bit, yang mampu memberikan keamanan yang lebih lama. Berdasarkan analisis hasil implementasi proses enkripsi dan dekripsi RSA dan RSACRT, dapat disimpulkan RSA-CRT memiliki waktu dekripsi yang lebih cepat dibandingkan RSA. Hal ini membuktikan penambahan CRT pada RSA mampu mempercepat proses dekripsi. Saran Ruang lingkup penelitian ini dibatasi pada algoritma RSA untuk panjang modulus kunci 1024 bit. Penelitian selanjutnya dapat dikembangkan dengan menggunakan kunci yang lain yaitu kunci 2048 bit.
Eksponensial enkripsi (e) yang digunakan pada penelitian ini adalah 65537. Untuk penelitian selanjutnya dapat menggunakan e random. Penelitian ini menggunakan algoritma RSACRT untuk mempercepat proses dekripsi. Penelitian selanjutnya dapat menggunakan varian RSA yang lain seperti Rebalanced RSACRT.
DAFTAR PUSTAKA Cormen TH, Leiserson CE, dan Rivest RL 1990. Introduction to Algorithms. Massachussets-London: The MIT Press. Erivani P. 2007. Implementasi Chinese Remainder Theorem dalam Membentuk Varian RSA (Rivest-Shamir-Adleman) untuk Pengamanan Data Digital. http://www.informatika.org/~rinaldi/Matdis/20 06-2007/Makalah/Makalah0607-22.pdf. [28 November 2008]. Guritman S. 2003. Pengantar Kriptografi. Handout mata kuliah Pengantar Kriptografi / Data Security. Fakultas Matematika dan Ilmu Pengetahuan Alam IPB. Bogor. Menezes AP, van Oorschot, dan Vanstones. 1996. Handbook of Applied Chryptograpy. New York: CRC Press. Nursanto D. 2003. Tinjauan Mengenai Aplikasi Metode Montgomery MultiplicationChinese Remainder Theorem (CRT) dalam Mmpercepat Dekripsi RSA. budi.insan.co.id/courses/ec7010/dikmenjur/djok o-nursanto-revisi.doc. [2 Januari 2006]. Pressman RS. 2002. Rekayasa Perangkat Lunak. Yogyakarta: Penerbit ANDI. Stallings W. 2003. Chrytograpy and Network Security Principles and Practice. Third Edition. New Jersey: Pearson Education. Wells D. 1992. Chinese Remainder Theorem. http://www.cut-theknot.org/blue/chinese. shtml. [7 Januari 2006].
LAMPIRAN
Lampiran 1 Tampilan client
Lampiran 2 Tampilan server
Lampiran 3 Tampilan saat melakukan koneksi pada client
Lampiran 4 Tampilan saat melakukan koneksi pada server
Lampiran 5 Contoh pengiriman pesan dari client ke server menggunakan algoritma RSA
Lampiran 6 Contoh pengiriman pesan dari server ke client menggunakan algoritma RSA-CRT
Lampiran 7 Hasil pembangkitan kunci RSA client private key=640481329873587826404475646052732302276416604796357435373040346050778958841824 6607346484501331129371391572754636178689967337969124424245343280367288271166873007 5116595175591595071623911017117488103851798236719667571974060845605731795229928399 751813855943493524344703167320520056331172594869127525856312555333 RSA client public key=896044933630597190288613948454646534193393425734632879539821649250291399842387 9344768204819377483735999348993928727565468874554008056180319405815582696885037973 8096634016083072669605076046511537537476655072835222164005031619029469870354388483 396046047103083206623013156723623325641343150232093959634283493089 RSA server private key=367549238937543034456980094519044543021365933089513225420497939583810965495519 9338783479658096016240053305187014276327322299974200488594606855791955690216605270 5193216739564843275086224284740960267086475713440623328917774661036792181144247601 117244570865920163143923850452097888237059132887572737430621539533 RSA server public key=695242718626425313857104639781066822985864841310573159418800284772252121271102 5458650183460404612703101955783801039849445019003353174041756847866695531348379976 6588738785442906188455137992881482345347278881521375803032096034769987287213578502 790300205138019550355801005159072495851966787935688683810573108897 RSACRT client p=12197060040134503044036695375431469360833209006364785885781133087581096848795565 4216176335302694924925567485428636259725861885847804471844549456886072597171 RSACRT client q=28192622511022606281387733657569900036738363446259435345167003274702450571628580 5248251620813014638243772464389272312119721572938101805649963826038877957 RSACRT client dp=1179264403898687231460611815873231341959252720568988957179357793248834430515712 05178048999956054766360737570329739047580290714174592711811008007478662496713 RSACRT client dq=1275479892964005487347828406773193060544871562905827636272947567168054167033564 8756596518847530225710557171626931235873399369268679858000093729407895893 RSACRT server p=61338420703901547645720675237406331692590684478724426312958418762698094138483272 880272374819884226074097023034318666691069959891022863944890424596019127 RSACRT server q=34561055860456870659591298471601610899140170918956695344003984865006715472777261 4049454276358943599583613589526568827153975580566936233268228626165750117 RSACRT server dp=3025225097902268527019285877746440727069607541397698447768062269659414524372789 1562156399763539952078872058158571223331178636702283168764067522074814627 RSACRT server dq=1744585272404342882891495393499129486801890740102423662008239356858190276134729 02604392120031532907539635698440849442908705313888572630254353104518292649
Lampiran 8 Contoh plaintext Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vestibulum convallis. Aliquam at odio. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent pretium sem quis nulla. Mauris in tellus. Nulla in ante ut purus mattis fringilla. Sed faucibus ante nec orci. Nulla dictum dapibus lorem. Suspendisse viverra diam vitae tellus. Quisque pretium pulvinar leo. Nam molestie aliquam nunc. Quisque vulputate lacinia libero. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Morbi viverra fringilla nisl. Vivamus eu eros. Nam vel dolor. Pellentesque at massa a risus tempor malesuada. Ut arcu. In quis nisl. Duis ipsum urna, bibendum ultricies, consectetur euismod, condimentum aliquam, diam. Phasellus et ligula. Mauris ipsum. Nunc in est id lacus egestas cursus. Fusce nibh mauris, aliquam placerat, euismod non, pulvinar a, nibh. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Vestibulum consequat nisl quis justo. Suspendisse nulla massa, iaculis sit amet, porttitor a, volutpat ac, pede. Proin ac turpis. Nulla dui purus, aliquam quis, tempus et, fermentum ac, nibh. Etiam consectetur velit eget eros. In rutrum. Integer et lacus. Integer adipiscing vestibulum diam. Integer ullamcorper metus in elit. Nullam a turpis. Nulla ipsum. Nam blandit. Nam laoreet aliquet quam. Ut iaculis lacus non lectus. Duis faucibus mollis ligula. Nullam faucibus lectus at arcu. Vestibulum rutrum dictum dolor. Etiam egestas mi eget sapien. Quisque blandit leo vehicula turpis. Etiam et mauris id erat scelerisque egestas. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Cras cursus. Morbi tortor leo, ornare ut, laoreet id, lacinia sit amet, lorem. Vivamus bibendum. Phasellus et ante. Morbi a lacus id tortor condimentum blandit.
Lampiran 9 Ciphertext cipher RSA part 0=* \?gp?rE -@.??H?'?,L?Bx??? ???x?o?-?? [?|zQ?H[ >? j d }m ???? ??? ? ???=?9@??? SC?o??E??b?S????Fp???9^??wgu ?J??? IgI?o?? cipher RSA part 1=D???}? ?b?*2?K?" ????"?y?Z? ?2????Uk ??! V?.???S M 5E??? 1aV? Ud# ?*3O-??b cipher RSA part 2= ? k????>YV??y#? ??%Hl?,??????*???}? N?Xr ?Hw?? ?S9g)[????%k?? ??4??[e? \y=???A??M???? ?si? cipher RSA part 3=Pm?? ?4Grfq ~?? T {??V?? A???? ? ????????n??? ???? ?;?[?-@??HO,??? }C]N?-b CgjG~?L|tC ??>?????JH?|??? ?W????3?$? % ?E&? ? ????!;/M?E*i?????re?v??????x] ?=g1?RK2?? c? J~?L? T?{? \2o??????$N?? M?7' Th? ??5E?`N??? cipher RSA part 8=6E3?`{$[W????I?w0? ?cpD?+F? ?2T?<# ??????nB ?? ci%,? ?????W? p:??2?v?T??1/~GD???????q??? cipher RSA part 9=(e?? ??P z???? ``g[? ???K ?p ????Z????u@??>Qe?}????;?L{ cipher RSA part 10=D ??ZO??o???? ?]9r?eID???? ??_???????? 2(a"????7???t?????$B cipher RSA part 11=O?-g??? ?Y??vC? ?7ZYP:q??? cipher RSA part 12=]?L3 p? ????U?V?????0~U ? ???N~???y/u????:?%.B(??X??`g6????? `a??t??~????h{?E Y?q??zuf?? ? cipher RSA part 13= ?i y?R ?! ?Kv?? ?? ????F?/?.????>q??? 4? ?p??[}=?_#/1? ?3?~??K ????????gn ?x?U???)??? ?D??? ?d??$?S\R????-O??m?J m i?t?? 6B
Lampiran 9 Lanjutan cipher RSA part 14=E????{?^?r? mg:# T???\ ?dX???? ????R??{??;??#?.????????(?S?S??(????TS???e?T-?t? ? ?|1?]T?????c?? ?_???9?? ?R??????7?{ |??,vS??? ?o@ g -???2 fyY???c9? JK??v??Z Gx?d?z cipher RSA part 18=,Yl???@g??c b1??! ?????h? 6cA??M ?2 ?? m?&?J????/?p ?8'??? RM??6t`b ???????????7k ? ?[u? ? ???t l???? psS??g ????????8????xK| cipher RSA part 19= ?t#G??'?8(?t O?????`?{???? ?
Lampiran 10 Hasil proses dekripsi Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vestibulum convallis. Aliquam at odio. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent pretium sem quis nulla. Mauris in tellus. Nulla in ante ut purus mattis fringilla. Sed faucibus ante nec orci. Nulla dictum dapibus lorem. Suspendisse viverra diam vitae tellus. Quisque pretium pulvinar leo. Nam molestie aliquam nunc. Quisque vulputate lacinia libero. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Morbi viverra fringilla nisl. Vivamus eu eros. Nam vel dolor. Pellentesque at massa a risus tempor malesuada. Ut arcu. In quis nisl. Duis ipsum urna, bibendum ultricies, consectetur euismod, condimentum aliquam, diam. Phasellus et ligula. Mauris ipsum. Nunc in est id lacus egestas cursus. Fusce nibh mauris, aliquam placerat, euismod non, pulvinar a, nibh. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Vestibulum consequat nisl quis justo. Suspendisse nulla massa, iaculis sit amet, porttitor a, volutpat ac, pede. Proin ac turpis. Nulla dui purus, aliquam quis, tempus et, fermentum ac, nibh. Etiam consectetur velit eget eros. In rutrum. Integer et lacus. Integer adipiscing vestibulum diam. Integer ullamcorper metus in elit. Nullam a turpis. Nulla ipsum. Nam blandit. Nam laoreet aliquet quam. Ut iaculis lacus non lectus. Duis faucibus mollis ligula. Nullam faucibus lectus at arcu. Vestibulum rutrum dictum dolor. Etiam egestas mi eget sapien. Quisque blandit leo vehicula turpis. Etiam et mauris id erat scelerisque egestas. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Cras cursus. Morbi tortor leo, ornare ut, laoreet id, lacinia sit amet, lorem. Vivamus bibendum. Phasellus et ante. Morbi a lacus id tortor condimentum blandit.
Lampiran 11 Rincian waktu eksekusi enkripsi pada RSA
NO
Ukuran File (byte)
Waktu Enkripsi (ms) 1
2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9
1764 3528 5292 8820 10584 12348 14112 15876 17640
47 31 62 110 125 125 125 141 187
15 32 63 94 78 141 156 265 188
16 32 62 94 141 188 94 109 203
15 31 63 62 141 157 109 156 125
16 47 62 109 141 140 94 125 188
15 31 63 109 78 125 266 140 94
16 31 16 109 125 94 141 109 203
31 47 31 109 63 109 94 94 187
16 47 62 110 109 62 172 109 125
31 31 62 110 125 109 94 110 203
10
21168
125
234
234
234
250
157
125
187
141
125
Lampiran 12 Rincian waktu eksekusi dekripsi pada RSA Waktu Dekripsi (ms)
Ukuran File (byte)
1
2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9
1764 3528 5292 8820 10584 12348 14112 15876 17640
531 1000 2250 2406 3875 3812 4625 5204 6250
563 1235 2047 4719 3969 3984 5297 5313 6297
1171 1141 2109 4219 4422 4219 5656 6109 5640
515 2406 2234 4453 3781 4719 5500 6438 7469
563 1156 2282 3094 3594 4203 6266 6203 6907
640 1328 2484 3640 4328 3922 5047 4375 6375
532 1156 3625 3610 3656 4532 4453 6438 7250
531 1016 1953 4407 3172 5156 5218 6453 6438
547 1172 2515 3705 4297 4500 4375 4688 5594
515 2407 1984 3891 4859 5063 5188 5671 6891
10
21168
7125
7500
8172
8563
8938
9219
8391
7953
8828
7047
NO
Lampiran 13 Rincian waktu eksekusi enkripsi pada RSA-CRT
NO
Ukuran File (byte)
Waktu Enkripsi (ms) 1
2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9
1764 3528 5292 8820 10584 12348 14112 15876 17640
16 47 62 109 125 156 93 172 125
32 31 63 109 94 156 94 156 188
15 31 63 109 125 93 172 140 94
15 47 63 109 125 78 157 125 110
31 31 62 94 125 156 187 141 187
16 47 63 109 141 140 110 156 157
32 31 62 94 109 156 187 156 187
15 46 47 94 125 141 172 141 140
16 47 63 109 140 109 125 140 125
16 31 188 110 109 156 188 172 203
10
21168
109
93
125
141
203
234
235
234
140
172
Lampiran 14 Rincian waktu eksekusi dekripsi pada RSA-CRT Waktu Dekripsi (ms)
Ukuran File (byte)
1
2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9
1764 3528 5292 8820 10584 12348 14112 15876 17640
375 625 578 719 1031 1141 1672 1875 2578
234 312 1079 828 1140 1328 1562 1296 1500
359 719 469 1781 922 1187 1140 1625 2406
359 703 1078 1797 1093 1469 1156 2094 2453
234 703 469 1063 1125 2157 1406 1375 2703
360 718 1078 875 2140 1578 1391 2625 2469
360 719 1063 953 984 1265 1500 1390 2391
359 719 484 860 2141 1406 1625 1718 2110
359 719 1078 1781 2141 1125 1609 1829 2375
171 328 1079 1781 860 1093 1969 1437 2547
10
21168
1719
2265
2421
2063
1969
2953
2343
2531
2859
2641
NO
