Location:Home / Journals / Article Detail

Journal of Applied Mathematics and Computation

DOI:http://dx.doi.org/10.26855/jamc.2022.12.001

PDF Download

A Factorization Attack Algorithm on RSA Cryptosystem Using Fast Searching Algorithm

Yuh-Sien Sun1, Che Wun Chiou1,*, Wei-Cheng Sun2

1Chien Hsin University of Science and Technology, Taoyuan City, Taiwan, China.

2Business Unit. III, Himax Technologies, Inc., Taipei City, Taiwan, China.

*Corresponding author: Che Wun Chiou

Date: October 25,2022 Hits: 580

Abstract

The RSA cryptosystem is the first public key cryptosystem and has widely applied in privacy and ensure authenticity of digital data and included in many standards such as FIPS PUB 186-4. The security of RSA cryptosystem is heavily relied on the practical difficulty of factoring the product of p and q (N=p×q). Many studies are reported for attacking RSA cryptosystem, but no direct solving algorithms for finding p and q of the RSA cryptosystem by mathematical derivative are proposed. This paper uses strictly mathematical steps to derive out important parameters such as K=p+q, B = p-q, and   for breaking the RSA cryptosystem. Two fast searching methods are proposed to find out the correct K value, and then two primary values p =   and q =   can be computed directly. Proposed algorithms need division operations with complexity  in average to solve the q solution and suggest some important up-down search limits to attack RSA-2048 for helping cryptanalysis on such unbroken cryptosystem. The proposed algorithms can find out the precision K value with computation complexity  , and thus unbroken RSA cryptosystems with huge numbers such as the RSA-2048 cryptosystem will be solved immediately because exhaustive search is no more needed.

References

[1] Diffie,W., and Hellman, M. (1976). New directions in cryptography. IEEE Trans. Information Theory. IT-22, 644-654.

[2] Rivest, R., Shamir, A., and Adelman, L. (1978). A method for obtaining digital signature and public key cryptosystems. Com-munications of the ACM, 21, 120-126.

[3] Kaliski, B., and Staddon, J. (1998). PKCS #1: RSA Cryptography Specifications (Version 2.0). Network Working Group. https://www.rfc-editor.org/rfc/rfc2437.

[4] American National Standard for Financial Services. (1998). X9.31 -1998, Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA). American National Standards Institute.

[5] National Institute of Standards and Technology. (2013). FIPS PUB 186-4, Digital Signature Standard (DSS). https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.186-4.pdf.

[6] Barker, E. (2020). Recommendation for key management: Part 1 – General. NIST Special Publication 800-57 Part 1 Revision 5.

[7] Mahto, D., and Yadav, D. K. (2017). RSA and ECC: A Comparative Analysis.12, 9053-9061.

[8] Boneh, D. (1999). Twenty years of attacks on the RSA acyptosystem. Notices of the American Mathematical Society, 46, 203-213.

[9] Wiener, M. (1990). Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36, 553-558.

[10] Boneh, D., and Durfee, G. (1999) Cryptanalysis of RSA with Private Key d less than N0.292. Advances in Cryptology – EUROCRYPT’99, Lecture Notes in Computer Science 1592, Berlin: Springer, 1-11.

[11] Boneh, D., and Durfee, G. (2000). New results on the Cryptanalysis of Low Exponent RSA. IEEE Transactions on Information Theory, 46, 1339-1349.

[12] Loshin, P. (1998). Personal Encryption Clearly Explained. Academic Press, USA.

[13] Abubakar, A., Jabaka, S., Tijjani, B. I., Zeki, A., Chiroma, H., Usman, M. J., Raji, S., Mahmud, M. (2014). Cryptanalytic Attacks on Rivest, Shamir, and Adleman (RSA) Cryptosystem: Issues and Challenges. Journal of Theoretical and Applied Information Technology, 61, 1-7.

[14] Pomerance, C. (1996). A tale of two sieves. Notices of the American Mathematical Society, 43, 1473-1485. 

[15] Yan, S. Y. (2008). Cryptanalytic Attacks on RSA. Springer-Verlag, Heidelberg, Germany.

[16] Bruce, S. (1999). Cryptography: The Importance of Not Being Different. IEEE Computer, 32, 108-109.

[17] Kocher, P. C. (1999). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, 104-113.

[18] Kota, C. M., and Aissi, C. (2002). Implementation of the RSA algorithm and its cryptanalysis. Proceedings of the 2002 ASEE Gulf Southwest Annual Conference, The University of Louisiana at Lafayette.

[19] Aumüller, C., Bier, P., Fischer, W., Hofreiter, P., Seifert, J.-P. (2002). Fault attacks on RSA with CRT: Concrete results and practical countermeasures. International Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2002, LNCS, 2523, 260-275, Springer, Heidelberg, (Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.)).

[20] Sun, H.-M., Wu, M.-E., Ting, W.-C., Hinek, M. J. (2007). Dual RSA and its security analysis. IEEE Transactions on Information Theory, 53, 2922-2933.

[21] Kaliski, B. (2021). Announcement of “RSA Factoring Challenge”. Retrieved 8 March 2021.

[22] Denny, T., Dodson, B., Lenstra, A. K., Manasse, M. S. (1994). On the factoring of RSA-120. Advances in Cryptology - CRYPTO’ 93, LNCS, 773, 166-174.

[23] Cavallar, S., Dodson, B., Lenstra, A., Leyland, P., Lioen, W., Montgemery, P., Murphy, B., Zimmermann, P. (1999). Factoring of RSA-140 using the number field sieve. Proc. of Asiacrypt’99, Singapore. URL: http://www.comp.nus.edu.sg/~asia99.

[24] Eric, W. (2003). Prime Factorization Algorithms. From MathWorld--A Wolfram Web Resource. https://mathworld. wol-fram.com/PrimeFactorizationAlgorithms. html.

[25] Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W., Gaudry, P., Kruppa, A., Montgomery, P. L., Osvik, D. A., Riele, H. te., Timofeev, A., Zimmermann, P. (2010). Factorization of a 768-Bit RSA Modulus. CRYPTO 2010, California, USA, LNCS 6223, 333-350.

[26] RSA numbers, Wikipedia, https://en.wikipedia.org/wiki/RSA_numbers, accessed in 2022/1/13.

[27] Ercegovac, M. D., and Lang, T. (2004). Digital arithmetic, Elsevier.

Full-Text HTML

A Factorization Attack Algorithm on RSA Cryptosystem Using Fast Searching Algorithm

How to cite this paper:  Yuh-Sien Sun, Che Wun Chiou, Wei-Cheng Sun. (2022) A Factorization Attack Algorithm on RSA Cryptosystem Using Fast Searching Algorithm. Journal of Applied Mathematics and Computation6(4), 390-404.

DOI: http://dx.doi.org/10.26855/jamc.2022.12.001