Apa itu RSA ?

Mengenal RSA

Lama tak jumpa dalam tulisan blog, kali ini saya akan membahas tentang alghoritma keamanan dalam hal enkripsi data dengan menggunakan RSA.

 

Nama RSA merupakan kependekan dari pembuat alghoritma itu sendiri yaitu Rivest, Shamir dan Adleman. RSA merupakan alghoritma untuk melakukan enkripsi data dengan memanfaatkan fasilitas public dan private key. RSA merupakan alghoritma pertama yang mengimplementasikan Digital Signature juga alghoritma pertama yang berhasil dengan baik dalam implementasi public dan private key. Sampai hari ini RSA masih digunakan sebagai alghoritma utama dalam melakukan enkripsi data terutama dalam suatu koneksi jaringan internet, dimana data yang ditransfer sangat rawan akan pencurian (man in middle attack).

 

Alghoritma ini biasanya digunakan untuk melakukan enkripsi data pada protokol-protokol aman seperti TLSdan SSL. Salah satu service/layanan paling populer yang menggunakan TLS atau SSL diantaranya HTTPSatau 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.

 

Tapi maaf, dalam blog ini saya tidak akan membahas tentang TLS atau SSL, tapi akan membahas tentangAlghoritma atau Logika cara kerja enkripsi RSA yang dapat selanjutnya Kita implementasikan kedalam satu bahasa pemrograman untuk digunakan pada Aplikasi yang sedang Kita bangun.

 

Alur Operasi RSA

Alghoritma RSA terbagi kedalam tiga bagian utama yaitu Proses Pembuatan Kunci (Private dan Public Keys), Proses Enkripsi (Encrypt) dan Proses Dekripsi (Decrypt).

 

Perhitungan Matematika dalam Alghoritma RSA sangat terasa kental, dimana pada alghoritma ini akan melakukan proses matematika dengan bilangan yang sangat besar agar hasil enkripsi maupun hasil pembuatan kunci sukar untuk di lacak (hack). Dengan demikian implementasi RSA juga harus didukung oleh alghoritma matematika yang dapat melakukan perhitungan dengan nilai bilangan yang sangat besar.

 

Proses Pembuatan Kunci

Alghoritma RSA melibatkan dua kunci yaitu Private Key danPublic 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:

1. 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 atas128bit/2 = 64bit bila akan membuat kunci dengan bit-length sebesar 128bit ( min 64bit hex = 0x8000000000000000; min 64bit desimal=9223372036854775808 ).
2. Hitung n = p*q;
   Dimana nilai n ini akan digunakan untuk modulus pada private dan public key.
3. Hitung pq = (p-1) * (q-1);
   Untuk digunakan sebagai pencarian nilai private key.
4. 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 sering dugunakan adalah 0x10001 = 65537.
   Bila kriteria e tidak cocok dengan syarat di atas, maka harus dicari nilai e lain yang sesuai, atau bilae sudah ditentukan dengan 0x10001, maka yang harus dicari kembali adalah nilai p, q, n dan pqseperti pada tahap awal.
5. Pilih nilai d, dengan syarat nilai d memenuhi: (d*e) mod pq = 1

Dalam point ke 4, terdapat fungsi GCD, dimana nilai fungsi ini digunakan untuk mencari nilai bagi terbesar(Greatest common divisor) yang biasanya telah terdapat pada fungsi matematika seperti gmp_gcd. Atau bila Kita tidak memiliki fungsi ini, kita dapat membuatnya sendiri dengan alghoritma seperti berikut:

 

Lihat Source Code

1. function gcd(bilangan1, bilangan2) { 
2.     do { 
3.         tmp = bilangan1 mod bilangan2 
4.         bilangan1 = bilangan2 
5.         bilangan2 = tmp 
6.     } 
7.     while (bilangan2>0) 
8.     return bilangan1 
9. } 

 

Untuk PHP yang mendukung bcmath dapat menggunakan script seperti ini:

 

Lihat Source Code

1. <?php 
2.     function gcd($bilangan1, $bilangan2) { 
3.         do { 
4.             $tmp = bcmod($bilangan1, $bilangan2); 
5.             $bilangan1 = $num2; 
6.             $bilangan2 = $tmp; 
7.         } while (bccomp($bilangan2,'0')); 
8.         return $bilangan1; 
9.     } 
10.      
11.     /* Untuk yang mendukung GMP, dapat menggunakan fungsi gmp_gcd */ 
12. ?> 

 

Contoh Kasus Pembuatan Kunci dengan bilangan yang kecil (Tidak direkomendasikan, hanya sebagai ilustrasi cara kerja alghoritma saja).

1. Pilih 2 bilangan prima yang berbeda untuk p dan q. Misalnya:
   p=61 dan q=53
2. Hitung n=pq
   61*53 = 3233
3. Hitung pq=(p-1) * (q-1);
   (61-1)*(53-1) = 3120;
4. Pilih bilangan e dengan syarat (1 < e < 3120) dan gcd(e,3120)=1, kita ambil e=17, dimana
   17 memenuhi syarat: (1 < 17 < 3120) dan (gcd(17,3120)=1).
5. Pilih nilai d, dimana (d*e) mod pq = 1. Kita ambil d=2753 dimana:
   (2753*17) mod 3120 = 1
   46801 mod 3120 = 1

Dengan perhitungan tersebut Kita telah mendapatkan Private dan Public Key, dimana Private Key adalah (n=3233 dan d=2753) dan Public Key adalah (n=3233 dan e=17).

 

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 syarat0 < 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 

 

Untuk lebih efisien, Kita dapat menggunakan fungsi powmod (dalam bcmath dapat menggunakanbcpowmod, dalam GMP dapat menggunakan gmp_powm). Atau membuat fungsi powmod yang efisien seperti pada logika kode berikut:

 

Lihat Source Code

1. function AmarullzPowMod(a,b,c){ 
2.     r=a; 
3.     for (i=1;i<b;i++){ 
4.         r=(a*r) % c; 
5.     } 
6.     return r; 
7. } 
8.  
9. cipher = AmarullzPowMod(77,17,3233); 

 

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, sedangkannilai 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.

 

Big Integer

Setelah mengetahui Alghoritma RSA, kiranya sangat penting untuk mengerti tentang cara penghitungan matematika dengan bilangan yang sangat besar. Kita ambil contoh kode berikut ini dalam PHP:

 

Lihat Source Code

1. <?php 
2.  
3.  /* Untuk Perhitungan yang kecil, hal ini 
4.     tidak akan mengalami permasalahan ketika 
5.     kita menggunakan operasi standard pada 
6.     bahasa pemrograman */ 
7.  $a = 10; 
8.  $b = 20; 
9.  $c = $a+$b; 
10.  echo "Hasil : {$c}\n"; 
11.   
12.  /* Tapi bagaimana dengan ini? */ 
13.  $a = 923012332140043243204324324023213232143243454365476576587686; 
14.  $b = 843274839564375865473856765748365654654635435646757865865865; 
15.  $c = $a*$b; 
16.  echo "Hasil : {$c}\n"; 
17.  
18. ?> 

Nilai Integer pada sebuah bahasa pemrograman biasanya tergantung dari jenis komputer. Untuk komputer dengan sistem berbasis 32bit (8 bit = 1 byte/karakter; 32 bit = 4bytes; max=FF,FF,FF,FF), Nilai Signed Integer (Integer yang mendukung minus) terbesarnya biasanya berkisar pada 0xFFFFFFFF/2 = 4294967295/2 = 2147483647, dimana nilai diatas 2147483647 (0x7FFFFFFF) akan dihitung sebagai minus.

 

Hal ini tidak memadai untuk implementasi alghoritma RSA, dimana rekomendasi minimum private/public key harus berada pada kisaran bilangan dengan jumlah bit sekitar 128bit dan lebih baik lagi sampai 4096 bit, dimana angka rekomendasi minimum saja sudah tidak memadai pada komputer dengan yang berbasis64bit.

 

Permasalahan ini dapat diatasi dengan beberapa library matematika yang biasanya terdapat pada bahasa pemrograman. Misalnya pada PHP kita dapat menjumpai BCMATH dan GMP, pada javascript Kita dapat menggunakan BigInt.js. Beberapa library tersebut mengimplementasikan perhitungan matematika dengan cara mereka masing-masing, seperti BCMATH dan GMP yang menggunakan arbitrary precision (perhitungan dengan binary), BigInt yang memanfaatkan Array untuk menghitung bilangan dalam bagian-bagian.

 

Sehingga permasalahan code di atas dapat diatasi dengan script seperti berikut ini:

 

Lihat Source Code

1. <?php 
2.  
3.  $a = "923012332140043243204324324023213232143243454365476576587686"; 
4.  $b = "843274839564375865473856765748365654654635435646757865865865"; 
5.   
6.  /* BCMATH */ 
7.  $c = bcmul($a,$b); 
8.  echo "Hasil : {$c}"; 
9.   
10.  /* GMP */ 
11.  $c = gmp_mul($a,$b); 
12.  echo "Hasil : ".gmp_strval($c); 
13.   
14. ?> 

 

Pencarian Nilai Prima

Yang sangat menguras kinerja mesin dalam pembuatan private dan public key adalah pencarian nilai prima secara looping, dimana secara ortodok/tradisional nilai prima ini dihitung dengan melakukan pembagian apakah nilai tersebut dapat dibagi oleh bilangan selain dirinya seperti pada contoh algoritma berikut ini:

 

Lihat Source Code

1. function cekNilaiPrima(nilai){ 
2.     for (i=1;i<nilai;i++){ 
3.         if (nilai%i==0) 
4.             return false; 
5.     } 
6.     return true; 
7. } 
8.  
9. if (cekNilaiPrima(1000000)){ 
10.     ...Ini Nilai Prima... 
11. } 

 

Contoh di atas adalah cara tradisional untuk melakukan cek apakah nilai yang dimaksud adalah nilai prima atau bukan. Pada bilangan kecil, hal ini mungkin tidak terlalu berpengaruh, tapi untuk nilai yang berdigit 128bit, bayangkan saja komputer harus melakukan looping sebanyak berjuta-juta kali hanya untuk mencek apakah bilangan tersebut dapat dibagi oleh bilangan selain dirinya.

 

Pada beberapa bahasa pemrograman seperti PHP, GMP telah menyediakan fungsi gmp_nextprime, dimana fungsi ini dapat mencari bilangan prima setelah bilangan yang dimintanya seperti pada contoh berikut:

 

Lihat Source Code

1. <?php 
2.     echo gmp_strval(gmp_nextprime("10000000")); 
3.     /* Akan menghasilkan bilangan prima: 10000019 */ 
4. ?> 

Terdapat juga beberapa alghoritma lainnya untuk melakukan cek nilai prima yang lebih efisien, diantaranyaMiller-Rabin Primality Test [http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test]

 

Penutup

Rupanya itu saja pengenalan tentang RSA dan Alghoritma-nya, mudah-mudahan dapat menjadi referensi yang berguna bagi Anda, terutama para mahasiswa Unikom yang akan melakukan Tugas Akhir dan berminat dengan hal-hal seputar keamanan data.

 

Algoritma ini digunakan pada fasilitas-fasilitas web di Unikom yang meminta user untuk mengirimkan data-data sensitif seperti password untuk mendukung keamanan yang maksimal walaupun telah mendukung protokol HTTPS.

 

Dengan mengetahui Algoritma ini, Kita bisa saja membuat sebuah layanan web yang aman tanpa menggunakan protokol HTTPS, tapi hanya dengan PHP sebagai server side untuk melakukan pembuatan pasangan kunci juga melakukan dekripsi, dan Javascript sebagai client side yang melakukan enkripsi dengan public key yang diberikan oleh server.

 

Terima Kasih

Dan Sampai Jumpa pada Blog-blog lainnya yang lebih menarik.

 

Referensi

• RSA Wikipedia : http://en.wikipedia.org/wiki/RSA
• RSA Request for Comments (RFC2313) : http://www.ietf.org/rfc/rfc2313.txt
• Miller Rabin Test Wikipedia : http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
• Inverse Mod : http://delphiforfun.org/programs/delphi_techniques/Hans_BigInt_Email.htm
• BigInteger in Javascript: http://www.leemon.com/crypto/BigInt.html
• PHP BCMath : http://www.php.net/manual/en/book.bc.php
• PHP GMP : http://www.php.net/manual/en/book.gmp.php
• GNU MP - GMBLIB : http://gmplib.org/
• OpenSSL : http://www.openssl.org/

Bila akan menyalin artikel ini, mohon untuk menambahkan link sumber:
"http://amarullz.blog.unikom.ac.id/mengenal-rsa.xm".
Semua Tulisan di Atas © 2010 oleh Ahmad Amarullah ( amarullz at yahoo dot com )