BAB II
PEMBAHASAN
A. Sejarah RSA (Rivest – Shamir –
Adlemen)
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 (Rivest - Shamir – Adleman).
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.
B.Pengertian RSA
RSA merupakan algoritma
kriptografi asimetri, dimana kunci yang digunakan untuk mengenkripsi berbeda
dengan yang digunakan untuk mendekripsi.Kunci yang digunakan untuk mengenkripsi
disebut dengan kunci public, dan yang digunakan untuk mendekripsi disebut
dengan kunci privat.
C. Tiga langkah dalam proses RSA
a. Pembangkitan Kunci
b. proses enkripsi
c. proses dekripsi
a. pembangkitan kunci
Berikut
langkah-langkah yang digunakan untuk membangkitkan pasangan kunci di RSA :
1. Pilih dua buah bilangan prima sembarang p dan q.
2. Hitung n = p * q, dengan p ≠ q.
3. Hitung ϕ(n) = (p-1)(q-1)
4. Pilih kunci public e, yang relative prima terhadap
ϕ(n).
5. Bangkitkan kunci privat d = 1+ kϕ(n) / e
atau d = e-1 (1 + k.ϕ(n)).
Hasil dari algoritma diatas adalah :
1. Kunci public (n, e)
2. Kunci privat (n, d)
b. proses enkripsi
Enkripsi
adalah suatu proses mengubah sebuah teks murni (plaintext) menjadi sebuah runtutan
karakter atau data yang terlihat tidak berarti dan mempunyai urutan bit yang
tidak beraturan, di sebut chipertext.
Misalkan Bob ingin mengirim sebuah pesan 'H' kepada Alice.
a. Alice harus membuat keynya sehingga ia memiliki private dan
public keys.
private key = (M,d)
public key = (M,e)
b. Mengubah 'H' menjadi sebuah
bilangan yang menggunakan alphabet
yang valid dengan tabel bilangan. Sebuah contoh mudah adalah
mapping A = 1, B = 2 ... Z = 26.
sehingga H = 8
c. C = 8^e (mod M)
C adalah sebuah bilangan
ter-encrypt.
d. Bob mengirimkan bilangan
tersebut kepada Alice sehingga Alice
dapat melakukan decode ulang menggunakan private keynya.
c. proses dekripsi
Dekripsi adalah Proses pengubahan kembali ciphertext menjadi
plaintext.
Misalkan Alice menerima sebuah pesan ter-encrypt, ia akan men-decrypt-nya
menggunakan tahapan-tahapan berikut:
a. Alice mempunyai private key dari
langkah-langkah di atas (M,d)
b. N = C^d (mod M)
c. N adalah bilangan. Gunakan konversi
table alphabet untuk mengubah
N menjadi karakter yang direpresentasikannya.
D. Contoh RSA
Akan dilakukan enkripsi menggunakan algoritma RSA
terhadap plaintext M = FISIKA. Pertama-tama plaintext tersebut
diubah menjadi format ASCII sebagai beri-kut :
Text (karakter
|
F
|
I
|
S
|
I
|
K
|
A
|
ASCII (heksa)
|
46
|
49
|
53
|
49
|
4B
|
41
|
ASCII (desimal)
|
70
|
73
|
83
|
73
|
75
|
65
|
Plaintext
dalam format ASCII desimal terse-but
kemudian dipecah menjadi blok-blok tiga digit berikut :
Mi =707
|
M3= 737
|
M2= 383
|
M4= 565
|
Dalam membuat kunci RSA, perlu
dirancang agar nilai mi masih terletak di dalam ren-tang antara 0 sampai
n – 1. Maka ditentu-kan bahwa nilai n minimal adalah 909. Nilai
ini diambil berdasarkan pertimbangan bahwa karakter huruf kapital dengan nilai
terbesar adalah Z dengan nilai ASCII yaitu 5Ah atau 90. Kombinasi ZZ akan dapat
dipecah menjadi blok 909 atau 090.
Misalkan dipilih p = 23 dan
q = 43 (keduanya prima), maka dapat dihitung
n = p
x q = 989
m = (p
– 1) x (q – 1) = 924
Dipilih
kunci publik e = 25 (yang relatif prima dengan 924 karena pembagi
ber-sama terbesarnya adalah 1). Bahwa 25 relatif prima terhadap 924 dapat
dibuktikan dengan mencari nilai gcd (25,924) melalui algoritma Euclid seperti
berikut.
Hasil gcd pada algoritma ini
adalah hasil sisa bagi terakhir sebelum 0. Maka padaperhitungan diatas terlihat
bahwa sisa bagi sebelum nol adalah 1. Maka gcd (25, 924) = 1. Selanjutnya untuk
menghitung kunci privat d algoritma Extended Euclid sebagai berikut.
P2
dan P3 dihitung melalui persamaan berikut:
P2 = (pi-2 – pi-1qi-2)
mod n
=(0 – 1(36)) mod 924 =
888
P3 =(1 – 888(1)) mod 924 = 37
Maka diperoleh kunci publik
adalah 25 dan 989. Sedangkan kunci privat adalah 37 dan 989. Enkripsi setiap
blok diperoleh meng-gunakan kunci public 25 dan 989 dengan cara sebagai berikut
:
c1 = 70725 mod 989
Untuk
menghitung 70725 mod 989 dapat menggunakan teknik divide and conquer untuk
membagi pemangkatnya sampai berukuran kecil. Ilustarinya adalah sebagai
berikut.
Jadi c1 = 70725 mod 989 = 313.
Dengan
cara yang sama dapat diperoleh :
c2 = 38325
mod 989 = 776
c3 = 73725 mod 989 = 737
c4 = 56525 mod 989 = 909
Maka ciphertext adalah C =
313 776 737 909
Perlu
diingat, bahwa ciphertext ini dalam format ASCII desimal. Jika diubah
kembali
menjadi
format karakter maka dapat diperoleh:
ASCII(desimal)
|
31
|
37
|
76
|
73
|
79
|
09
|
ASCII (heksa)
|
1F
|
24
|
4
|
49
|
4F
|
09
|
Teks (karakter)
|
%
|
L
|
I
|
O
|
Heksa desimal 1F dan 09
adalah non-printing characters.
Untuk
melakukan dekripsi (mengubah ci-phertext menjadi plaintext) maka
digunakan kunci privat 37 dan 989 dengan cara seba-gai berikut :
m1 = 31337 mod 989 = 707
m2 = 77637 mod 989 = 383
m3 = 73737 mod 989 = 737
m4 = 90937 mod 989 = 565
Maka
diperoleh plaintext 707 383 737 565
E. Keamanan RSA
Sisi keamanan pada sistem RSA
terletak pada sulitnya memfaktorkan sebuah bilangan besar n yang dihasilkan
dari perkalian dua buah bilangan prima p dan q. nilai n yang dihasilkan
bersifat tidak rahasia, sementara nilai bilangan prima p dan q harus bersifat
rahasia, sehingga hampir mustahil bagi seorang penyerang untuk mendapatkan
nilai ϕ (n) (totien (n)atau disebut juga phi(n)) yang merupakan nilai bilangan
dasar yang digunakan untuk menghasilkan pasangan kunci publik e dengan kunci
privat d.
Secara umum, tipe serangan yang mungkin untuk algoritma RSA adalah:
1.
Brute Force
2.
Mathematical Attack
3.
Man-In-The-Middle
Attack
4.
Choosen Ciphertext
Attack
1. Brute Force
Tipe serangan ini berlaku untuk semua
jenis algoritma kriptografi, baik kriptografi simetri maupun asimetri.Model
serangan brute force adalah dengan melakukan percobaan terhadap semua kemungkinan
kunci pada sebuah sistem kriptografi.Oleh karena itu, performa serangan ini
sangat tergantung kepada key space dari sistem kriptografi yang ditargetkan.
Pada sistem RSA, brute force bekerja
dengan cara melakukan percobaan pada semua kemungkinan kunci privat. Oleh
karena itu, kemungkinan serangan tipe ini dapat diperkecil dengan jalan
memperbesar nilai key space yang dalam hal ini adalah memperbesar nilai d. Dari
persamaan dasar untuk mendapatkan nilai d berikut kita dapat memperbesar nilai
d yaitu d = 1 + k ϕ ( n ) / e. Dengan mengambil nilai p dan q
yang besar, maka akan dihasilkan nilai d yang cukup besar, sehingga proses
dekripsi ciphertext dengan bersamaan : cd mod n menghasilkan
kompleksitas yang besar.
2. Mathematical Attack
Dasar dari tipe serangan ini adalah
dengan memanfaatkan persamaan matematis yang mendasari algoritma RSA. Sebagai
contoh, diasumsikan terjadi kesalahan dalam bit ci ketika melakukan proses
dekripsi ciphertext c. Untuk I bernilai acak, I elemen dari {0,1,2,...,t-1}
kita lambangkan bit yang mengalami kesalahan tersebut sebagai c’i. Maka pesan
yang akan dihasilkan jika dilakukan dekripsi adalah:
Penyerang sekarang telah memiliki m dan m’, maka ia dapat menghitung:
Yang bernilai sama dengan (c’i/ci ) mod n jika di = 1 atau bernilai sama
dengan 1 jika di = 0. Lalu, kita asumsikan tiap angka yang akan didapat adalah
relatif prima terhadap n. Penyerang dapat dengan mudah menghitung semua nilai
yang mungkin untuk (c’i/ci ) mod n, yang berjumlah sebanyak t2 karena c’i
memiliki kemungkinan nilai sebanyak t. Penyerang kemudian membandingkan
angka-angka yang didapatnya dengan (m’/m) mod n. Ketika didapatkan sebuah nilai
yang sama, maka dapat diketahui i dan di adalah 1. Contoh ini menggambarkan ide
dasar dari serangan ini. Contoh ini menunjukkan bahwa kesalahan bit pada lokasi
tertentu dapat menyebabkan terbukanya kunci privat.
3. Man in The Middle
Serangan tipe ini sebenarnya tidak
bersentuhan langsung dengan algoritma enkripsi yang digunkan, namun dengan
memanfaatkan fakta bahwa setiap akan melakukan pengiriman pesan, seorang
pengirim akan dikirimkan kunci publik. Kunci ini kemudian akan digunakan oleh
pengirim untuk melakukan enkripsi data yang kemudian akan dikirim melalui
saluran yang sama. Seorang penyerang dapat melakukan intercept pada saluran
komunikasi yang digunakan oleh pengirim dan penerima dalam bertukar data. Untuk
lebih jelasnya, skema serangan ini dapat dilihat pada gambar berikut.
Misal, penerima mengirimkan
kunci publik XYZ kepada pengirim pesan.Namun dalam perjalanannya, seorang
penyerang menangkap kunci tersebut. Penyerang kemudia mengubah kunci publik
tersebut dengan kunci publik ABC yang telah ia buat. Di sini pengirim pesan,
percaya bahwa kunci yang dikirim adalah merupakan kunci dari penerima pesan.
Pengirim kemudian melakukan
enkripsi terhadap pesan dengan kunci yang diterianya, kemudian mengirimkannya
kepada penerima. Penyerang akan menerima pesan ter-ekripsi yang dikirim oleh
pengirim. Oleh karena penyerang memiliki pasangan kunci publik ABC maka dengan
mudah ia dapat mendekripsi pesan tersebut dan selanjutnya akan di enkripsi
kembali dengan menggunakan kunci public XYZ sebelum diteruskan kepada pihak
penerima.
4. Choosen Ciphertext Attack (CCA)
Skema dasar dari RSA sangat rentan
terhadap tipe serangan CCA. Skema Serangan Choosen Ciphertext Attack berupa
seorang penyerang akan memilih beberapa buah ciphertext dan kemudian melakukan
dekripsi untuk menghasilkan plainteks dengan kunci privat yang ia tentukan.
Dengan langkah yang sama, penyerang akan melakukan proses enkripsi.
Dari sini, penyerang dapat
menganalisa pola yang terbentuk.Seperti diketahui, bentuk dasar dari pola
ekripsi RSA adalahE({e,n},P1) X E({e,n},P2) = E({e,n},[P1 x P2])Dari persamaan
di atas, kita dapat melakukan dekripsi terhadap ciperteks C dengan persamaan C
= Me mod n sebagai berikut: :
misal: x = (C x 2e) mod n
dari x diatas, kita dapat menemukan plainteks sebagai berikut :
x=(C mod n) x (2e mod n) = (Me mod n) x (2e
mod n)= (2M)e mod n
Untuk itu, dalam praktiknya, sebelum
dilakukan enkripsi terhadap sebuah pesan, RSA melakukan kombinasi padding dan
hashing pada pesan seperti yang diperlihatkan pada gambar di bawah, sehingga
persamaan di atas tidak terpenuhi.
F. Kelebihan dan
Kekurangan 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.
Tidak ada komentar:
Posting Komentar