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. RSA adalah salah satu algoritma
kriptografi yang menggunakan konsep kriptografi kunci publik. RSA
membutuhkan tiga langkah dalam prosesnya, yaitu pembangkitan kunci,
enkripsi, dan dekripsi. Proses enkripsi dan dekripsi merupakan proses
yang hampir sama. Jika bilangan acak yang dibangkitkan kuat, maka akan
lebih sulit untuk melakukan cracking terhadap pesan. Parameter kuat
tidaknya suatu kunci terdapat pada besarnya bilangan acak yang
digunakan.
Apa itu RSA?
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 (‘R’ivest -
‘S’hamir – ‘A’dleman). 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.
RSA adalah sebuah algoritma berdasarkan skema kriptografi public-key.
Lebih jauh, RSA adalah algoritma yang mudah untuk diimplementasikan dan
dimengerti. algoritma RSA adalah sebuah aplikasi dari sekian banyak
teori seperti extended Euclid algorithm, euler's function sampai fermat
theorem.
Konsep fundamental dari Kriptografi Kunci Publik ditemukan oleh
Whitfield Diffie dan Martin Hellman, dan secara terpisah oleh Ralph
Merkle. Sedangkan konsep dasar Kriptografi Kunci Publik terletak pada
pemahaman bahwa kunci selalu berpasangan: kunci enkripsi dan kunci
dekripsi. Juga perlu diingat bahwa sebuah kunci tidak dapat
dibangkitkan dari kunci lainnya. Pemahaman kunci enkripsi dan dekripsi
sering disebut sebagai kunci publik dan kunci privat. Seseorang harus
memberikan kunci publiknya agar pihak lain dapat mengenkripsi sebuah
pesan. Dekripsi hanya terjadi jika seseorang mempunyai kunci privat.
Dasar Matematika
1. Sifat Pembagian pada Bilangan Bulat
Diberikan dua buah bilangan bulat
a dan b dengan syarat a ≠ 0. Dikatakan a habis membagi b (a divides b)
jika terdapat bilangan c sedemikian hingga b = ac.
Notasi : a | b jika b = ac, c ϵ Z dan a ≠ 0.
Contoh :
4 | 12 karena 12 = 4 × 3
Teorema Euclidean :
Misalkan m dan b adalah dua buah
bilangan bulat dengan syarat n > 0. Jika m dibagi dengan n maka
terdapat dua buah bilangan bulat unik q (quotient) dan r (remainder)
sedemikian sehingga m = nq + r dengan 0 ≤ r < n.
Contoh :
1987 = 97 × 20 + 47, yaitu 1987 dibagi dengan 97 memberikan hasil 20 dan sisa 47
2. Pembagi Bersama Terbesar
Diberikan dua buah bilangan bulat
tidak nol a dan b. Pembagi bersama terbesar (greatest common divisor
atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian
hingga d | a dan d | b, atau dinyatakan dengan gcd(a,b) = d.
Contoh :
Faktor pembagi 45 adalah : 1, 3, 5, 9, 15, 45
Faktor pembagi 36 adalah : 1, 2, 3, 4, 6, 9, 12, 18, 36
Faktor pembagi bersama dari 45 dan 36 adalah : 1, 3, 9
Sehingga gcd(45, 36) = 9
3. Algoritma Euclidean
Dengan dasar Teorema Euclidean
sebelumnya, dikembangkan sebuah algoritma (yang disebut dengan
algoritma Euclidean) untuk mencari gcd dari dua buah bilangan bulat.
Definisi :
Diberikan dua buah bilangan bulat tak negative a dan b (a ≥ b). Maka terdapat qi, ri ϵ Z sehingga :
Jadi rm+1 = gcd(rm, rm+1) = gcd(rm-1, rm) = gcd(rm-2, rm-1) = … = gcd(a, b)
Contoh :
a = 80, b = 12, dan dipenuhi syarat a ≥ b
Dihitung dengan menggunakan algoritma Euclidean sbb. :
Jadi gcd (80, 12) = gcd (12, 8) = gcd (8,4) = 4
4. Algoritma Euclidean yang Diperluas
Algoritma Euclidean yang
diperluas dapat digunakan untuk menentukan bilangan bulat positif b <
a memiliki invers (terhadap operasi perkalian) modulo a dengan
memeriksa jika rm+1 = 1.
Definisi :
Diberikan qj seperti pada Algoritma Euclidean, didefinisikan
Berdasarkan pada qj hasil algoritma Euclidean dan pendefinisian tj dan sj diperoleh hubungan rj, tj, dan sj yang diberikan oleh :
Teorema :
Jika j = 0, 1, 2, …, m maka rj = sja + tjb dengan tj dan sj seperti yang didefinisikan dan rj diperoleh di Algoritma Euclidean.
Akibat :
Jika gcd (a, b) = 1, maka b-1 = tj
Contoh :
a = 111, b = 25
Dengan menggunakan algoritma Euclidean dicari j dan dihitung apakah gcd (111, 25) = 1.
111 = 4 × 25 + 11 j=1
25 = 2 × 11 + 3 j=2
11 = 3 × 3 + 2 j=3
3 = 1 × 2 + 1 j=4
2 = 1 × 2 j=5
Dari algoritma Euclidean sebelumnya diketahui jika gcd (111, 25) = 1, maka :
t0 = 0
t1 = 1
t2 = t0 – q1t1 = 0 – 4 × 1 = -4
t3 = t1 – q2t2 = 1 – 2 × (-4) = 9
t4 = t2 – q3t3 = -4 – 3 × 9 = -31
t5 = t3 – q4t4 = 9 – 1 × (-31) = 40
Maka 25-1 terhadap modulo 111 adalah 40.
5. Kekongruenan
Definisi Aritmatika Modulo :
Diberikan dua buah bilangan bulat a dan m yang > 0. Operasi a mod m memberikan sisa jika a dibagi dengan m. Bilangan m disebut modulus atau modulo, dan hasil aritmatika modulo m terletak di himpunan {0, 1, … m-1}
Notasi : a mod m = r, sedemikian sehingga a = mq + r, dengan 0 ≤ r < m.
Contoh :
23 mod 5 = 3
-41 mod 9 = 4
Definisi Kongruen :
Diberikan dua buah bilangan bulat a dan b, dan m adalah bilangan > 0, maka a ≡ b (mod m) jika m habis membagi a – b.
Contoh :
Diberikan dua buah bilangan bulat a dan m yang > 0. Operasi a mod m memberikan sisa jika a dibagi dengan m. Bilangan m disebut modulus atau modulo, dan hasil aritmatika modulo m terletak di himpunan {0, 1, … m-1}
Notasi : a mod m = r, sedemikian sehingga a = mq + r, dengan 0 ≤ r < m.
Contoh :
23 mod 5 = 3
-41 mod 9 = 4
Definisi Kongruen :
Diberikan dua buah bilangan bulat a dan b, dan m adalah bilangan > 0, maka a ≡ b (mod m) jika m habis membagi a – b.
Contoh :
17 ≡ 2 (mod 3)Teorema :
Kekongruenan a ≡ b (mod m) dapat pula dituliskan dalam hubungan
a = b + km
untuk k adalah sembarang bilangan bulat. Berdasarkan definisi aritmatika modulo,
a mod m = r dapat juga dituliskan sebagai
a ≡ r (mod m)
- Jika a ≡ b (mod m) dan c adalah sembarang bilangan bulat positif maka
- ( a + c) ≡ (b + c) (mod m)
- ac ≡ bc (mod m)
- ap ≡ bp (mod m) untuk suatu bilangan bulat tak negative p.
- Jika a ≡ b (mod m) dan c ≡ d (mod m), maka
- (a + c) ≡ (b + d) (mod m)
- ac ≡ bd (mod m)
6. Bilangan Prima
Bilangan bulat positif p (p>1)
disebut bilangan prima jika pembaginya hanya 1 dan p. Bilangan selain
bilangan prima disebut dengan bilangan komposit.
The Fundamental Theorem of Arithmetic :
Setiap bilangan bulat positif
yang lebih besar atau sama dengan 2 dapat dinyatakan sebagai perkalian
satu atau lebih bilangan prima.
Contoh :
91 = 7 × 13
100 = 2 × 2 × 5 × 5
Terdapat banyak metode yang dapat digunakan untuk menguji keprimaan sebuah bilangan. Salah satunya adalah Teorema Eratosthenes.
Teorema Eratosthenes :
Untuk setiap bilangan komposit n, pasti ada bilangan prima p dimana p ≤√n sehingga p | n.
Dari teorema tersebut, dapat kita
simpulkan jika p tidak membagi habis n, maka n bukan bilangan komposit
(dengan kata lain n adalah bilangan prima).
Contoh :
1. n = 1993 prima?1993 = 44.6430…p ≤ 44.6430…. = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, dan 43Karena tidak ada p yang dapat membagi habis n, maka n bukanlah bilangan komposit. Sehingga 1993 adalah bilangan prima.
2. n = 121121 = 11p ≤ 11 = 2, 3, 5, 7, dan 117Karena 11 | 121 maka n merupakan bilangan komposit. Sehingga 121 bukan bilangan prima.
7. Relatif Prima
Dua buah bilangan bulat a dan b dikatakan relative prima jika gcd (a, b) = 1. Jika a dan b relative prima, maka terdapat bilangan bulat a dan b sedemikian sehingga ma + nb = 1.Contoh :
gcd (111, 25) = 1
m(111) + n(25) = 1, untuk m = -9 dan n = 40, maka
(-9)(111) + (40)(25) = -999 + 1000 = 1
8. Fungsi Euler (ϕ)
Fungsi Euler mendefinisikan ϕ(n) untuk n ≥ 1 yang menyatakan banyaknya bilangan bulat positif < n yang mempunyai invers terhadap operasi perkalian.Contoh :
Z8 = {0, 1, 2, 3, 4, 5, 6, 7}Teorema (untuk mencari ϕ(n)) :
ϕ(8) = 4, karena yang memiliki invers hanya 1, 3, 5, 7.
Contoh :
Jika n = pq adalah bilangan komposit dengan p dan q prima, maka ϕ(n) = ϕ(p) ϕ(q) = (p-1) (q-1).
Teorema 2 :
Diberikan dua buah bilangan bulat a dan n, dengan n ≥ 2 sedemikian sehingga gcd(a, n) = 1, maka
aϕ(n) ≡ 1 (mod n)
Algoritma RSA didasarkan pada teorema Euler yang menyatakan bahwa
Berdasarkan ap ≡ bp (mod m) :
≈ akϕ(n) ≡ 1k (mod n)
a diganti dengan m :
≈ mkϕ(n) ≡ 1k (mod n)
Kedua ruas dikalikan dengan m :
≈ mkϕ(n)+1 ≡ m (mod n) (kedua ruas dikali dengan m)
(pers. 1)
Misal e dan d dipilih sedemikian hingga ed = 1 (mod n) atau ed = kϕ(n) + 1.
Maka disubsitusikan ke pers.1 :
med ≡ m (mod n)
(me)d ≡ m (mod n)
Persamaan diatas dapat diartikan perpangkatan m dengan e diikuti dengan perpangkatan dengan d menghasilkan kembali m semula. Maka berdasarkan persamaan tersebut, enkripsi dan dekripsi pada RSA dapat dirumuskan sebagai berikut :
1. Kunci public (n, e)
2. Kunci privat (d)
n = 8Teorema 1 :
m = 1, p1 = 2, e1 = 3
ϕ(8) = (23 - 22) = 8 – 4 = 4
Jika n = pq adalah bilangan komposit dengan p dan q prima, maka ϕ(n) = ϕ(p) ϕ(q) = (p-1) (q-1).
Teorema 2 :
Diberikan dua buah bilangan bulat a dan n, dengan n ≥ 2 sedemikian sehingga gcd(a, n) = 1, maka
aϕ(n) ≡ 1 (mod n)
Algoritma 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.Algoritma RSA didasarkan pada teorema Euler yang menyatakan bahwa
aϕ(n) ≡ 1 (mod n)dengan syarat a harus relative prima terhadap n.
Berdasarkan teorema-teorema yang ada pada bahasan kekongruenan sebelumnya, bisa kita peroleh :aϕ(n) ≡ 1 (mod n)
Berdasarkan ap ≡ bp (mod m) :
a diganti dengan m :
Kedua ruas dikalikan dengan m :
(pers. 1)
Misal e dan d dipilih sedemikian hingga ed = 1 (mod n) atau ed = kϕ(n) + 1.
Maka disubsitusikan ke pers.1 :
med ≡ m (mod n)
(me)d ≡ m (mod n)
Persamaan diatas dapat diartikan perpangkatan m dengan e diikuti dengan perpangkatan dengan d menghasilkan kembali m semula. Maka berdasarkan persamaan tersebut, enkripsi dan dekripsi pada RSA dapat dirumuskan sebagai berikut :
Ee(m) = me (mod n) = cDd(c) = cd (mod n)
1. Algoritma Pembangkitan Kunci pada RSA
Kelebihan RSA terletak pada pasangan kunci yang digunakan untuk mengenkripsi dan mendekripsi pesan. Berikut langkah-langkah yang digunakan untuk membangkitkan pasangan kunci di RSA :- Pilih dua buah bilangan prima sembarang p dan q.
- Hitung n = p * q, dengan p ≠ q.
- Hitung ϕ(n) = (p-1)(q-1)
- Pilih kunci public e, yang relative prima terhadap ϕ(n).
- Bangkitkan kunci privat d = 1+ k ϕ(n) / e atau d = e-1 (1 + k.ϕ(n)).
1. Kunci public (n, e)
2. Kunci privat (d)
2. Algoritma Enkripsi dan Dekripsi
Algoritma enkripsi pada RSA adalah sebagai berikut :- Ambil kunci public milik penerima pesan (n dan e).
- Pecah plainteks menjadi blok-blok m1, m2, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam selang [0, n-1].
- Setiap blok mi dienkripsi menjadi blok ci dengan rumus ci = mie mod n
Kriptanalisis
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:
- Brute Force
- Mathematical Attack
- Man-In-The-Middle Attack
- Choosen Ciphertext Attack
