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 ).
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 ).
- Hitung n = p*q;
Dimana nilai n ini akan digunakan untuk modulus pada private dan public key. - Hitung pq = (p-1) * (q-1);
Untuk digunakan sebagai pencarian nilai private key. - 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. - 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:
- function gcd(bilangan1, bilangan2) {
- do {
- tmp = bilangan1 mod bilangan2
- bilangan1 = bilangan2
- bilangan2 = tmp
- }
- while (bilangan2>0)
- return bilangan1
- }
Untuk PHP
yang mendukung bcmath dapat menggunakan script seperti ini:
- <?php
- function gcd($bilangan1, $bilangan2) {
- do {
- $tmp = bcmod($bilangan1, $bilangan2);
- $bilangan1 = $num2;
- $bilangan2 = $tmp;
- } while (bccomp($bilangan2,'0'));
- return $bilangan1;
- }
- /* Untuk yang mendukung GMP, dapat menggunakan fungsi gmp_gcd */
- ?>
Contoh Kasus
Pembuatan Kunci dengan bilangan yang kecil (Tidak direkomendasikan, hanya sebagai ilustrasi cara kerja alghoritma
saja).
- Pilih 2 bilangan prima yang berbeda untuk p dan
q. Misalnya:
p=61 dan q=53 - Hitung n=pq
61*53 = 3233 - Hitung pq=(p-1) * (q-1);
(61-1)*(53-1) = 3120; - 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). - 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
c = (M pangkat e) mod n
Bila M=77,
dan public Key adalah n=3233 dan e=17 maka:
- c = (77 pangkat 17) mod 3233
- c = 117582402033097174749136828787597 mod 3233
- 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:
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:
Private Key = (n=3233 dan d=2753)
c = 3123
Dengan menggunakan private key, Kita ingin melakukan decrypt dari c menjadi M kembali, caranya adalah:
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:
- M2 = AmarullzPowMod(3123,2753,3233);
- 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:
- <?php
- /* Untuk Perhitungan yang kecil, hal ini
- tidak akan mengalami permasalahan ketika
- kita menggunakan operasi standard pada
- bahasa pemrograman */
- $a = 10;
- $b = 20;
- $c = $a+$b;
- echo "Hasil : {$c}\n";
- /* Tapi bagaimana dengan ini? */
- $a = 923012332140043243204324324023213232143243454365476576587686;
- $b = 843274839564375865473856765748365654654635435646757865865865;
- $c = $a*$b;
- echo "Hasil : {$c}\n";
- ?>
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:
- <?php
- $a = "923012332140043243204324324023213232143243454365476576587686";
- $b = "843274839564375865473856765748365654654635435646757865865865";
- /* BCMATH */
- $c = bcmul($a,$b);
- echo "Hasil : {$c}";
- /* GMP */
- $c = gmp_mul($a,$b);
- echo "Hasil : ".gmp_strval($c);
- ?>
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:
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:
<?php
echo gmp_strval(gmp_nextprime("10000000"));
/* Akan menghasilkan bilangan
prima: 10000019 */
?>
posted by Bani Be at
3:52 AM
0 Comments
