Kumpulan Contoh Soal Algoritma RSA Lengkap dengan Pembahasan

Di era digital yang serba terkoneksi ini, keamanan data menjadi prioritas utama. Salah satu metode enkripsi yang paling banyak digunakan di seluruh dunia adalah Algoritma RSA. Dikembangkan oleh Ron Rivest, Adi Shamir, dan Leonard Adleman pada tahun 1977, RSA merupakan algoritma kriptografi asimetris pertama yang cocok untuk enkripsi sekaligus tanda tangan digital.

Bagi mahasiswa teknik informatika, praktisi keamanan siber, maupun antusias kriptografi, memahami cara kerja RSA melalui latihan soal adalah langkah krusial. Artikel ini menyajikan kumpulan contoh soal algoritma RSA mulai dari tingkat dasar hingga penerapan angka besar, lengkap dengan pembahasan langkah demi langkah menggunakan prinsip matematika yang presisi.

Baca juga:Panduan Mudah VLOOKUP di Excel dengan Contoh Soal

Memahami Cara Kerja Algoritma RSA

Sebelum masuk ke contoh soal, mari kita bedah dasar matematika di balik RSA. RSA mengandalkan kesulitan faktorisasi dua bilangan prima besar. Prosesnya dibagi menjadi tiga tahap utama:

1. Pembangkitan Kunci (Key Generation)

1. Pilih dua bilangan prima berbeda, $p$ dan $q$.
2. Hitung $n = p \times q$. Nilai $n$ digunakan sebagai modulus untuk kunci publik dan pribadi.
3. Hitung fungsi totien Euler: $\phi(n) = (p – 1) \times (q – 1)$.
4. Pilih sebuah bilangan bulat $e$ (kunci publik) sedemikian sehingga $1 < e < \phi(n)$ dan $e$ relatif prima terhadap $\phi(n)$ (artinya $FPB(e, \phi(n)) = 1$).
5. Hitung $d$ (kunci pribadi) sebagai invers multiplikatif modular dari $e$ modulo $\phi(n)$. Secara matematis: $d \equiv e^{-1} \pmod{\phi(n)}$ atau $(d \times e) \pmod{\phi(n)} = 1$.

2. Enkripsi (Encryption)

Pesan (Plaintext) $M$ diubah menjadi Ciphertext $C$ menggunakan kunci publik $(e, n)$:

$$C = M^e \pmod n$$

3. Dekripsi (Decryption)

Ciphertext $C$ dikembalikan menjadi Pesan asli $M$ menggunakan kunci pribadi $(d, n)$:

$$M = C^d \pmod n$$

Kumpulan Contoh Soal Algoritma RSA dan Pembahasannya

Contoh Soal 1: Dasar Pembangkitan Kunci

Soal:

Tentukan kunci publik dan kunci pribadi jika diketahui bilangan prima $p = 3$ dan $q = 11$, dengan kunci publik $e = 3$.

Pembahasan:

1. Hitung n:$n = p \times q = 3 \times 11 = 33$
2. Hitung $\phi(n)$:$\phi(n) = (p – 1)(q – 1) = (2)(10) = 20$
3. Validasi e:$e = 3$. Cek apakah $FPB(3, 20) = 1$. Karena ya, maka $e=3$ valid.
4. Hitung d:Kita harus mencari $d$ sehingga $(d \times 3) \pmod{20} = 1$.
   • Jika $d = 7 \rightarrow 7 \times 3 = 21$.
   • $21 \pmod{20} = 1$.Maka, $d = 7$.

Hasil:

• Kunci Publik: $(e=3, n=33)$
• Kunci Pribadi: $(d=7, n=33)$

Contoh Soal 2: Proses Enkripsi dan Dekripsi Sederhana

Soal:

Menggunakan kunci dari Soal 1 ($e=3, d=7, n=33$), enkripsikan pesan $M = 5$, kemudian buktikan dengan proses dekripsi.

Pembahasan:

1. Enkripsi:$$C = M^e \pmod n$$$$C = 5^3 \pmod{33}$$$$C = 125 \pmod{33}$$$125 = (33 \times 3) + 26$. Maka, $C = 26$.
2. Dekripsi:$$M = C^d \pmod n$$$$M = 26^7 \pmod{33}$$Untuk menghitung $26^7 \pmod{33}$, kita gunakan metode Modular Exponentiation:
   • $26^1 \equiv 26 \equiv -7 \pmod{33}$
   • $26^2 \equiv (-7)^2 \equiv 49 \equiv 16 \pmod{33}$
   • $26^4 \equiv 16^2 \equiv 256 \equiv 25 \pmod{33} \equiv -8 \pmod{33}$
   • $26^7 = 26^4 \times 26^2 \times 26^1$
   • $26^7 \equiv (-8) \times 16 \times (-7) \pmod{33}$
   • $26^7 \equiv 896 \pmod{33}$$896 \div 33 = 27$ sisa $5$.Maka, $M = 5$.

Hasil:

Pesan berhasil dikembalikan menjadi 5.

Contoh Soal 3: Mencari Kunci Pribadi dengan Algoritma Euclidean

Soal:

Jika $p = 61, q = 53$, dan $e = 17$, hitunglah nilai kunci pribadi $d$.

Pembahasan:

1. Hitung n: $n = 61 \times 53 = 3233$
2. Hitung $\phi(n)$: $\phi(n) = 60 \times 52 = 3120$
3. Mencari d dengan Algoritma Euclidean Terluas (Extended Euclidean Algorithm):Kita mencari $d$ untuk $17d \equiv 1 \pmod{3120}$.
   • $3120 = 183 \times 17 + 9$
   • $17 = 1 \times 9 + 8$
   • $9 = 1 \times 8 + 1$ (Sisa 1 tercapai)
   Bekerja mundur:
   • $1 = 9 – 1 \times 8$
   • $1 = 9 – 1 \times (17 – 1 \times 9) = 2 \times 9 – 1 \times 17$
   • $1 = 2 \times (3120 – 183 \times 17) – 1 \times 17$
   • $1 = 2 \times 3120 – 366 \times 17 – 1 \times 17$
   • $1 = 2 \times 3120 – 367 \times 17$
   Maka, $d = -367$. Karena hasil negatif, tambahkan dengan $\phi(n)$:$d = -367 + 3120 = 2753$.

Hasil:

Kunci pribadi $d = 2753$.

Contoh Soal 4: Analisis Keamanan RSA

Soal:

Seorang peretas menemukan kunci publik RSA adalah $(e=13, n=77)$. Berapakah kunci pribadinya?

Pembahasan:

1. Faktorisasi n:$n = 77$. Bilangan prima yang menghasilkan 77 adalah $p=7$ dan $q=11$.
2. Hitung $\phi(n)$:$\phi(77) = (7-1)(11-1) = 6 \times 10 = 60$.
3. Hitung d:$13d \equiv 1 \pmod{60}$.
   • Jika $d=37 \rightarrow 13 \times 37 = 481$.
   • $481 \pmod{60} = 1$ (karena $60 \times 8 = 480$).

Hasil:

Kunci pribadi adalah 37. Ini menunjukkan mengapa dalam praktik nyata, $n$ harus sangat besar (misal 2048-bit) agar tidak mudah difaktorkan.

Tips Mengerjakan Soal RSA

Agar tidak terjadi kesalahan dalam perhitungan, perhatikan tips berikut:

• Ketelitian pada $\phi(n)$: Jangan tertukar antara $n$ dan $\phi(n)$ saat mencari nilai $d$. Nilai $d$ selalu dihitung terhadap $\phi(n)$.
• Gunakan Sifat Modulo: Saat menghitung pangkat besar, gunakan sifat $(A \times B) \pmod n = [(A \pmod n) \times (B \pmod n)] \pmod n$.
• Pengecekan FPB: Selalu pastikan $e$ dan $\phi(n)$ adalah coprime. Jika tidak, dekripsi tidak akan menghasilkan pesan yang benar.

Baca juga:CoE Smart Agriculture Universitas Teknokrat Indonesia Kenalkan Irigasi Tetes Berbasis IoT di SMK Gajah Mada

Kesimpulan

Algoritma RSA adalah perpaduan indah antara teori bilangan dan keamanan informasi. Melalui kumpulan contoh soal di atas, kita dapat melihat bahwa meskipun konsepnya sederhana—hanya melibatkan perkalian dan perpangkatan modular—kekuatannya terletak pada kerumitan faktorisasi angka besar.

Bagi Anda yang sedang mempersiapkan ujian atau proyek kriptografi, menguasai perhitungan manual seperti di atas akan memberikan fondasi yang kuat sebelum beralih ke implementasi menggunakan bahasa pemrograman seperti Python atau Java.

Penulis:kiara salsabilla