RSA

RSA 

Tugas Sistem Terdistribusi

   Anggota Kelompok : 

    Ismarbani                    ( 10.01.53.0085 )

    Naufal Ari Safrudi      ( 10.01.53.0044)

  Gigih Dwi Wicaksana ( 10.01.53.0036)

  Rifgi Nanda R.M.        ( 10.01.53.0062)

RSA adalah salah satu teknik kriptografi dimana kunci untuk melakukan enkripsi berbeda dengan kunci untuk melakukan dekripsi. Data transkrip akademik mahasiswa merupakan salah satu data yang harus dijaga keamanannya sehingga perlu diterapkan suatu teknik pengamanan dalam penyimpanannya. Pada makalah ini akan dibahas proses enkripsi (penyandian data) nilai transkrip akademik mahasiswa menggunakan algoritma RSA, lalu akan dibahas proses melakukan dekripsi (pengembalian data asli), serta akan dibahas pula proses pembangkitan kunci pada algoritma RSA ini. Kinerja yang diukur dari algoritma RSA ini waktu komputasi serta kompleksitas memori yang dibutuhkan dalam melakukan enkripsi dan dekripsi data. Sebuah perangkat lunak berbasis LabVIEW dibangun untuk implementasi algoritma RSA ini. Hasil pengujian menunjukkan bahwa algoritma RSA berhasil diimplementasikan untuk pengamanan data transkrip akademik mahasiswa. Berdasarkan pengujian diperoleh waktu komputasi algoritma RSA adalah sebesar 15625 mikrodetik. Sedangkan kompleksitas memori yang dibutuhkan algoritma RSA sebesar 3908 bytes.

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:

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 atas 128bit/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 bila e sudah ditentukan dengan 0x10001, maka yang harus dicari kembali adalah nilai p, q, n dan pq seperti 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 syarat 0 < 77 < 3233; dan dapat langsung dilakukan kalkulasi.

Proses enkripsi sangat mudah, hanya dengan melakukan kalkulasi

Lihat Source Code

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 menggunakan bcpowmod, dalam GMP dapat menggunakan gmp_powm). Atau membuat fungsi powmod yang efisien seperti pada logika kode berikut:

Lihat Source Code

function AmarullzPowMod(a,b,c){ 

    r=a; 

    for (i=1;i<b;i++){ 

        r=(a*r) % c; 

    } 

    return r; 

} 

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

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

c = 3123 

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

Lihat Source Code

M2 = (c pangkat d) mod n 

M2 = (3123 pangkat 2753) mod 3233 

M2 = 7+E8301 mod 3233 

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 berbasis 64bit.

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

function cekNilaiPrima(nilai){ 

    for (i=1;i<nilai;i++){ 

        if (nilai%i==0) 

            return false; 

    } 

    return true; 

} 

if (cekNilaiPrima(1000000)){ 

    ...Ini Nilai Prima... 

} 

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

<?php 

    echo gmp_strval(gmp_nextprime("10000000")); 

    /* Akan menghasilkan bilangan prima: 10000019 */ 

?> 

blogerahman.staff.unisbank.ac.id

www. unisbank.ac.id