Sandi RSA merupakan algoritma kriptografi kunci publik
(asimetris). Ditemukan pertama kali pada tahun 1977
oleh R. Rivest, A. Shamir, dan L. Adleman. Nama RSA
sendiri diambil dari ketiga penemunya tersebut.
Sebagai algoritma kunci publik, RSA
mempunyai dua kunci, yaitu kunci publik dan kunci
rahasia. Kunci publik boleh diketahui oleh siapa saja,
dan digunakan untuk proses enkripsi. Sedangkan kunci
rahasia hanya pihak-pihak tertentu saja yang boleh
mengetahuinya, dan digunakan untuk proses dekripsi.
Keamanan sandi RSA terletak pada sulitnya
memfaktorkan bilangan yang besar. Sampai saat ini RSA
masih dipercaya dan digunakan secara luas di internet.
Gambar 1. Skema algoritma kunci publik
Sandi RSA terdiri dari tiga proses, yaitu proses
pembentukan kunci, proses enkripsi dan proses dekripsi.
Sebelumnya diberikan terlebih dahulu beberapa konsep
perhitungan matematis yang digunakan RSA.
2. Konsep Dasar Perhitungan Matematis
2.1. Fungsi Phi-Euler
Fungsi Phi-Euler j (n) merupakan fungsi terhadap
bilangan bulat positif n yang menyatakan banyaknya
elemen n
ℤ yang mempunyai invers terhadap operasi
pergandaan. Ingat bahwa n
ℤ belum tentu merupakan
grup terhadap operai pergandaan. Dengan kata lain, j (n)
adalah banyaknya elemen {x,0 £ x < n | gcd(x,n) =1} .
Jika n = pq dengan p dan q adalah bilangan prima, maka
j (n) = ( p -1)(q -1) . Jika n adalah bilangan prima, maka
j (n) = n -1 . Bukti pernyataan di atas dapat dilihat di
(Fraleigh, 2000), (Buchmann, 2000), dan (Stinson, 2006).
2.2. Algoritma Euclide
Algoritma ini digunakan untuk mencari nilai pembagi
persekutuan terbesar dari dua bilangan bulat. Algoritma
ini didasarkan pada pernyataan berikut ini. Diberikan
bilangan bulat 0 r dan 1 r , dengan 0 1 r ³ r , kemudian
dihitung menggunakan algoritma pembagian:
0 1 1 2 r = q r + r , 2 1 0 < r < r
1 2 2 3 r = q r + r , 3 2 0 < r < r
...
n 2 n 1 n 1 n r q r r - - - = + , 1 0 n n r r - < <
n 1 n n r q r - =
Dari pernyataan di atas, dapat ditunjukkan bahwa
0 1 1 2 1 gcd( , ) gcd( , ) ... gcd( , ) gcd( ,0) n n n n r r r r r r r r - = = = = = .
Bukti lihat di (Buchmann, 2000)
Contoh 1. Akan dihitung gcd(40,24).
Jawab: 40 = 1.24 + 16
24 = 1.16 + 8
16 = 2.8
Jadi, gcd(40,24)=8.
2.3. Algoritma Euclide Diperluas
Algoritma ini merupakan perluasan dari algoritma
Euclide (Extended Euclidean Algorithm), digunakan
untuk mencari invers terhadap operasi pergandaan.
Algoritma ini didasarkan pada pernyataan berikut.
Diberikan bilangan bulat positif 0 r dan 1 r , 0 1 r > r . Jika
( ) 0 1 gcd r , r = 1, maka 1
1 0 r - mod r ada. Jika ( ) 0 1 gcd r , r ¹ 1 ,
maka 1
1 0 r - mod r tidak ada. Gunakan rumus rekurensi
berikut ini.
0 t = 0 , 1 t = 1
j j 2 j 1 j 1 t t q t - - - = - , j ³ 2 ....................... (1)
Ket: j q diperoleh dari perhitungan ( ) 0 1 gcd r , r
menggunakan algoritma Euclide. Jika ( ) 0 1 gcd r , r = 1,
berarti 1
1 n r - = t . Sehingga n n 1 r = t r atau 1 1 n = t r . Bukti
bisa dilihat di (Stinson, 2006).
A enkripsi dekripsi B
Plainteks cipherteks Plainteks
Kunci Publik Kunci Rahasia
Kriptografi Kunci Publik: Sandi RSA
Copyright © Kelompok Studi Sandi – Yogyakarta, 30 Agustus 2008
http://sandi.math.web.id
2
Contoh 2. Akan dihitung 28-1 mod 75 .
Diketahui 0 r = 75 dan 1 r = 28 . Hitung gcd(75,28)
menggunakan algoritma Euclide, yaitu:
75 = 2.28 + 19 n = 1, 1 r = 28 , 1 q = 2
28 = 2.19 + 9 n = 2, 2 r = 19 , 2 q = 2
19 = 2.9 + 1 n = 3, 3 r = 9 , 3 q = 2
9 = 9.1 n = 4, 4 r = 1 , 4 q = 9
Jadi, gcd(75,28) = 1, dengan kata lain 28-1 mod 75 ada.
Dari penyelesaian algoritma Euclide di atas diperoleh
diperoleh n = 4. Selanjutnya, menggunakan rumus
rekurensi (1) di atas, diperoleh: (semua perhitungan
dilakukan dalam mod 75)
2 0 1 1 t = t - q t = 0 - 2.1 = -2 = 73
3 1 2 2 t = t - q t = 1-1.(-2) = 3
4 2 3 3 t = t - q t = -2 - 2.3 = -8 = 67
1
4 4 1 r = t r = 67.28 = 1Û67 = 28-
Dari hasil terakhir di atas, diperoleh 28-1 mod 75 = 67 .
2.4. Metode Fast Exponentiation
Metode ini digunakan untuk menghitung operasi
pemangkatan besar bilangan bulat modulo dengan cepat.
Metode ini memanfaatkan ekspansi biner dari
eksponennya dan didasarkan pada pernyataan berikut ini:
( ) 1 2
2i 2i g g + = .
Untuk lebih jelasnya mengenai langkah-langkah metode
fast exponentiation, perhatikan contoh berikut ini.
Contoh 3. Akan dihitung 673 mod100 .
Jawab.
73 = 1.26 +1.23 +1.20 atau 73 = ( )2 1001001 .
(semua perhitungan dilakukan dalam mod 100)
620 = 6 , 621 = 36 , 622 = 362 = 96 , 623 = 16 ,
624 = 162 = 56 , 625 = 562 = 36 , 626 = 562 = 96 .
Sehingga diperoleh:
673 = 6.623 .626 = 6.16.96= 16 .
Jadi, 673 mod100 = 16.
Setelah mempelajari konsep-konsep dasar
perhitungan matematis, berikut ini diberikan prosesproses
yang digunakan RSA.
3. Pembentukan Kunci
Berikut ini adalah proses pembentukan kunci. Proses ini
dilakukan oleh pihak penerima, dalam hal ini adalah B.
(1) Pilih bilangan prima p dan q.
(2) Hitung n = pq .
(3) Hitung j (n) = ( p -1)(q -1) .
(4) Pilih sebarang bilangan b, 1 < b
(5) Hitung invers dari b, yaitu a = b-1 modj (n) .
(6) Kunci publik: (n, b) dan kunci rahasia: a.
Agar mempermudah dalam memahami sandi
RSA, khusus pada tulisan ini, plainteks yang digunakan
hanya berupa bilangan 0 s/d 25 yang berkorespondensi
dengan huruf a s/d z. Akan tetapi pada penggunaan yang
sebenarnya, digunakan korespondensi khusus seperti
kode ASCII, serta bilangan-bilangan yang sangat besar.
Perhatikan, dalam pemilihan p dan q harus
memenuhi n = pq lebih dari atau sama dengan nilai
plainteks yang mungkin. Dalam hal ini n = pq ³ 25 .
Tabel 1. Tabel Korespondensi
a b c d e f g h i j k l m
0 1 2 3 4 5 6 7 8 9 10 11 12
n o p q r s t u v w x y z
13 14 15 16 17 18 19 20 21 22 23 24 25
Contoh 4. B memilih p = 5 dan q = 11 , maka n = 55
dan j (55) = (5 -1)(11-1) = 4.10 = 40 . Selanjutnya dapat
dipilih b = 13 , sebab gcd(13,40) = 1 . Menggunakan
algoritma Euclide diperluas diperoleh bahwa
a =13-1mod 40 = 37 . Jadi, kunci publiknya adalah
(n,b) = (55,13) dan kunci rahasianya adalah a = 37 .
Selanjutnya B mengirimkan kunci publik kepada A.
4. Enkripsi
Berikut ini adalah proses enkripsi RSA. Dilakukan oleh
pihak pengirim, dalam hal ini adalah A. Seluruh
perhitungan pemangkatan bilangan modulo dilakukan
menggunakan metode fast exponentiation.
(1) Ambil kunci publik (n,b).
(2) Pilih plainteks m, dengan 0 £ m £ n -1 .
(3) Hitung c = mb mod n .
(4) Diperoleh cipherteks c, dan kirimkan kepada B.
Kriptografi Kunci Publik: Sandi RSA
Copyright © Kelompok Studi Sandi – Yogyakarta, 30 Agustus 2008
http://sandi.math.web.id
3
Contoh 5. A menerima kunci publik (n,b) = (55,13) dari
B. Misalkan plainteksnya adalah “kripto”, menggunakan
Tabel 1 diperoleh 1 m = 10 , 2 m = 17 , 3 m = 8 , 4 m = 15 ,
5 m = 19 , dan 6 m = 14 . Selanjutnya, dihitung:
13
1 1 c = m b mod n = 10 mod55 = 10
13
2 2 c = m b mod n = 17 mod 55 = 7
13
3 3 c = m b mod n = 8 mod 55 = 28
13
4 4 c = m b mod n = 15 mod55 = 20
13
5 5 c = m b mod n = 19 mod 55 = 39
13
6 6 c = m b mod n = 14 mod 55 = 49
Jadi, cipherteksnya adalah 10-7-28-20-39-49.
Selanjutnya A mengirimkan cipherteks ini kepada B.
5. Dekripsi
Berikut ini adalah proses dekripsi RSA. Dilakukan oleh
pihak penerima cipherteks, yaitu B.
(1) Ambil kunci publik (n,b) dan kunci rahasia a.
(2) Hitung m = ca mod n .
Contoh 6. Setelah B memperoleh cipherteks dari A,
yaitu 10-7-28-20-39-49, maka diambil kunci rahasia
a = 37 , dan dilakukan perhitungan berikut.
37
1 1 m = c a mod n = 10 mod55 = 10
37
2 2 m = c a mod n = 7 mod55 = 17
37
3 3 m = c a mod n = 28 mod55 = 8
37
4 4 m = c a mod n = 20 mod55 = 15
37
5 5 m = c a mod n = 39 mod55 = 19
37
6 6 m = c a mod n = 49 mod55 = 14
Diperoleh plainteks 10-17-8-15-19-14, jika dikorespondensikan
sesuai Tabel 1, diperoleh pesan asli yang
dikirimkan oleh A, yaitu “kripto”.
6. Kesimpulan dan Saran
Algoritma kunci publik seperti sandi RSA, baik
digunakan untuk mengatasi masalah distribusi kunci, dan
apabila jalur komunikasi yang digunakan tidak aman.
Untuk menembus keamanan RSA, pihak
penyerang cukup hanya dengan memfaktorkan nilai n
menjadi p dan q yang sesuai dengan kunci publik. Untuk
memperkuat tingkat keamanan, sebaiknya digunakan
bilangan prima p dan q yang besar, oleh Stinson (2006)
dianjutran sebesar >80 digit, sehingga pihak penyerang
akan kesulitan dan membutuhkan waktu yang sangat
lama untuk memfaktorkan n, tidak sepadan dengan nilai
informasi yang dicari.
Daftar Pustaka
Buchmann, Johannes A., 2000, Introduction to
Cryptography, Springer-Verlag New York,
USA.
Fraleigh. 2000, A First Course in Abstract Algebra, Sixth
Edition, Addison-Wisley, USA.
Stinson, D.R., 2006, Cryptography Theory and Practice,
Third Edition, Chapman & Hall/CRC, USA.
Tidak ada komentar:
Posting Komentar