Makalah Kriptografi (Algoritma RSA) [PDF]

Citation preview

Mata Kuliah



Dosen Pembimbing



Keamanan Informasi



Nazruddin Safaat H., ST, MT



ALGORITMA RSA



OLEH : AYU ANITA SARI (11651201525) RIZKI PRASETIA (11651103422) WEGI ZULIANDA (11651103411) AKMAH AULIA



JURUSAN TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SULTAN SYARIF KASIM RIAU



2018/2019



DAFTAR ISI DAFTAR ISI ........................................................................................................... i BAB I PEMBAHASAN ........................................................................................ 1 1.1



PENGERTIAN ....................................................................................... 1



1.2



SEJARAH............................................................................................... 1



1.3



CARA KERJA........................................................................................ 3



1.4



KELEBIHAN DAN KEKURANGAN .................................................. 5



1.5



SOURCE CODE .................................................................................... 6



1.6



APLIKASI YANG MENGGUNAKAN ALGORITMA RSA............. 10



BAB II PENUTUP .............................................................................................. 12 2.1



SIMPULAN .......................................................................................... 12



2.2



SARAN................................................................................................. 12



DAFTAR PUSTAKA ........................................................................................ 16



ii



BAB I PEMBAHASAN 1.1



PENGERTIAN Kriptografi merupakan ilmu dan seni untuk menjaga kerahasiaan suatu



informasi. Orang yang melakukan kegian di bidang kriptografi dinamakan kriptografer. Pesan kriptografi terdiri dari dua bentuk, yaitu plainteks dan cipherteks. Plainteks merupakan pesan yang dapat dibaca dengan mudah dan sudah jelas. Sedangkan cipherteks adalah pesan yang isinya acak sehingga tidak dapat dibaca, pengacakan pesan tersebut menggunakan cara tertentu. Kriptografi terdiri dari dua, yaitu simetri kriptografi dan asimetri kriptografi. Saat ini algoritma kriptografi yang paling efektif adalah algoritma RSA. Algoritma kriptografi ini sebenarnya sangat sederhana, yang diperlukan hanya dua bilangan prima. Yang menjadi kekuatan dari RSA ini adalah pencarian dua bilangan prima tersebut dari hasil kali kedua bilangan tersebut. Jika dua bilangan tersebut memiliki digit yang sedikit, maka alogritma tersebut sangatlah lemah. Sang penemu menyarankan menggunakan bilangan prima dengan 100 digit. Sehingga tidak mungkin didapat karena membutuh waktu bermiliar tahun untuk mendapatkan kedua bilangan prima tersebut.1 1.2



SEJARAH Gagasan tentang kriptografi asimetris menggunakan kunci privat dan



publik ditemukan oleh Whitfield Diffie dan Martin Hellman, pada tahun 1976. Mereka juga memperkenalkan tanda tangan digital dan mencoba menerapkan teori bilangan. Perumusan mereka dalam penggunaan kunci rahasia secara bersama yang dibuat dari beberapa bilangan berpangkat, dan modulus pada bilangan prima. Namun, mereka meninggalkan metode ini karena sulitnya untuk membuat fungsi satu arah, hal ini terjadi karena kemungkinan besar sulit untuk melakukan faktorisasi bilangan tidak dipelajari dengan baik pada saat itu. 1



Wico Chandra, “Kriptografi dan Algoritma RSA”, Makalah, Bandung, 2010, Hal 1



1



Ron Rivest, Adi Shamir, dan Leonard Adleman ("R.S.A.") di Massachusetts Institute of Technology melakukan beberapa upaya selama setahun untuk menciptakan fungsi satu arah yang sulit untuk dibalikkan. Rivest dan Shamir, sebagai ilmuwan komputer, mengajukan banyak fungsi yang potensial. Sementara Adleman, sebagai seorang matematikawan, bertanggung jawab untuk menemukan kelemahan mereka. Mereka mencoba banyak pendekatan termasuk "berbasis knapsack" dan "polinom permutasi". Untuk sementara, mereka pikir tidak mungkin untuk mencapai apa yang mereka inginkan karena persyaratan yang saling bertolak belakang. Pada bulan April 1977, mereka menghabiskan Paskah di rumah seorang siswa dan meminum banyak anggur Manischewitz sebelum kembali ke rumah mereka pada tengah malam. Rivest, tidak bisa tidur, berbaring di sofa dengan buku teks matematika dan mulai memikirkan fungsi satu arah mereka. Ia menghabiskan sisa malam itu untuk mewujudkan idenya, dan ia telah menulis dibanyak kertas hingga fajar menyingsing. Algoritma ini sekarang dikenal sebagai RSA - yang merupakan inisial dari nama keluarga mereka dalam urutan yang sama seperti kertas mereka. Clifford Cocks, seorang matematikawan Inggris yang bekerja untuk badan intelijen Inggris, Government Communications Headquarters (GCHQ), membuat sebuah algoritma untuk meyandikan dokumen internal pada tahun 1973. Namun, karena harga computer yang cukup mahal pada saat itu, RSA dianggap algoritma yang tepat untuk menyandikan dokumen tersebut, karena algoritma RSA yang belum dikenal public dan jarang digunakan. Hingga pada tahun 1997, dokumen yang telah disandikannya baru dapat buka sandinya. Ini berarti selama 24 tahun dokumen tersebut aman dengan menggunakan ekripsi RSA. Pada 1997 Algoritma turunan dari RSA pun mulai dikenalkan dengan nama Kid-RSA (KRSA). KRSA adalah algoritma yang menggunakan kunci public yang sederhana dan dirancang untuk tujuan pendidikan. Beberapa orang merasa



2



mempelajari Kid-RSA berarti juga mempelajari RSA dan kunci publiknya, yang dianalogikan sebagai Algoritma DES yang disederhanakan.2 1.3



CARA KERJA



Gambar 1 Cara Kerja algoritma RSA



Pada dasarnya, cara kerja algoritma ini sangat sederhana, yaitu pengirim pesan menyandikan pesannya dengan menggunakan kunci yang dimilikinya. Kunci yang dimiliki penyandi tidak dapat digunakan untuk membuka pesan kembali karena fungsi dari kuncinya hanya untuk menyandikan pesan. Yang dapat membuka sandi dari pesan tersebut hanyalah penerima yang dialamatkan dengan menggunakan kunci yang hanya dimiliki olehnya. Langkah untuk melakukan untuk menentuka pasangan kunci, enkripsi, dan dekripsi akan dijelaskan dibawah ini:. a. Pembuatan pasangan kunci Langkah-langkah melakukan pembangkit pasangan kunci adalah sebagai berikut: 



Pilih dua bilangan prima sembarang, sebut p dan q. jaga kerahasian p dan q ini.







Hitung n = p x q. nilai dari n tidak perlu dirahasiakan.



2



Wikipedia, RSA (Cryptosystem), https://en.wikipedia.org/wiki/RSA_(cryptosystem), diakses pada 13 Oktober 2018 pada pukul 13.45 WIB



3







Hitung m = (p - 1)(q - 1). Sekali m telah dihitung, a dan b dapat dihapus untuk mencegah diketahui oleh orang lain.







Pilih sebuah bilangan bulat untuk kunci public, sebut namanya e, yang relatif prima terhadap m.







Hitung kunci dekripsi, d, dengan kekongruenan d  e-1 mod m atau



d



1  ( k  m) e



b. Enkripsi Langkah-langkah melakukan enkripsi adalah sebagai berikut: 



Nyatakan pesan menjadi: blok-blok plainteks: p1, p2, p3,… (harus dipenuhi persyaratan bahwa nilai p, harus terletak dalam himpunan nilai 0,1,2,…,(n – 1) untuk menjamin hasil perhitungan tidak berada di luar himpunan).







Hitung blok cipherteks c, untuk blok plain teks p, dengan persamaan ci = pie mod n dalam hal ini, e adalah kunci public



c. Dekripsi Proses dekripsi dilakukan dengan menggunakan persamaan pi = cid mod n dalam hal ini, d adalah kunci privat (privat key).



Dari uraian diatas, maka didapat beberapa komponen dalam menggunakan algoritma ini, yaitu: a) p dan q adalah bilangan prima (rahasia) b) n = p x q



(tidak rahasia)



c) m= (p-1) (q-1)



(rahasia)



d) e (kunci enkripsi / publik)



(tidak rahasia)



Perhatikan Langkah ker-5 pada proses pembangkitan pasangan kunci. Kekonguenan ed = 1 (mod m) sama dengan ed mod m = 1.



4



Dengan menggunakan pernyataan a = b (mod m) ekivalen dengan a = b +km maka d dapat dicari dengan rumus 𝑑=



1 + 𝑘𝑚 𝑒



Dalam implementasinya, nilai a dan b disarankan memiliki nilai yang sangat besar (100 angka). Agar tidak mudah mendapatkan factor bilangan prima dari n. Seperti yang telah dijelaskan di atas, kekuatan algoritma RSA itu bergantung pada tingkat kesulitan memfaktor n menjadi 2 bilangan prima. Dengan menggunakan komputer, pencarian faktor bilangan prima menjadi mudah, oleh karena itu sang penemu menyarankan untuk memilih dua buah bilangan prima yang jumlah digitnya minimal 100 sehingga hasil perkalian kedua bilangan prima tersebut memiliki digit 200. Untuk mencari factor bilangan prima dari 200 digit tersebut dibutuhkan waktu 4 miliar tahun dengan kecepatan computer 1 milidetik. 1.4



KELEBIHAN DAN KEKURANGAN Beberapa kelebihan dari algoritma RSA adalah : a. Ketahanannya terhadap berbagai bentuk serangan, terutama serangan brute force. b. Masalah Keamanan Pada distribusi kunci dapat lebih baik. c. Masalah menejemen kunci yang lebih baik karena jumlah kunci yang lebih sedikit. d. Keamanan algoritma RSA terletak pada sulitnya memfaktorkan bilangan yang besar menjadi faktor-faktor prima. Beberapa kekurangan dari algoritma RSA adalah : a. RSA memiliki kecepatan yang lebih lambat dibandingkan dengan DES dan algoritma simetrik lainnya. b. Ukuran kunci privat yang terlalu besar akan mengakibatkan proses dekripsi yang cukup lambat, terutama untuk ukuran pesan yang besar. 5



c. RSA tidak di gunakan untuk mengenkripsi pesan, tetapi mengenkripsi kunci simetri dengan kunci public penerima pesan. 1.5



SOURCE CODE Berikut ini merupakan implementasi dari algoritma RSA dalam C++ :



#include #include #include #include using namespace std; // inisialisasi variable long int p, q, n, t, flag, e[100], d[100], temp[100], j, m[100], en[100], i; char msg[100]; //inisialisai method int prime(long int); void ce(); long int cd(long int); void encrypt(); void decrypt(); //method untuk menentukan angka yang diinput merupakan bilangan prima atau tidak int prime(long int pr) { int i; j = sqrt(pr); for (i = 2; i p; //menerima inputan dan menyimpannya pada variable p flag = prime(p); //pengambilan nilai dari method prime if (flag == 0) { cout q; flag = prime(q); if (flag == 0 || p == q) { cout msg; //input pesan yang ingin di enkripsi for (i = 0; msg[i] != NULL; i++) m[i] = msg[i]; n = p * q; t = (p - 1) * (q - 1); ce(); cout