Pemanfaatan Persamaan Diophantine Linear dalam Membangkitkan Kunci Privat pada Algoritma RSA

Tahang Purwandi, Syamsyida Rozi

Abstract


The RSA algorithm is one of the most widely used public-key cryptographic algorithms due to its security, which is based on the difficulty of factoring large integers. One of the crucial steps in this algorithm is the generation of the private key, which mathematically involves solving an integer equation. This study aims to formally demonstrate that this process can be formulated as a linear Diophantine equation problem. The method involves transforming a congruence equation into a two-variable linear equation and solving it using the extended Euclidean algorithm. A case study is conducted by selecting two large prime numbers and a specific public key value. The results show that a private key value of 1197031 can be obtained from the solution of the Diophantine equation and successfully used to decrypt the message back into its original text. These findings indicate that the mathematical structure of the RSA algorithm can be fully explained through an elementary number theory approach, thereby enhancing conceptual understanding of the algorithm.

Keywords


Cryptography; Euclidean algorithm; Linear Diophantine Equation; Number Theory; RSA algorithm

Full Text:

PDF

References


1] T. W. E. Suryawijaya, “Memperkuat keamanan data melalui teknologi blockchain: Mengeksplo-154
rasi implementasi sukses dalam transformasi digital di indonesia,” Jurnal Studi Kebijakan Publik,155
vol. 2, no. 1, pp. 55–68, 2023.156
[2] N. Azis, “Perancangan aplikasi enkripsi dekripsi menggunakan metode caesar chiper dan operasi157
xor,” IKRA-ITH Informatika: Jurnal Komputer dan Informatika, vol. 2, no. 1, pp. 72–80, 2018.158
[3] M. Rizki and P. F. Ariyani, “Penerapan kriptografi dengan menggunakan algoritma rsa untuk159
pengamanan data berbasis desktop pada pt trias mitra jaya manunggal,” SKANIKA: Sistem Kom-160
puter dan Teknik Informatika, vol. 4, no. 2, pp. 77–82, 2021.161
[4] Badan Pengembangan dan Pembinaan Bahasa. “Kamus besar bahasa indonesia (kbbi) daring.”162
Diakses pada 14 Juni 2025. (2024), Available online.163
[5] C. Repi, J. Titaley, and E. Ketaren, “Implementasi kriptografi dalam pengamanan data gambar164
menggunakan algoritma rsa,” Jurnal TIMES, vol. 13, no. 1, pp. 93–99, 2024.165
[6] C. Chandra, “Keamanan data dengan metode kriptografi kunci publik,” Jurnal TIMES, vol. 5,166
no. 2, pp. 11–15, 2016.167
[7] S. Jarkasih, U. Fatimah, et al., “Penggunaan public key infrastructure kunci persetujuan (key168
agreement),” Jurnal Tiple A Pendidikan Teknologi Informasi dan Teknologi Informasi, vol. 1, no. 2,169
pp. 97–102, 2022.170
[8] E. Setiawan, G. M. Muhammad, and M. Soeleman, “Analisis kemampuan pemecahan masalah171
mahasiswa pada mata kuliah teori bilangan,” Mosharafa: Jurnal Pendidikan Matematika, vol. 10,172
no. 1, pp. 61–72, 2021.173
[9] D. Yesilyurt, Solving linear diophantine equations and linear congruential equations, 2012.174
[10] R. Irawan, Y. B. Ilhamsyah, et al., “Aplikasi enkripsi dan dekripsi pesan singkat menggunakan175
algoritma knapsack berbasis android,” Coding Jurnal Komputer dan Aplikasi, vol. 3, no. 3, 2015.176
[11] R. Munir, Kriptografi, 2nd ed. Bandung: Informatika Bandung, 2019.177
[12] A. Tampubolon, “Implementasi kombinasi algoritma rsa dan algoritma des pada aplikasi penga-178
man pesan teks,” Jurnal SAINTIKOM (Jurnal Sains Manajemen Informatika Dan Komputer),179
vol. 20, no. 1, pp. 38–43, 2021.180
[13] Y. A. Pradana, L. P. Dewi, M. A. Rahmah, A. Wijanarko, N. Ishartono, and D. A. Kusumaningtyas,181
“Penyelesaian aplikasi persamaan diophantine dengan algoritma euclid,” Jurnal Keilmuan Dan182
Keislaman, pp. 10–18, 2024.183
[14] M. Affaf, “Solusi persamaan diophantine bentuk kuadrat f (x, y)= 0,” Apotema: Jurnal Program184
Studi Pendidikan Matematika, vol. 10, no. 1, pp. 91–97, 2024.185
[15] A. Jupri, Dasar-dasar Teori Bilangan, 1st ed. Bandung: YRAMA WIDYA, 2020.186
[16] A. Asmat and W. Widowati, “Penyelesaian faktorisasi koprima dengan algoritma euclid dan metode187
ruang keadaan untuk penentuan pengendali yang menstabilkan sistem,” JURNAL SAINS DAN188
MATEMATIKA, vol. 20, no. 1, pp. 5–10,189




DOI: https://doi.org/10.18860/jrmm.v4i6.34656

Refbacks

  • There are currently no refbacks.