KRIPTOGRAFI KUNCI PUBLIK: SANDI RSA

Kriptografi Kunci Publik: Sandi RSA

KRIPTOGRAFI KUNCI PUBLIK: SANDI RSA Oleh: Muhamad Zaki Riyanto ([email protected]) Ardhi Ardhian ([email protected])

1. Sandi RSA 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. Kunci Publik Plainteks A

Plainteks

cipherteks

dihitung menggunakan algoritma pembagian: r0 = q1r1 + r2 , 0 < r2 < r1

r1 = q2 r2 + r3 ,

0 < r3 < r2

... rn − 2 = qn −1rn −1 + rn , 0 < rn < rn −1

rn −1 = qn rn Dari pernyataan di atas, dapat ditunjukkan bahwa gcd(r0 , r1 ) = gcd(r1 , r2 ) = ... = gcd(rn −1 , rn ) = gcd(rn , 0) = rn . Bukti lihat di (Buchmann, 2000)

Kunci Rahasia

enkripsi

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 r0 dan r1 , dengan r0 ≥ r1 , kemudian

dekripsi

B

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.

Contoh 1. Akan dihitung gcd(40,24). Jawab: 40 = 1.24 + 16 24 = 1.16 + 8 16 = 2.8 Jadi, gcd(40,24)=8.

merupakan fungsi terhadap

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 r0 dan r1 , r0 > r1 . Jika

bilangan bulat positif n yang menyatakan banyaknya elemen ℤ n yang mempunyai invers terhadap operasi

maka r1−1 mod r0 tidak ada. Gunakan rumus rekurensi

2. Konsep Dasar Perhitungan Matematis 2.1. Fungsi Phi-Euler Fungsi Phi-Euler ϕ (n)

pergandaan. Ingat bahwa ℤ n belum tentu merupakan grup terhadap operai pergandaan. Dengan kata lain, ϕ (n) adalah banyaknya elemen

gcd ( r0 , r1 ) = 1 , maka r1−1 mod r0 ada. Jika gcd ( r0 , r1 ) ≠ 1 , berikut ini. t0 = 0 , t1 = 1

t j = t j − 2 − q j −1t j −1 , j ≥ 2 ....................... (1)

{ x, 0 ≤ x < n | gcd( x, n) = 1} .

gcd ( r0 , r1 )

Jika n = pq dengan p dan q adalah bilangan prima, maka

Ket:

ϕ (n) = ( p − 1)(q − 1) . Jika n adalah bilangan prima, maka

menggunakan algoritma Euclide. Jika gcd ( r0 , r1 ) = 1 ,

ϕ (n) = n − 1 . Bukti pernyataan di atas dapat dilihat di

berarti r1−1 = tn . Sehingga rn = tn r1 atau 1 = tn r1 . Bukti

(Fraleigh, 2000), (Buchmann, 2000), dan (Stinson, 2006).

bisa dilihat di (Stinson, 2006).

qj

diperoleh

dari

perhitungan

1 Copyright © Kelompok Studi Sandi dan Matematika | Yogyakarta, 30 Agustus 2008 http://sandimath.web.id


Contoh 2. Akan dihitung 28−1 mod 75 .

3. Pembentukan Kunci

Diketahui r0 = 75 dan r1 = 28 . Hitung gcd(75, 28)

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 .

menggunakan algoritma Euclide, yaitu: 75 = 2.28 + 19 n = 1, r1 = 28 , q1 = 2 28 = 2.19 + 9

n = 2, r2 = 19 , q2 = 2

19 = 2.9 + 1

n = 3, r3 = 9 ,

q3 = 2

9 = 9.1

n = 4, r4 = 1 ,

q4 = 9

(3) Hitung ϕ (n) = ( p − 1)(q − 1) . (4) Pilih sebarang bilangan b, 1 < b < ϕ (n) , dengan

gcd(b, ϕ (n)) = 1 .

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) t2 = t0 − q1t1 = 0 − 2.1 = −2 = 73

t3 = t1 − q2 t2 = 1 − 1.(−2) = 3 t4 = t2 − q3t3 = −2 − 2.3 = −8 = 67 r4 = t4 r1 = 67.28 = 1 ⇔ 67 = 28−1 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:

( ).

i +1

g2 = g2

i

73 = 1.2 + 1.2 + 1.2 atau 73 = (1001001)2 . 0

(semua perhitungan dilakukan dalam mod 100)

6 2 = 6 , 6 2 = 36 , 6 2 = 36 2 = 96 , 6 2 = 16 , 0

1

2

3

6 2 = 162 = 56 , 6 2 = 562 = 36 , 6 2 = 562 = 96 . Sehingga diperoleh: 4

5

6

673 = 6.62 .62 = 6.16.96 = 16 . 3

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 ϕ (55) = (5 − 1)(11 − 1) = 4.10 = 40 . Selanjutnya dapat

Contoh 3. Akan dihitung 673 mod100 . Jawab. 3

(6) Kunci publik: (n, b) dan kunci rahasia: a.

2

Untuk lebih jelasnya mengenai langkah-langkah metode fast exponentiation, perhatikan contoh berikut ini.

6

(5) Hitung invers dari b, yaitu a = b −1 mod ϕ (n) .

6

Jadi, 673 mod100 = 16. Setelah mempelajari konsep-konsep dasar perhitungan matematis, berikut ini diberikan prosesproses yang digunakan RSA.

dipilih b = 13 , sebab gcd(13, 40) = 1 . Menggunakan algoritma

Euclide

diperluas

diperoleh

bahwa

−1

a = 13 mod 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.



Contoh 5. A menerima kunci publik (n, b) = (55,13) dari

m5 = c5a mod n = 3937 mod 55 = 19

B. Misalkan plainteksnya adalah “kripto”, menggunakan Tabel 1 diperoleh m1 = 10 , m2 = 17 , m3 = 8 , m4 = 15 ,

m6 = c6 a mod n = 4937 mod 55 = 14

m5 = 19 , dan m6 = 14 . Selanjutnya, dihitung: c1 = m1b mod n = 1013 mod 55 = 10 c2 = m2b mod n = 1713 mod 55 = 7 c3 = m3b mod n = 813 mod 55 = 28 c4 = m4 mod n = 15 mod 55 = 20 b

13

c5 = m5b mod n = 1913 mod 55 = 39 c6 = m6b mod n = 1413 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.

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.

(2) Hitung m = c a mod n .

Daftar Pustaka 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.

m1 = c1a mod n = 1037 mod 55 = 10 m2 = c2 a mod n = 7 37 mod 55 = 17 m3 = c3a mod n = 2837 mod 55 = 8 m4 = c4 mod n = 20 mod 55 = 15 a

37

Buchmann, Johannes Cryptography, USA.

A., 2000, Introduction to Springer-Verlag New York,

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.



Soal Latihan 1: A ingin mengirimkan sebuah pesan rahasia “helo” kepada B. Karena jalur komunikasi tidak aman, maka keduanya sepakat untuk menggunakan sistem kriptografi kunci publik, dan dipilih sandi RSA. Proses pertama, B membuat pasangan kunci terlebih dahulu. B memilih bilangan prima p = 3 dan q = 17 .

2. Proses Enkripsi (dilakukan oleh A) a) Ubah pesan “helo” ke dalam bilangan (Tabel 1). “h” m1 = ..... “e” m2 = ..... “l” m3 = ..... “o” m4 = ..... b) Hitung:

1. Pembentukan Kunci (dilakukan oleh B) a) Hitung n = pq = ........................... b) Hitung ϕ (n) = ............................... c)

Misalkan B akan memilih b = 6 atau b = 9 . Nilai b manakah yang bisa digunakan sebagai kunci? Cek kedua nilai b menggunakan algoritma Euclide. Gunakan nilai b yang memenuhi gcd(ϕ (n), b) = 1 .

Jawab: Untuk b = 6. .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... Untuk b = 9. .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... Jadi, nilai b yang digunakan adalah b = ...... d) Tentukan

nilai

a = b −1 mod ϕ (n) = .....mod ϕ (n) .

menggunakan Extended Euclidian Algorithm. Jawab: .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... e)

Diperoleh pasangan kunci dari B, yaitu: Kunci publik: (n, b) = (......... , .........) Kunci rahasia: a = ...............

c1 = m1b mod n = ....................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... ....................................................................................

c2 = m2 b mod n = ...................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... ....................................................................................

c3 = m3b mod n = ....................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... ....................................................................................

c4 = m4 b mod n = ....................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... Diperoleh cipherteks: c1 − c2 − c3 − c4 = .......... - .......... - .......... - .........



3. Proses Dekripsi (dilakukan oleh B) a) Diketahui kunci rahasia a = .............

m1 = c1a mod n = ....................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... ....................................................................................

m2 = c2 a mod n = ..................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... ....................................................................................

m3 = c3 a mod n = ...................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... ....................................................................................

m4 = c4 a mod n = ..................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... .................................................................................... b) Konversi ke dalam huruf sesuai Tabel 1. m1 = ........, m2 = ........, m3 = ........, m4 = ........

Soal Latihan 2: 1) Hitung nilai pembagi persekutuan terbesar berikut ini menggunakan algoritma Euclide. a. gcd(87,36) b.

gcd(188, 72)

c.

gcd(435,125)

2) Tentukan nilai invers berikut ini menggunakan Extended Euclidean Algorithm. a.

17 −1 mod101

b.

23−1 mod151

c.

357 −1 mod1234

3) Hitung hasil dari pemangkatan besar modulo berikut ini menggunakan metode Fast Exponentation. a.

2 25 mod 25

b.

434 mod 30

c.

10 43 mod 75

4) Jika dipilih bilangan prima p = 23 dan q = 37 , apakah b = 143 bisa digunakan sebagai kunci? 5) Diberikan bilangan prima p dan q seperti soal 4) di atas, dipilih b = 67 . Apakah nilai p, q, dan b di atas dapat digunakan untuk proses pembentukan kunci? Jika ya, tentukan kunci publik dan kunci rahasianya. 6) Diberikan kunci publik (n, b) = (253,3) . Tentukan hasil enkripsi plainteks m = 165. 7) Menggunakan kunci publik soal 6) di atas dan kunci rahasia a = 147, tentukan hasil dekripsi cipherteks c = 78 . (hint. hasilnya adalah plainteks m, dimana m adalah hasil kuadrat suatu bilangan genap) 8) Buktikan bahwa plainteks m dapat diperoleh dari perhitungan c a mod n . 9) Hitunglah nilai fungsi Phi-Euler ϕ (n) untuk n = 9, 26, 29, dan 50. 10) Buktikan bahwa jika n adalah bilangan prima, maka ϕ ( n) = n − 1 .

Jadi, pesan yang dikirimkan A adalah ......................


KRIPTOGRAFI KUNCI PUBLIK: SANDI RSA

Recommend Documents