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. 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 q_i, r_i ϵ Z sehingga :

Jadi r_m+1 = gcd(r_m, r_m+1) = gcd(r_m-1, r_m) = gcd(r_m-2, r_m-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 q_j hasil algoritma Euclidean dan pendefinisian t_j dan s_j diperoleh hubungan r_j, t_j, dan s_j yang diberikan oleh :

Teorema :

Jika j = 0, 1, 2, …, m maka r_j = s_ja + t_jb dengan t_j dan s_j seperti yang didefinisikan dan r_j diperoleh di Algoritma Euclidean.
Akibat :
Jika gcd (a, b) = 1, maka b^-1 = t_j

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 :

t₀ = 0
t₁ = 1
t₂ = t₀ – q₁t₁ = 0 – 4 × 1 = -4
t₃ = t₁ – q₂t₂ = 1 – 2 × (-4) = 9
t₄ = t₂ – q₃t₃ = -4 – 3 × 9 = -31
t₅ = t₃ – q₄t₄ = 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 :

17 ≡ 2 (mod 3)
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)

Teorema :

1. Jika a ≡ b (mod m) dan c adalah sembarang bilangan bulat positif maka
• ( a + c) ≡ (b + c) (mod m)
• ac ≡ bc (mod m)
• a^p ≡ b^p (mod m) untuk suatu bilangan bulat tak negative p.
2. 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 43

Karena tidak ada p yang dapat membagi habis n, maka n bukanlah bilangan komposit. Sehingga 1993 adalah bilangan prima. 

2. n = 121

121 = 11

p ≤ 11 = 2, 3, 5, 7, dan 11

7

Karena 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}
ϕ(8) = 4, karena yang memiliki invers hanya 1, 3, 5, 7.

Teorema (untuk mencari ϕ(n)) :

Diberikan n = =1 dengan pi bilangan prima, m banyaknya bilangan prima, ei > 0,

0 < i < m, maka ϕ(n) = 
Contoh :

n = 8
m = 1, p1 = 2, e1 = 3
ϕ(8) = (23 - 22) = 8 – 4 = 4

Teorema 1 :
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 a^p ≡ b^p (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 :

E_e(m) = m^e (mod n) = cD_d(c) = c^d (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 :

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 (d)

2. Algoritma Enkripsi dan Dekripsi

Algoritma enkripsi pada RSA adalah sebagai berikut :

1. Ambil kunci public milik penerima pesan (n dan e).
2. Pecah plainteks menjadi blok-blok m₁, m₂, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam selang [0, n-1].
3. Setiap blok mi dienkripsi menjadi blok c_i dengan rumus c_i = m_i^e mod n

Untuk mendapatkan plainteks kembali, blok cipherteks ci didekripsi menjadi blok m_i dengan rumus m_i = c_i^d 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:

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 : c^d mod n menghasilkan kompleksitas yang besar.

Pihak pengembang RSA menyarankan untuk menggunakan nilai desimal diatas 100 untuk nilai p dan q, sehingga menghasilkan key space yang besar pula (mencapai 300 angka desimal). Berikut adalah tabel gambaran waktu untuk menemukan nilai faktorial dari n dalam satuan MIPS (Million Instructions Per Second).

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 terhadapat 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 adalah

E({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 = M^e mod n sebagai berikut :

misal: x = (C x 2^e) mod n 

dari x diatas, kita dapat menemukan plainteks sebagai berikut :

x = (C mod n) x (2^e mod n)
  = (M^e mod n) x (2^e mod n)
  = (2M)^e mod n 

Untuk itu, dala praktiknya, sebelum dilakukan enkripsi terhadap sebuah pesan, RSA melakukan kombinas padding dan hashing pada pesan seperti yang diperlihatkan pada gambar di bawah, sehingga persamaan di atas tidak terpenuhi.

Kelebihan dan Kelemahan 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.

Kesimpulan

RSA merupakan metode penyandian yang masih kokoh untuk mengatasi masalah keamanan dalam pengiriman data pada suatu jaringan pada media elektronik. Dari segi teknis penghitungan, system RSA mempunyai cara enkripsi yang mudah, tetapi jika sudah dienkripsi, data yang terenkripsi sulit untuk dibobol jika hanya mempunyai kunci publiknya saja. Dalam proses pembuatan kunci publik dan kunci privat, terdapat beberapa faktor yang menjadi pertimbangan, yaitu ukuran dari kunci, penentuan nilai p dan q agar sulit untuk dibobol, dan kemungkinan-kemungkinan kelemahan yang dapat diketahui saat data selesai dienkripsi. Pada kehidupan sehari-hari, aplikasi sisten RSA dapat ditemukan pada system autentikasi data dan pembuatan tanda tangan digital pada komputer, pada tingkat perangkat keras, RSA banyak digunakan pada telepon yang mempunyai system pengaman dari penyadapan, kartu jaringan ethernet, dan pada kartu cerdas. RSA juga dimasukkan ke dalam protokol internet yang mempunyai sistem pengaman, seperti S-HTTP, S/MIME dan lain-lain.