RSA Security (Rivest, Shamir, Adleman)

Apakah RSA Itu?? RSA security merupakan algoritma kriptografi asimetri yang digunakan untuk mengenkripsi dan mendekripsi data dengan kunci yang berbeda . Kunci yang digunakan untuk mengenkripsi disebut dengan kunci public sedangkan yang digunakan untuk mendekripsi disebut dengan kunci privat. RSA juga alghoritma pertama yang mengimplementasikan Digital Signature dan berhasil dengan baik dalam implementasi public serta private key. RSA membutuhkan tiga langkah dalam prosesnya, yaitu pembangkitan kunci, enkripsi, dan dekripsi. Proses enkripsi dan dekripsi merupakan proses yang hampir sama. Jika bilangan acak yang dibangkitkan kuat, maka akan lebih sulit untuk melakukan cracking terhadap pesan. Parameter kuat tidaknya suatu kunci terdapat pada besarnya bilangan acak yang digunakan.

Algortima RSA dijabarkan pada tahun 1976 oleh tiga orang : Ron Rivest, Adi Shamir dan Len Adleman dari Massachusetts Institute of Technology. Huruf '''RSA''' itu sendiri berasal dari inisial nama mereka (‘R’ivest - ‘S’hamir – ‘A’dleman). Clifford Cocks, seorang matematikawan Inggris yang bekerja untuk GCHQ, menjabarkan tentang sistem equivalen pada dokumen internal di tahun 1973. Penemuan Clifford Cocks tidak terungkap hingga tahun 1997 karena alasan ''top-secret classification''. Algoritma RSA dipatenkan oleh Massachusetts Institute of Technology pada tahun 1983 di Amerika Serikat sebagai US patent 4405829. Paten tersebut berlaku hingga 21 September 2000. Setelah bulan September tahun 2000, paten tersebut berakhir, sehingga saat ini semua orang dapat menggunakannya dengan bebas.

Konsep fundamental dari Kriptografi Kunci Publik ditemukan oleh Whitfield Diffie dan Martin Hellman, dan secara terpisah oleh Ralph Merkle. Sedangkan konsep dasar Kriptografi Kunci Publik terletak pada pemahaman bahwa kunci selalu berpasangan: kunci enkripsi dan kunci dekripsi tetapi juga perlu diingat bahwa sebuah kunci tidak dapat dibangkitkan dari kunci lainnya. Seseorang harus memberikan kunci publiknya agar pihak lain dapat mengenkripsi sebuah pesan dan dekripsi hanya terjadi jika seseorang mempunyai kunci privat.

Alghoritma ini biasanya digunakan untuk melakukan enkripsi data pada protokol-protokol aman seperti TLS dan SSL. Salah satu service/layanan paling populer yang menggunakan TLS atau SSL diantaranya HTTPS atau protokol HTTP yang aman. Telah terdapat banyak software yang dapat digunakan untuk memanfaatkan fasilitas TLS dan SSL ini, diantaranya yang paling populer adalah OpenSSL dan GnuTLS. Aplikasi server juga sudah banyak yang mendukung layanannya agar dapat berjalan dalam protokol ini seperti Apache HTTPD, Sendmail, dan sebagainya.

Alur Operasi RSA

Alghoritma RSA terbagi kedalam tiga bagian utama yaitu :

1. Proses Pembuatan Kunci (Private dan Public Keys)

Alghoritma RSA melibatkan dua kunci yaitu Private Key dan Public Key. Dimana Public Key dapat secara aman diketahui oleh semua pihak untuk digunakan sebagai kunci untuk melakukan enkripsi, sedangkan Private Key harus selalu di simpan secara rahasia untuk melakukan Dekripsi (Decrypt) data yang telah di enkripsi dengan menggunakan Public Key.

Data yang telah di enkripsi oleh Public Key hanya dapat di dekripsi oleh Private Key, hal ini lah yang membuat data yang dienkripsi dengan alghoritma RSA aman walaupun Alghoritma RSA-nya diketahui selama Private Key nya tidak diketahui oleh pihak lain.

Pembuatan Private dan Public key terdiri dari 5 tahap, diantaranya:

a.       Cari 2 Bilangan Prima secara acak dan simpan dalam variabel p dan q, dengan catatan jumlah bit untuk bilangan ini sama. Nilai p harus lebih besar dari q dan direkomendasikan minimal untuk menggunakan bilangan di atas 128bit/2 = 64bit bila akan membuat kunci dengan bit-length sebesar 128bit ( min 64bit hex = 0x8000000000000000; min 64bit desimal=9223372036854775808 ).

b.      Hitung n = p*q;

Dimana nilai n ini akan digunakan untuk modulus pada private dan public key.

c.       Hitung pq = (p-1) * (q-1);

Untuk digunakan sebagai pencarian nilai private key.

d.      Pilih nilai e untuk public key dengan syarat (1< e < pq) dan (gcd(e,pq)=1);
Nilai e ini biasanya merupakan nilai yang relatif kecil, yang paling seringv digunakan adalah 0x10001 = 65537. Bila kriteria e tidak cocok dengan syarat di atas, maka harus dicari nilai e lain yang sesuai, atau bila e sudah ditentukan dengan 0x10001, maka yang harus dicari kembali adalah nilai p, q, n dan pq seperti pada tahap awal.

e.       Pilih nilai d, dengan syarat nilai d memenuhi: (d*e) mod pq = 1

2. Proses Enkripsi

Berikut adalah ilustrasi enkripsi dengan menggunakan RSA:

Ahmad mengirimkan public key (n,e) nya untuk Idik, dan menyimpan secara rahasia private key-nya. Idik ingin mengirimkan pesan "M" pada Ahmad. Idik kemudian merubah M menjadi kode ascii (berupa integer) dan menghitung ciphertext "c" (nilai yang telah terenkripsi) dengan menggunakan public key yang dikirimkan oleh Ahmad kepadanya, kemudian Idik mengirimkan nilai c kepada Ahmad untuk di-decrypt dengan menggunakan private-key miliknya.

Ada beberapa syarat dalam enkripsi di RSA, dimana nilai M harus lebih besar dari 0, dan harus lebih kecil dari nilai n (dari public key). Kode Ascii untuk M adalah 77. Bila Public Key adalah (n=3233 dan e=17) maka nilai M ini memenuhi syarat 0 < 77 < 3233; dan dapat langsung dilakukan kalkulasi.

Proses enkripsi sangat mudah, hanya dengan melakukan kalkulasi

Lihat Source Code

1.                   c = (M pangkat e) mod n 

Bila M=77, dan public Key adalah n=3233 dan e=17 maka:

Lihat Source Code

1.                   c = (77 pangkat 17) mod 3233 

2.                   c = 117582402033097174749136828787597 mod 3233 

3.                   c = 3123 

3. Proses Dekripsi

Operasi Dekripsi/decrypt tidak berbeda jauh dengan operasi encrypt, yang berbeda adalah nilai yang dimasukkan kedalam fungsi powmod itu. Dalam operasi decrypt, nilai M diganti dengan nilai c dari ciphertext (hasil enkripsi) dan nilai e dari public key diganti dengan nilai d dari private key, sedangkan nilai n dari public key selalu sama dengan nilai n dari private key.

Dari penjelasan sebelumnya Kita sudah mendapatkan data-data sebagai berikut:

Lihat Source Code

1.                   Private Key = (n=3233 dan d=2753) 

2.                   c = 3123 

Dengan menggunakan private key, Kita ingin melakukan decrypt dari c menjadi M kembali, caranya adalah:

Lihat Source Code

1.                   M2 = (c pangkat d) mod n 

2.                   M2 = (3123 pangkat 2753) mod 3233 

3.                   M2 = 7+E8301 mod 3233 

4.                   M2 = 77 

Kita coba menghitungnya dengan fungsi bcpowmod, gmp_powm atau AmarullzPowMod di atas:

Lihat Source Code

1.                   M2 = AmarullzPowMod(3123,2753,3233); 

2.                   M2 akan bernilai 77 

Dengan perhitungan tersebut, kita sudah dapat mengimplementasikan Private dan Public Key sebagai sarana untuk melakukan enkripsi dengan menggunakan alghoritma RSA, dimana Idik melakukan enkripsi data M=77 dengan public key dan mendapatkan nilai c=3123, kemudian mengirimkannya kepada Ahmad untuk di dekripsi dengan menggunakan private key dan mendapatkan data yang sama dengan yang dimaksudkan oleh Idik, yaitu M2=77.

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.

Kelompok 3 Sistem Terdistribusi (A1)

• Ahmad Quzwaini 1001.53.0032
• Atiek Puji Rahayu (10.01.53.0049)
• Siti Rachmawati (10.01.53.0058)
• Marischa W.F (10.01.53.0052)