Algoritma RSA-CRT merupakan bentuk kombinasi dari algoritma RSA. Seperti yang sudah kita bahas pada contoh perhitungan algoritma RSA bahwa algoritma kunci-public yang satu ini termasuk ke dalam kategori algoritma kriptografi yang sangat populer dan banyak dipakai dalam pengamanan data di era modern karena ketahanan yang dimiliki algoritma ini cukup handal. Hal ini dikarenakan konsep ikatan antara kunci private dan kunci public yang unik dan sulit untuk dipecahkan. Namun begitu, algoritma RSA memiliki kelemahan yaitu saat bilangan yang akan didekripsikan memiliki pangkat yang tinggi, maka secara manual sulit untuk diperoleh hasil pemangkatannya. Disamping itu, jika diimplementasikan dalam bahasa pemrograman tertentu, hal ini juga akan memperlambat kerja program karena pemakaian memory yang cukup besar.

Karena bentuk kekurangan ini, maka algoritma RSA kerap disempurnakan dengan mengombinasikannya dengan teknik tertentu contohnya CRT atau singkatan dari Chinese Remainder Theorem. Dalam sebuah penelitian yang dilakukan pada tahun 2015 dinyatakan bahwa “Chinese Remainder Theorem dapat mengkonversi bilangan yang besar dari kunci dengan panjang eksponensiasi modular berukuran besar menjadi kunci yang lebih pendek dengan eksponensiasi modular berukuran yang relatif lebih kecil.”

Oleh karena kekurangan dari RSA dapat diselesaikan dengan CRT, maka banyak pengembang sistem menggunakan modifikasi algoritma RSA-CRT. Pada dasarnya CRT digunakan hanya saat mendekripsi pesan karena kebutuhan akan pengecilan pemangkatan ada pada saat dekripsi pesan. Namun, algoritma RSA-CRT memiliki skema sendiri yang memiliki penambahan dari algoritma RSA tanpa kombinasi CRT.

Tahapan Algoritma RSA-CRT

Pada dasarnya tahapan yang dilakukan dalam algoritma RSA yang dimodifikasi dengan CRT tidak jauh beda dengan algoritma RSA, hanya saja ada beberapa penambahan variabel yang dibutuhkan sehingga tahapan yang harus dilalui adalah sebagai berikut :

1. Proses Pembentukan Kunci Algoritma RSA-CRT

Proses yang dilakukan dalam algoritma ini memiliki beberapa tahap sebagai berikut :

Menentukan nilai p dan q

Sama halnya seperti algoritma RSA, kita dituntut untuk menentukan nilai p dan q seseuai keinginan namun nilai ini haruslah bilangan prima dan lebih baik jika besar agar sulit untuk dipecahkan nantinya. Contohnya pada kasus ini kita memilih pasangan angka sebagai berikut

• p = 137
• q = 131

Menghitung nilai n

Masih sama dengan algoritma RSA tunggal, nilai n adalah berkalian kedua buah bilangan prima p dan q :

• n = 137 x 131
• n = 17947

Menghitung nilai m

Adapun rumus dari mencari nilai m masih sama dengan algoritma RSA tanpa CRT yaitu sebagai berikut :

• m = (p – 1) x (q – 1)
• m = (137 – 1) x (131 – 1)
• m = 17680

Memilih e yang relatif prima dengan m

Memilih e yang relatif prima terhadap m dengan syarat memenuhi Greater Common Divisor (GCD) artinya faktor pembagi terbesar nilai e dan m adalah satu. Untuk menentukan nilai ini dipakai algoritma Euclidean seperti yang sudah pernah kita bahas pada artikel sebelumnya sebagai berikut:

• gcd⁡(e,m)=1
• gcd⁡(e,17680)=1
• Rumus Algoritma Euclidean

Percobaan pertama nilai e = 2

Dapat disimpulkan bahwa 2 bukanlah nilai e karena angka pada r terahir sebelum 0 tidak = 1 tetapi 2.

Percobaan ke 2 nilai e = 3

Dari perhitungan di atas dapat dilihat bahwa nilai r terahir sebelum 0 adalah 1, maka nilai e adalah 3.

• Jadi, e = 3

Menentukan nilai d

Untuk mendapatkan nilai d maka berlaku rumus sebagai berikut :

• e×d mod m=1

Ini artinya adalah e dikalikan dengan angka berapa yang jika e dan angka tersebut dikalikan hasilnya mod m didapat 1. Untuk perumusan mod dapat dilihat pada video tutorial berikut

• 3 × 11787 mod 17680=1
• d = 11787

Menentukan nilai dP

Nah, yang membedakan algrotima RSA dengan RSA yang dimodifikasi dengan CRT adalah pada penambahan nilai dP, dQ, dan qInv. adapun untuk menentukan nilai dP diberikan rumus sebagai berikut :

Menentukan nilai dQ

Untuk menentukan nilai dQ dapat dilakukan dengan menerapkan rumus sebagai berikut :

Menentukan nilai qInv

Terakhir, dicari nilai qInv dengan rumusan sebagai berikut :

• Artinya 114 ×131≡1 mod 137, sama dengan 114×131 mod 137=1

Kuci Public dan Kunci Private yang didapat

Dari proses yang telah dilalui di atas, maka didapatkan pasangan kunci public dan kunci private sebagai berikut :

• Kunci public = (e,n) yaitu (3, 17947)
• Kunci private = (dP, dQ, qInv, p, q) yaitu (91, 87, 114, 137, 131)

2. Enkripsi Pesan dengan Algoritma RSA-CRT

Pada dasarnya, proses enkripsi pesan dengan RSA tidak membutuhkan proses perhitungan dengan teori seperti CRT. Hal ini dikarenakan nilai pemangkatan eksponensial modulo yang diproses tidaklah besar. CRT hanya diperlukan untuk menurunkan nilai pemangkatan yang besar pada saat dekripsi pesan. Oleh karena itu, proses enkripsi disini dilakukan tanpa teori CRT.

Kunci public yang telah dihasilkan dari proses pembangkitan kunci akan dipakai untuk mengenkripsi pesan yaitu dalam hal ini contoh pesan adalah 1562 (dalam hal ini sengaja kita ambil contoh angka yang besar agar nanti saat dekripsi dapat kita lihat contoh pengecilan pemangkatannya yang besar)  sebagai berikut :

3. Dekripsi RSA dengan CRT

Seperti yang telah kita bahas, bahwa kelemahan RSA adalah saat dekripsi jika dilihat nilai pemangkatannya yang sangat besar, maka akan mustahil diperoleh hasilnya dalam waktu yang singkat karena pada penggunaan kalkulator saja akan mengalami error. Oleh karena itulah hal ini menyebabkan besarnya waktu yang dibutuhkan saat diimplementasi pada proses komputasi. Maka disinilah dibutuhkan modifikasi algoritma ini dengan CRT untuk menurunkan nilai eksponensialnya.

Namun sebelum dilakukan dekripsi pesan perlu beberapa hal sebagai berikut untuk dilakukan :

Memasukkan Nilai Cipherteks

Ciphertext yang akan dienkripsi adalah berupa hasil enkripsi yaitu “8825”

Menentukan Nilai m1

Adapun rumus dari m1 adalah sebagai berikut :

Jika dilihat, nilai pemangkatan masih terlihat besar. Untuk mencari nilai m1 ini maka dibuat proses sebagai berikut :

Mari kita ambil angka pangkatnya yaitu 91. Kemudian, carilah angka pembagi yang sesui, yaitu 3 karena :

• 91 jika dibagi 3 maka sisa 1. Maka :

• m1 = 55

Menentukan Nilai m2

Untuk menetukan nilai m2 maka dihitung dengan rumus sebagai berikut :

Sama seperti penentuan nilai m₁, nilai pemangkatannya tidak dapat diperoleh langsung, maka untuk menentukan nilai m₂ juga dilakukan proses sebagai berikut :

Ambillah angka pangkatnya yaitu 87, kemudian tentukan angka pembaginya yaitu disini 2 karena :

• 87 dibagi 2 akan sisa 1, maka :

• m2 = 121

Menentukan Nilai h

Adapun rumus untuk mencari nilai h adalah sebagai berikut :

• h=114(55-121+137) mod 137, (ditambahkan nilai p untuk menjaga agar tetap positif)

Hasil Dekripsi

Dengan didapatkan semua nilai m1, m2, dan h maka dapat diambil hasil dekripsi sebagai berikut :

Dengan hasil yang telah terlihat, didapatkan kembali plaintext awal yaitu 1562

Demikianlah untuk memecahkan nilai pemangkatan pada algoritma RSA maka digunakan teori CRT. Dari perhitungan di atas terlihat bahwa hasil pemangkatan besar berhasil didapatkan dan kembali kepada nilai plainteks awal.