Pemanfaatan Persamaan Diophantine Linear dalam Membangkitkan Kunci Privat pada Algoritma RSA

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.