A Cryptanalytic Approach to Breaking RSA Encryption Using Public Key, with Proposed Improvement Leveraging Prime Number Distribution Patterns

RSA algorithm, a widely used public-key cryptosystem, relies on the difficulty of factoring large composite numbers into their prime factors. However, advancements in computational power and factorization techniques have introduced potential threats to its security. As RSA remains a cornerstone of modern cryptography, the need for improved in its security measures is paramount in the face of evolving computational challenges. This study presents a cryptanalytic examination of the RSA encryption scheme and proposes an improvement that leverages prime number distribution patterns to strengthen data security. Several mathematical methods which involve RSA key generation and its encryption/decryption process, ASCII Table, mapping as well as the Sieve of Eratosthenes were applied in the study. The research analyses how RSA public parameters and encoding methods can reveal structural weaknesses when subjected to mathematical scrutiny. To address these vulnerabilities, a modified scheme is introduced, in which plaintext characters are mapped using prime distribution patterns. This substitution increases ciphertexts randomness and minimizes predictable patterns between plaintexts and ciphertexts. Experimental evaluation demonstrates that the proposed improvement enhances resistance to analytical attacks while maintaining RSA operational compatibility. The study contributes to the on-going development of more secure and efficient public-key cryptographic systems.

RSA, Encryption, Decryption, Cryptanalysis

1. Ameha, T. T. (2021). Advanced mathematical formulas to calculate prime numbers. Strategic Planning, Commercial Bank of Ethiopia, Addis Ababa, Ethiopia. [Google Scholar] [Crossref]

2. Aminudina, A., & Cahyonoa, E. B. (2021). A practical analysis of the Fermat factorization and Pollard Rho method for factoring integers. Lontar Komputer, 12(1). https://doi.org/10.24843/LKJITI.2021 [Google Scholar] [Crossref]

3. Ariffin, M. R. K., & Shehu, S. (2016). Cryptanalysis on prime power RSA modulus of the form N = p^r q. International Journal of Applied Mathematical Research, 5(4), 167–175. [Google Scholar] [Crossref]

4. Hardy, G. H., & Wright, E. M. (2008). An introduction to the theory of numbers (6th ed.). Oxford University Press. [Google Scholar] [Crossref]

5. Hinek, M. J. (2009). Cryptanalysis of RSA and its variants. CRC Press. [Google Scholar] [Crossref]

6. Kannan, B., & Mohana, P. P. (2023). A survey of Fermat factorization algorithms for factoring RSA composite numbers. Mathematics and Its Applications in Technology: Multidisciplinary Science Journal. https://doi.org/10.3193/ [Google Scholar] [Crossref]

7. Kefa, R. (2006). Review of methods for integer factorization applied to cryptography. Journal of Applied Science, 6(1), 458–481. [Google Scholar] [Crossref]

8. Nadia, W. N., Syahril, E., Sawaluddin, (2020). Analysis of RSA variants in securing message. IOP Conf. Series: Materials Science and Engineering. DOI:10.1088/1757-899X/725/1/012131. [Google Scholar] [Crossref]

9. Nitaj, A. (2016). New Attacks on RSA with two or three decryption exponents. In International Conference on Cryptology in Africa; Springer, Cham, Switzerland, 8(3), 112–129. [Google Scholar] [Crossref]

10. Overmars, A., & Venkatraman, S. (2020). Mathematical attack of RSA by extending the sum of squares of primes to factorize a semi-prime. Mathematical and Computational Applications, 25(4), 63. https://doi.org/10.3390/mca25040063 [Google Scholar] [Crossref]

11. Overmars, A., & Venkatraman, S. (2021). New semi-prime factorization and application in large RSA key attacks. Journal of Cybersecurity and Privacy, 1(4), 660–674. https://doi.org/10.3390/jcp1040033 [Google Scholar] [Crossref]

12. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. [Google Scholar] [Crossref]

13. Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 124–134. [Google Scholar] [Crossref]

14. Somsuk, K., & Kasemvilas, S. (2013). MFFv2 and MNQsv2: Improved factorization algorithms. https://doi.org/10.1109/icisa.2013.6579415 [Google Scholar] [Crossref]

15. Wiener, M. J. (1990). Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36(3), 553–558. [Google Scholar] [Crossref]

• Interplay of Students’ Emotional Intelligence and Attitude toward Mathematics on Performance in Grade 10 Algebra
• Numerical Simulation of Fitzhugh-Nagumo Dynamics Using a Finite Difference-Based Method of Lines
• Fixed Point Theorem in Controlled Metric Spaces
• Usage of Moving Average to Heart Rate, Blood Pressure and Blood Sugar
• Exploring Algebraic Topology and Homotopy Theory: Methods, Empirical Data, and Numerical Examples