Panduan Memahami Algoritma RSA: Contoh Soal dan Cara Penyelesaiannya

Algoritma RSA merupakan salah satu sistem kriptografi kunci publik yang paling populer dan banyak digunakan dalam keamanan data digital. Algoritma ini ditemukan oleh Ron Rivest, Adi Shamir, dan Leonard Adleman pada tahun 1977. RSA digunakan untuk mengenkripsi pesan sehingga hanya penerima yang memiliki kunci privat dapat membaca pesan tersebut. Selain itu, RSA juga digunakan dalam tanda tangan digital untuk memastikan integritas data.

Bagi pelajar, mahasiswa, maupun praktisi teknologi informasi, memahami algoritma RSA dan cara menyelesaikan soal terkait sangat penting. Artikel ini akan membahas panduan memahami algoritma RSA, langkah-langkah perhitungannya, serta contoh soal beserta penyelesaiannya secara step by step. Dengan panduan ini, pembaca dapat belajar RSA dari dasar hingga tingkat menengah dengan mudah.

Baca juga:Latihan Soal VLOOKUP Excel untuk Pemula hingga Mahir

1. Pengertian Algoritma RSA

RSA adalah algoritma kriptografi kunci publik yang menggunakan dua kunci: kunci publik (public key) untuk mengenkripsi pesan dan kunci privat (private key) untuk mendekripsi pesan. Keamanan RSA didasarkan pada kesulitan faktorisasi bilangan besar menjadi faktor prima.

Keunggulan RSA:

1. Memungkinkan komunikasi aman tanpa berbagi kunci rahasia sebelumnya.
2. Dapat digunakan untuk enkripsi dan tanda tangan digital.
3. Aman jika menggunakan bilangan prima yang cukup besar.

2. Konsep Dasar Algoritma RSA

Langkah-langkah dasar dalam algoritma RSA adalah sebagai berikut:

1. Pilih dua bilangan prima besar p dan q.
2. Hitung n = p × q, yang menjadi modulus RSA.
3. Hitung totien Euler φ(n) = (p − 1) × (q − 1).
4. Pilih bilangan e (1 < e < φ(n)) yang relatif prima dengan φ(n). e menjadi kunci publik.
5. Hitung bilangan d sebagai invers modular dari e modulo φ(n). d menjadi kunci privat.
6. Enkripsi: Jika pesan m, maka ciphertext c = m^e mod n.
7. Dekripsi: Jika ciphertext c, maka m = c^d mod n.

3. Contoh Soal RSA dan Cara Penyelesaiannya Step by Step

Soal 1: Membuat Kunci RSA Sederhana

Pilih bilangan prima p = 7 dan q = 11. Tentukan kunci publik dan kunci privat.

Penyelesaian:

1. Hitung n:
   n = p × q = 7 × 11 = 77
2. Hitung totien Euler φ(n):
   φ(n) = (p − 1)(q − 1) = (7 − 1)(11 − 1) = 6 × 10 = 60
3. Pilih bilangan e yang relatif prima dengan φ(n), misal e = 7.
4. Hitung d, invers modular dari e modulo φ(n):
   d × e ≡ 1 mod 60 → d × 7 ≡ 1 mod 60

Uji nilai d:
7 × 43 = 301 → 301 mod 60 = 1 ✅

Jadi, d = 43

5. Kunci publik: (n, e) = (77, 7)
6. Kunci privat: (n, d) = (77, 43)

Soal 2: Enkripsi Pesan dengan RSA

Gunakan kunci publik dari soal sebelumnya (n = 77, e = 7). Enkripsilah pesan m = 20.

Penyelesaian:

Ciphertext c = m^e mod n = 20^7 mod 77

Langkah perhitungan:

1. Hitung pangkat bertahap modulo 77:

• 20^2 mod 77 = 400 mod 77 → 400 ÷ 77 = 5 sisa 15 → 20^2 mod 77 = 15
• 20^4 = (20^2)^2 → 15^2 = 225 → 225 mod 77 = 225 − 154 = 71
• 20^7 = 20^4 × 20^2 × 20^1 mod 77 = 71 × 15 × 20 mod 77

Hitung bertahap:
71 × 15 = 1065 → 1065 mod 77
77 × 13 = 1001 → 1065 − 1001 = 64

64 × 20 = 1280 → 1280 mod 77
77 × 16 = 1232 → 1280 − 1232 = 48

Jadi, c = 48

Jawaban: Ciphertext = 48

Soal 3: Dekripsi Pesan RSA

Gunakan ciphertext c = 48 dan kunci privat (n = 77, d = 43). Tentukan pesan asli m.

Penyelesaian:

m = c^d mod n = 48^43 mod 77

Hitung dengan metode pangkat modular (lebih efisien menggunakan faktorisasi biner).

1. Representasikan 43 dalam biner: 43 = 32 + 8 + 2 + 1 = 101011
2. Hitung pangkat bertahap modulo 77:

• 48^1 mod 77 = 48
• 48^2 = 48^2 mod 77 = 2304 mod 77 → 2304 − (77 × 29 = 2233) → 2304 − 2233 = 71
• 48^4 = 71^2 = 5041 mod 77 → 5041 − (77 × 65 = 5005) → 5041 − 5005 = 36
• 48^8 = 36^2 = 1296 → 1296 − (77 × 16 = 1232) → 1296 − 1232 = 64
• 48^16 = 64^2 = 4096 → 4096 − (77 × 53 = 4081) → 4096 − 4081 = 15
• 48^32 = 15^2 = 225 → 225 − (77 × 2 = 154) → 225 − 154 = 71

Gabungkan pangkat biner: 32 + 8 + 2 + 1 → 48^32 × 48^8 × 48^2 × 48^1 mod 77

Hitung bertahap:

• 48^32 × 48^8 = 71 × 64 = 4544 → 4544 mod 77
  77 × 59 = 4543 → 4544 − 4543 = 1
• 1 × 48^2 = 1 × 71 = 71
• 71 × 48^1 = 71 × 48 = 3408 → 3408 mod 77
  77 × 44 = 3388 → 3408 − 3388 = 20

Jadi, pesan asli m = 20 ✅

Soal 4: Menentukan Kunci Publik dari Kunci Privat

Jika diketahui kunci privat (n = 77, d = 43) dan p = 7, q = 11, tentukan kunci publik (n, e).

Penyelesaian:

1. Hitung totien Euler: φ(n) = (p − 1)(q − 1) = 6 × 10 = 60
2. Diketahui d × e ≡ 1 mod φ(n) → 43 × e ≡ 1 mod 60
3. Tentukan e: 43 × 7 = 301 → 301 mod 60 = 1 ✅
4. Jadi, kunci publik: (77, 7)

Soal 5: Enkripsi Pesan dengan RSA Lebih dari 1 Digit

Pesan m = 33, kunci publik (n = 77, e = 7). Tentukan ciphertext.

Penyelesaian:

c = m^e mod n = 33^7 mod 77

Langkah modular:

• 33^2 = 1089 → 1089 − 77 × 14 = 1089 − 1078 = 11
• 33^4 = 11^2 = 121 → 121 − 77 = 44
• 33^7 = 33^4 × 33^2 × 33^1 mod 77 = 44 × 11 × 33

Hitung: 44 × 11 = 484 → 484 − 77 × 6 = 484 − 462 = 22
22 × 33 = 726 → 726 − 77 × 9 = 726 − 693 = 33

Jadi, ciphertext c = 33

Tips Praktis Memahami Algoritma RSA

1. Mulai dari contoh sederhana dengan bilangan prima kecil agar mudah dihitung manual.
2. Gunakan metode pangkat modular untuk menghitung pangkat besar agar efisien.
3. Latihan soal step by step membantu memahami proses enkripsi dan dekripsi.
4. Gunakan tabel faktorisasi jika menghitung invers modular secara manual.
5. Pelajari konsep teori bilangan seperti bilangan prima, faktor, dan modulo agar RSA lebih mudah dipahami.

Manfaat Menguasai Algoritma RSA

1. Memahami prinsip dasar keamanan data digital.
2. Mampu mengenkripsi dan mendekripsi pesan secara aman.
3. Menjadi bekal untuk memahami kriptografi modern dan keamanan jaringan.
4. Membantu mempersiapkan ujian atau latihan soal mata kuliah keamanan informasi.
5. Meningkatkan kemampuan analisis matematis dan logika berpikir.

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

Kesimpulan

Panduan memahami algoritma RSA beserta contoh soal dan cara penyelesaiannya ini memberikan dasar yang kuat bagi pembaca untuk belajar kriptografi kunci publik. Dengan memahami langkah-langkah pembuatan kunci, enkripsi, dan dekripsi, siswa maupun profesional dapat menguasai RSA dari level dasar hingga menengah.

Latihan soal secara bertahap, pemahaman konsep, dan perhitungan step by step akan membuat pembaca mampu menyelesaikan soal RSA dengan mudah. Menguasai RSA juga menjadi keterampilan penting dalam bidang teknologi informasi, keamanan data, dan pengembangan aplikasi digital yang aman.

Penulis:kiara salsabilla