TUGAS KRIPTOGRAFI

PENYANDIAN KUNCI ASIMETRIS

“RSA”

Disusun oleh :

Aditya Wiyanto ( M0508080 )

Ahmad Aniq N M ( M0508082 )

Andreas Dony M S ( M0508084 )

Program Studi Teknik Informatika

Fakultas Matematika dan Ilmu Pengetahuan Alam

UNIVERSITAS SEBELAS MARET

2010

RSA

1. Penjelasan Singkat

Sandi RSA merupakan algoritma kriptografi kunci public (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. Dasar Teori

a. Konsep Dasar Perhitungan Matematis

Fungsi Phi-Euler

Fungsi Phi-Euler φ(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

operasi pergandaan. Dengan kata lain, φ(n) adalah banyaknya elemen {x, 0 ≤

x < n | gcd(x,n) = 1}. Jika n = pq dengan p dan q adalah bilangan prima, maka

φ(n) = (p -1)(q -1). Jika n adalah bilangan prima, maka φ(n) = n -1.

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 dihitung

menggunakan algoritma pembagian :

r0 = q1r1 + r2, 0 < r2 < r1

r1 = q2r2 + r3, 0 < r3 < r2

...

rn-2 = qn-1rn-1 + rn, 0 < rn < rn-1

rn-1 = qnrn,

Dari pernyataan di atas, dapat ditunjukkan bahwa :

gcd(r0, r1) = gcd(r1, r2) = ... = gcd(rn-1, rn) = gcd(rn,0) = rn.

Contoh : Akan dihitung gcd(40 , 24)

Jawab :

75 = 1.24 + 16 n = 1, r1 = 24 , q1 = 1

24 = 1.16 + 8 n = 2, r2 = 16 , q2 = 1

16 = 2.8 n = 3, r3 = 8 , q3 = 2

Jadi, gcd(40 , 24) = 8

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 gcd(r0, r1) = 1, maka r1-1 mod r0 ada.

Jika gcd(r0, r1) ≠ 1, maka r1-1 mod r0 tidak ada. Gunakan rumus rekurensi

berikut ini.

t0 = 0, t1 = 0

tj = tj-2 - qj-1tj-1, j ≥ 2 ....................... (1)

Ket : qj diperoleh dari perhitungan gcd(r0, r1) menggunakan algoritma Euclide.

Jika gcd(r0, r1) = 1, berarti r1-1 = tn. Sehingga rn = tnr1 atau 1 = tnr1.

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 :

g2i+1

=(g2i )2

Untuk lebih jelasnya mengenai langkah-langkah metode fast exponentiation,

perhatikan contoh berikut ini.

Contoh : Akan dihitung 673 mod 100.

Jawab :

73 = 1.26 + 1.23 + 1.20 atau 73 = (1001001)2.

(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 mod 100 = 16.

b. Pembentukan / Pembangkitan 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 φ(n) = ( p -1)(q -1) .

(4) Pilih sebarang bilangan b, 1 < b < φ(n), dengan gcd(b , φ(n)) = 1.

(5) Hitung invers dari b, yaitu a = b-1 mod φ(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 .

Gambar 2. Tabel Korespondensi

c. 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.

d. 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 .

3. Penerapan dan Penyelesaian

Dalam bagian ini akan dilakukan penerapan dari langkah-langkah algoritma RSA di

atas dengan contoh soal : A ingin mengirimkan pesan kepada B. Misalkan plaintext-

nya “KRIPTO” dengan memilih bilangan prima p = 5 dan q = 11, sehingga n = 55

dan φ(55) = (5 -1)(11-1) = 4.10 = 40. Berikut ini adalah langkah-langkah

penyelesaiannya :

a. Pendefinisian / Pembangkitan Kunci

B memilih sembarang bilangan b, 1 < b < φ(n), dengan gcd(b , φ(n)) = 1. Dalam

hal ini diambil b = 13 dengan syarat gcd(b , φ(n)) = gcd(13 , 40) = 1. Bila belum

memenuhi syarat maka dicari nilai b lainnya dengan batas 1 < b < 40. Berikut

langkah pembuktian syaratnya :

40 = 3.13 + 1 n = 1, r1 = 13 , q1 = 3

13 = 13.1 n = 2, r2 = 1 , q2 = 13

Jadi, gcd(40 , 13) = 1

Karena gcd(40 , 13) = 1, maka invers-nya / a = b-1 mod φ(n) = 13-1 mod 40 ada

atau memiliki nilai. Berikut perhitungannya :

t0 = 0, t1 = 1

t2 = t0 – q1t1 = 0 - 3.1 = -3 = 37

t3 = t1 – q2t2 = 1 - 13.(-3) = 38]

Diambil r2 sebagai acuan karena memiliki nilai 1

r2 = t2r1 = 37.13 mod 40 = 1 ↔ 37 = 13-1

Dari hasil terakhir di atas, diperoleh 13-1 mod 40 = 37.

Sehingga di dapat kunci public dan kunci private-nya, yaitu :

Kunci Public → (n,b) = (55,13) → (dikirimkan ke A)

Kunci Private → (n,a) = (55,37) / a = 37 → (disimpan oleh B)

b. Enkripsi

Sebelum dilakukan enkripsi ubah plainteks dalam bentuk angka sesuai dengan

tabel korespondensi sebelumnya, berikut pengubahannya :

Plain : K R I P T O

Angka: 10 17 8 15 19 14

m1 m2 m3 m4 m5 m6

Selanjutnya dilakukan perhitungan c = mb mod n oleh A dengan kunci public

yang telah dibangkitkan B pada tiap plaintext m dengan cara metode fast

exponentiation :

c1 = m1b mod n = 1013 mod 55 = 10

Cara perhitungan :

13 = 1.23 + 1.22 + 1.20 atau 13 = (1101)2.

(semua perhitungan dilakukan dalam mod 55)

1020

= 10, 1021

= 45, 1022

= 452 = 45, 1023

= 45,

Sehingga diperoleh:

1013 = 10 . 1022

. 1023

= 10 . 45 . 45 = 10.

Jadi, 1013 mod 55 = 10.

Cara itu berlaku untuk plaintext lainnya sehingga didapat hasilnya :

c2 = m2b mod n = 1713 mod 55 = 7

c3 = m3b mod n = 813 mod 55 = 28

c4 = m4b mod n = 1513 mod 55 = 20

c5 = m5b mod n = 1913 mod 55 = 39

c6 = m6b mod n = 1413 mod 55 = 49

Sehingga, didapatkan cipherteksnya adalah 10-7-28-20-39-49. Selanjutnya A

mengirimkan cipherteks ini kepada B untuk di-dekripsi.

c. Dekripsi

Setelah B memperoleh cipherteks dari A, yaitu 10-7-28-20-39-49, maka diambil

kunci rahasia a = 37 untuk di-dekripsi menggunakan perhitungan m = ca mod n

pada tiap ciphertext m dengan cara metode fast exponentiation :

m1 = c1a mod n = 1037 mod 55 = 10

m2 = c2a mod n = 737 mod 55 = 17

m3 = c3a mod n = 2837 mod 55 = 8

m4 = c4a mod n = 2037 mod 55 = 15

m5 = c5a mod n = 3937 mod 55 = 19

m6 = c6a mod n = 4937 mod 55 = 14

Diperoleh plainteks 10-17-8-15-19-14, kemudian dilakukan korespondensi ke

dalam bentuk abjad dengan table korespondensi sebelumnya :

m1 m2 m3 m4 m5 m6

Angka: 10 17 8 15 19 14

Plain : K R I P T O

Dari hasil korespondesi di atas didapat hasil dekripsinya sama dengan plaintext

sebelumnya yaitu ”KRIPTO”.

4. Kesimpulan

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 / dipilih bilangan

prima p dan q yang besar, sehingga pihak penyerang akan kesulitan dan

membutuhkan waktu yang sangat lama untuk memfaktorkan n, dan tidak

sepadan dengan nilai informasi yang dicari.