MEKA ISME DASAR KERJA RSA
Tingkat keamanan algoritma
penyandian RSA sangat bergantung pada ukuran kunci sandi tersebut (dalam bit),
karena makin besar ukuran kunci, maka makin besar juga kemungkinan kombinasi
kunci yang bias dijebol dengan metode mengencek kombinasi satu persatu kunci
atau lebih dikenal dengan istilah brute force attack. Jika dibuat suatu sandi
RSA dengan panjang 256 bit, maka metode brute force attack akan menjadi tidak
ekonomis dan sia-sia dimana para hacker pun tidak mau/sanggup untuk menjebol
sandi tersebut.
Proses Pembuatan Kunci
Dalam membuat suatu sandi, RSA
mempunyai cara kerja dalam membuat kunci publik dan kunci privat adalah sebagai
berikut :
Pilih dua bilangan prima p dan q
secara acak , p ≠ q. Bilangan ini harus cukup besar (minimal 100 digit).
Hitung N = pq. Bilangan N disebut
parameter sekuriti.
Hitung φ = (p-1)(q-1).
Pilih bilangan bulat (integer)
antara satu dan φ (1 < e < φ) yang tidak mempunyai faktor pembagi dari φ. Hitung d hingga d e ≡ 1 (mod φ).
Keterangan :
Langkah 3 dan 4 dapat dihasilkan
dengan cara algoritma Euclidean
Langkah 4 dapat dihasilkan dengan
menemukan integer x sehingga d = (x(p-1)(q-1) + 1)/e menghasilkan bilangan
bulat, kemudian menggunakan nilai dari d (mod (p-1)(q-1))
Setelah melalui cara ini, maka
kita akan mendapatkan kunci publik dan kunci privat. Kunci publik terdiri dari
dua elemen, yaitu :
N, merupakan modulus yang
digunakan
e, eksponen publik atau eksponen
enkripsi dan kunci privat, yang terdiri dari :
N, merupakan modulus yang
digunakan, sama seperti pada kunci publik
d, eksponen pribadi atau eksponen
deskripsi, yang harus dijaga kerahasiaanya
Nilai p dan q sebaiknya dibuang
atau dijaga kerahasiaannya, karena terdapat N dimana p dan q adalah faktor
pembagi dari N. Walaupun bentuk ini memperbolehkan dekripsi secara cepat dan
signing menggunakan Chinese Remainder Theorem (CRT), hal ini mejadi lebih tidak
aman karena bentuk ini memperbolehkan side channel attacks. Side channel attacks
adalah sebuah serangan yang berdasarkan informasi yang dikumpulkan dari
implementasi fisik (atau kelemahan secara fisik) dari sebuah system kriptografi,
dibanding dengan kelemahan teoritis dari algoritmanya sendiri. Sebagai
contohnya, faktor-faktor kurun waktu dari informasi, konsumsi tenaga, bahkan suara
yang ditimbulkan dapat membantu mempermudah informasi yang bisa diambil untuk menjebol
sistem tersebut.
Proses Enkripsi Pesan
Misalkan pada suatu kasus si A
ingin mengirim pesan m kepada si B. A mengubah m menjadi angka n < N, menggunakan
protokol yang sebelumnya telah disepakati dan dikenal sebagai padding scheme. Padding
scheme harus dibangun secara hati-hati sehingga tidak ada nilai dari m yang
menyebabkan masalah keamanan. Contohnya, jika kita ambil contoh sederhana dari
penampilan ASCII dari m dan menggabungkan bit-bit secara bersama-sama akan menghasilkan
n, kemudian pessan yang berisi ASCII tunggal karakter NUL (nilai numeris 0)
akan menghasilkan n = 0, yang akan menghasilkan ciphertext 0 apapun itu nilai
dari e dan N yang digunakan.
Maka A mempunyai nilai n dan
mengetahui N dan e, yang telah diumumkan oleh B. A kemudian menghitung
ciphertext c yang terkait pada n :
c = ne mod N (1)
Perhitungan tersebut dapat
diselesaikan dengan menggunakan metode exponentation by squaring, yaitu sebuah
algoritma yang dipakai untuk komputasi terhadap sejumlah nilai integer yang
besar dengan cepat. Kemudian A mengirimkan nilai c kepada B.
Proses Dekripsi Pesan
B sudah menerima c dari A, dan
mengetahui kunci privat yang digunakan B. B kemudian mengembalikan nilai n dari
c dengan langkah-langkah sebagai berikut :
n = cd mod N (2)
Perhitungan diatas akan
menghasilkan n, dengan begitu B dapat mengembalikan pesan semula m. Prosedur
dekripsi bekerja karena
cd ≡ (n)d ≡ (mod N) (3)
Kemudian, karena ed ≡ 1 (mod p-1)
dan ed ≡ 1 (mod q-1), hasil dari Fermat's little theorem.
ned ≡ n (mod p) (4)
dan
ned ≡ n
(mod q) (5)
Karena p dan q merupakan bilangan
prima yang berbeda, mengaplikasikan Chinese remainder theorem akan menghasilkan
dua macam kongruen
ned ≡ n (mod pq) (6)
Serta cd ≡ n
(mod N) (7)
Contoh Penghitungan RSA
Sekarang kita mencoba suatu
contoh untuk mengenal lebih dalam sistem kerja enkripisi RSA. Misalnya kita mau
mengenkripsi kata “SECRET” dengan RSA, lalu kita dekripsi kembali ke dalam
plaintext. Karena p dan q berjumlah minimal 100
digit atau lebih, nilai d dan e bisa berjumlah sama dengan 100 digit dan nilai
N akan berjumlah 200 digit. Untuk itu di contoh pemakaian berikut, kita akan
memakai angka-angka yang kecil agar mudah dalam penghitungan. Cara
pengerjaannya adalah :
Kita pilih p = 3 dan q = 5
Hitung N = pq = 3*5 = 15
Nilai e harus merupakan bilangan
prima yang lebih besar dan relatif dekat dengan (p-1)(q-1) = (2)(4) = 8,
sehingga kita pilih e = 11. Angka 11 adalah bilangan prima terdekat dan lebih
besar daripada 8
Nilai d harus dipilih sehingga
(ed - 1)
(p-1)(q-1)
adalah sebuah integer. Lalu nilai
(11d - 1) / [(2)(4)] = (11d - 1)
/ 8
juga merupakan integer. Setelah
melalui proses penghitungan, salah satu nilai yang mungkin adalah d = 3.
Lalu kita masukkan kata yang akan
dienkripsi, “SECRET”. Kita akan mengkonversi string ini ke representasi desimal
menggunakan nilai karakter ASCII, yang akan menghasilkan nilai ASCII 83 69 67
82 69 84
Pengirim akan mengenkripsi setiap
digit angka pada saat yang bersamaan menggunakan nilai kunci publik (e, n) =
(11,15). Lalu setiap karakter ciphertext akan masuk ke persamaan
Ci = Mid mod 15
Yang akan menghasilkan nilai
digit masukan adalah 0x836967826984 yang akan dikirim sebagai 0x2c696d286924
Penerima akan mendekripsi setiap
digit angka menggunakan nilai kunci privat (d, n) = (3, 15). Lalu, setiap
karakter plaintext akan masuk persamaan
Mi = Ci3 mod 15
String masukan yang bernilai
0x2c696d286924, akan dikonversi kembail menjadi 0x836967826984, dan akhirnya
angka-angka tersebut akan diubah kembali menjadi bentuk string plaintext yang
bernilai “SECRET”
Dari contoh di atas kita dapat
menangkap suatu kelemahan dari pemakaian p dan q yang bernilai kecil yaitu bisa
kita lihat di digit ke-4, ke-6 dan ke-9 tidak berubah saat dienkripsi, dan
nilai 2 dan 8 dienkripsi menjadi 8 dan 2, yang berarti dienkripsi menjadi kebalikannya.
Tapi kesimpulan yang bisa diambil dari contoh yang sederhana ini adalah RSA
dapat digunakan dalam penyandian dalam pengiriman informasi. Kunci RSA yang mempunyai ukuran
512 dan 768 bit dianggap masih lemah dan mudah dijebol. Ukuran kunci yang
dianjurkan adalah 1024 bit. Ukuran 2048 dan 3072 bit merupakan suatu ukuran
yang lebih baik.
Sumber :