Kriptografi : RSA

Algoritma RSA dibuat oleh tiga orang peneliti dari MIT (Massachussets Institute of Technology) pada tahun 1976, yaitu Ron Rivest, Adi Shamir dan Leonard Adleman. RSA adalah salah satu teknik kriptografi dimana kunci untuk melakukan enkripsi berbeda dengan kunci untuk melakukan dekripsi. Kunci untuk melakukan enkripsi disebut sebagai kunci publik, sedangkan kunci untuk melakukan dekripsi disebut sebagai kunci privat. Orang yang mempunyai kunci publik dapat melakukan enkripsi tetapi yang dalam melakukan dekripsi hanyalah orang yang memiliki kunci privat. Kunci publik dapat dimiliki oleh sembarang orang, tetapi kunci privat hanya dimiliki oleh orang tertentu saja.

Untuk pembangkitan pasangan kunci RSA, digunakan algoritma sebagai berikut: 

1. Dipilih dua buah bilangan prima sembarang yang besar, p dan q. Nilai p dan q harus dirahasiakan. 
2. Dihitung n = p x q. Besaran n tidak perlu dirahasiakan. 
3. Dihitung m = (p – 1)(q – 1). Besaran m perlu dirahasiakan. 
4. Dipilih sebuah bilangan bulat sebagai kunci publik, disebut namanya e, yang relatif prima terhadap m. e relatif prima terhadap m artinya faktor pembagi terbesar keduanya adalah 1, secara matematis disebut gcd (e,m) = 1. Untuk mencarinya dapat digunakan algoritma Euclid. Nilai e bersifat tidak rahasia. 
5. Dihitung kunci privat, disebut namanya d sedemikian agar (d x e) mod m = 1. Untuk mencari nilai d yang sesuai dapat juga digunakan algoritma Extended Euclid. Nilai D bersifat rahasia.

Maka hasil dari algoritma tersebut diperoleh : 

1. kunci publik adalah pasangan (e,n). Bersifat tidak rahasia. 
2. kunci private adalah pasangan (d,n). Bersifat rahasia 

Algoritma Enkripsi/Dekripsi 

Enkripsi 

• Ambil kunci publik penerima pesan, e, dan n 
• Nyatakan plainteks M menjadi blok-blok M1, M2, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam selang [0, n – 1]. 
• Setiap blok Mi dienkripsi menjadi blok Ci dengan rumus Ci = Mi ^ e mod n 

Dekripsi 

• Setiap blok cipherteks Ci didekripsi kembali menjadi blok Mi dengan rumus Mi = Ci ^ d mod n

Algoritma Euclid

Algoritma ini mencari FPB dengan cara melakukan pembagian berulang-ulang dimulai dari kedua bilangan yang hendak kita cari FPBnya sampai kita mendapatkan sisa 0 dari hasil pembagian.

Marilah kita lihat contoh yang lain, cari FPB dari 40 dan 64 :

• 64 ÷ 40 = 1 dengan sisa 24 
• 40 ÷ 24 = 1 dengan sisa 16 
• 24 ÷ 16 = 1 dengan sisa 8 
• 16 ÷ 8 = 2 dengan sisa 0.

Kita berhenti di sini sebab kita sudah mendapat sisa 0. Bilangan terakhir yang kita gunakan untuk membagi adalah 8, jadi FPB dari 40 dan 64 adalah 8 

Contoh lain, cari FPB 3337 dan 79 :

• 3337 ÷ 79 = 42 dengan sisa 19 
• 79 ÷ 19 = 4 dengan sisa 3 
• 19 ÷ 3 = 6 dengan sisa 1 

Kita berhenti karena sudah mendapatkan sisa 1.

Contoh RSA Sederhana 

1. p = 47 dan q = 71 (keduanya prima). 
2. n = p ⋅ q = 3337 
3. m = (p – 1)(q – 1) = 3220 
4. Pilih e yg relativ prime terhadap m, gcd(e,m) = 1.
   e = 79 => gcd(79, 3337) = 1 
5. Cari nilai d, d*e = 1 mod (m) 

          d*79 = 1 mod 3220
          d*79 mod 3220 = 1

          d = 1019

Sehingga didapatkan : 

1. Public key : (79, 3337) 
2. Private key : (1019, 3337) 

Proses Enkripsi

Setelah didapat perhitungan di atas, maka akan dilakukan enkripsi plaintext M = AKU. Pertama-tama plaintext tersebut diubah menjadi format ASCII sebagai berikut : 

Karakter          A                K           U 

ASCII             65               75          85 

M1 = 657 M2 = 585

Setelah dibagi perblock, maka akan dihitung menggunakan rumus Ci = Mi ^ e mod n. 

• C1 = 657 ^ 79 mod 3337 = 2349 
• C2 = 585 ^ 79 mod 3337 = 685 

Maka, chipertext yang didapatkan adalah C = 320328

Proses Dekripsi

Setelah chipertext dari kata AKU didapat, untuk mengubahnya kembali jadi plaintext menggunakan dekripsi dengan rumus Mi = Ci ^ d mod n. 

• M1 = 2349 ^ 1019 mod 3337 = 657 
• M2 = 685 ^ 1019 mod 3337 = 585 

Maka, setelah di dekripsi hasilnya akan sama. Yaitu 657585.

Kelebihan dan Kelemahan RSA

Kekuatan algoritma RSA terletak pada tingkat kesulitan dalam memfaktorkan bilangan menjadi faktor primanya, dalam hal ini memfaktorkan n menjadi p dan q. Karena sekali n berhasil difaktorkan, maka menghitung nilai m adalah perkara mudah. Selanjutnya, walau nilai e diumumkan, perhitungan kunci d tidaklah mudah pula karena nilai m yang tidak diketahui. Kelebihan lain algoritma RSA terletak pada ketahanannya terhadap berbagai bentuk serangan, terutama serangan brute force. Hal ini dikarenakan kompleksitas dekripsinya yang dapat ditentukan secara dinamis dengan cara menentukan nilai p dan q yang besar pada saat proses pembangitkan pasangan kunci, sehingga dihasilakan sebuah key space yang cukup besar, sehingga tahan terhadap serangan.

Namun demikian, kelebihan tersebut sekaligus menjadi kelemahan dari sistem ini. Ukuran kunci privat yang terlalu besar akan mengakibatkan proses dekripsi yang cukup lambat, terutama untuk ukuran pesan yang besar. Oleh karena itu, RSA umumnya digunakan untuk meng-enkripsi pesan berukuran kecil seperti kata kunci dari enkripsi simetris seperti DES dan AES yang kemudian kunci tersebut dikirim secara bersamaan dengan pesan utama.

Kesimpulan

RSA merupakan metode penyandian yang masih kokoh untuk mengatasi masalah keamanan dalam pengiriman data pada suatu jaringan pada media elektronik. Dari segi teknis penghitungan, system RSA mempunyai cara enkripsi yang mudah, tetapi jika sudah dienkripsi, data yang terenkripsi sulit untuk dibobol jika hanya mempunyai kunci publiknya saja. Dalam proses pembuatan kunci publik dan kunci private, terdapat beberapa faktor yang menjadi pertimbangan, yaitu ukuran dari kunci, penentuan nilai p dan q agar sulit untuk dibobol, dan kemungkinan-kemungkinan kelemahan yang dapat diketahui saat data selesai dienkripsi. Pada kehidupan sehari-hari, aplikasi sistem RSA dapat ditemukan pada system autentikasi data dan pembuatan tanda tangan digital pada komputer, pada tingkat perangkat keras, RSA banyak digunakan pada telepon yang mempunyai system pengaman dari penyadapan, kartu jaringan ethernet, dan pada kartu cerdas. RSA juga dimasukkan ke dalam protokol internet yang mempunyai sistem pengaman, seperti S-HTTP, S/MIME dan lain-lain.

Sumber :

• Ir. Rinaldi Munir, M.T., Algoritma RSA dan ElGamal, Institut Teknologi Bandung, 2004
• TRI RAHAJOENINGROEM dan MUHAMMAD ARIA, STUDI DAN IMPLEMENTASI ALGORITMA RSA UNTUK PENGAMANAN DATA TRANSKRIP AKADEMIK MAHASISWA, Universitas Komputer Indonesia.
• Muhash, Microsoft PowerPoint - Algoritma RSA, 2008
• http://studyinformatics.blogspot.com/2012/07/algoritma-rsa.html