The special method with the fake key to attack RSA

Somsuk, Kritsanapong; Sanemueang, Chalida; Khummanee, Suchart; Suwannapong, Chanwit; Atsawaraungsuk, Sarutte

doi:10.47974/JIM-1689

Open Access Research Article

The special method with the fake key to attack RSA

^*Kritsanapong SomsukCorresponding authorkritsanapong@udru.ac.thDepartment of Computer and Communication EngineeringUdon Thani Rajabhat UniversityUdon Thani, 41000, Thailand0000-0002-7264-4628View full profile → , Chalida SanemueangChalida.sa@udru.ac.thOffice of Academic Resources and Information TechnologyUdon Thani Rajabhat UniversityUdon Thani, 4100, ThailandView full profile → , Suchart Khummaneesuchart.k@msu.ac.thDepartment of Computer ScienceMahasarakham UniversityMahasarakham, 44150, ThailandView full profile → , Chanwit Suwannapongschanwit@npu.ac.thDepartment of Computer EngineeringNakhon Phanom UniversityNakhon Phanom, 48000, ThailandView full profile → , Sarutte Atsawaraungsuksarutte@udru.ac.thDepartment of Computer EducationUdon Thani Rajabhat UniversityUdon Thani, 41000, ThailandView full profile →

* Corresponding author · click or hover a name for details

pp. 1461–1479Vol. 27Issue 7November 2024DOI: 10.47974/JIM-1689XML

Received:: 12 Oct 2022
Published Online:: 26 Nov 2024
Article type:: Research Article
Language:: EN
Article no.:: JIM-1689
Pages:: 1461–1479

Abstract

Because RSA is the cryptographic algorithm that is still extensively employed today, several attack techniques against RSA are continually being developed. These algorithms are divided into two distinct groups. The first group is a general group unaffected by RSA parameters. The other group is unique due to at least one characteristic that represents a vulnerability. The aim of this research is to reveal the new vulnerabilities in RSA and to provide ways for recovering the original plaintext. The first vulnerability occurs when the sum of the private key and Euler totient function is near to the modulus but lower than the modulus. If this result is found, it can be selected as the exponent which is called the fake key. The second situation occurs whenever the key is larger than the modulus. The experimental results indicate that if a new weak point is found, the fake key may be disclosed quickly despite the modulus’s size. In addition, when the sum of the public key and the Euler totient function is relatively near to the modulus, the proposed method can be also used to break the modulus. Additionally, the other vulnerability is demonstrated. It occurs when the product of the unknown integer j and the modulus is near to the addition of the key and the product of the other unknown integer and the Euler totient function. However, the issue with the second weak point is the mechanism for finding j.

Keywords

RSA Computation Time Decryption process The fake key FK FK2

Subject Classifications

94A6000A6968R01

References

[1] V. K. Vivek and R. G. Rati, “Hybrid symmetric cryptography approach for secure communication in web application,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 24, no. 5, pp. 1179-1187 (2021).
[2] W. Diffie and M. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654 (1976).
[3] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public key cryptosystems,” Communications of ACM, vol. 21, pp. 120–126 (1978).
[4] G. C. Kim, S. C. Li, and H. C. Hwang, “Fast rebalanced RSA signature scheme with typical prime generation,” Theoretical Computer Science, vol. 830-831, pp. 1-19 (2020).
[5] S. M. Hamdi, S. T. Zuhori, F. Mahmud, and B. Pal, “A compare between Shor’s quantum factoring algorithm and General Number Field Sieve,” in Proceedings of the International Conference on Electrical Engineering and Information & Communication Technology, Dhaka, pp. 1-6, Apr. 10–12 (2014).
[6] S. Murat, “Generalized trial division,” International Journal of Contemporary Mathematical Science, vol. 6, no. 2, pp. 59–64 (2011).
[7] M. Wiener, “Cryptanalysis of short RSA secret exponents,” IEEE Transactions on Information Theory, vol. 36, pp. 553-558 (1990).
[8] J. M. Pollard, “Theorems of factorization and primality testing,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 76, no. 3, pp. 521-528 (1974).
[9] B. R. Ambedkar, A. Gupta, P. Gautam, and S. S. Bedi, “An efficient method to factorize the RSA public key encryption,” in Proceedings of the International Conference on Communication Systems and Network Technologies, Katra, pp. 108-111, Jun. 3–5 (2011).
[10] M. Cosnard and J. Philippe, “The quadratic sieve factoring algorithm on distributed memory multiprocessors,” in Proceedings of the Fifth Distributed Memory Computing Conference, Charleston, pp. 254-262, Apr. 8–12 (1990).

[11] F. Lemmermeyer, “Václav Šimerka: quadratic forms and factorization,” LMS Journal of Computation and Mathematics, vol. 16, pp. 118-129 (2013).
[12] N. Lal, A. P. Singh, and S. Kumar, “Modified trial division algorithm using KNJ-factorization method to factorize RSA public key encryption,” in Proceedings of the International Conference on Contemporary Computing and Informatics, Mysore, pp. 992-995, Nov. 27–29 (2014).
[13] K. Somsuk, T. Chiawchanwattana, and C. Sanemueang, “Estimating the new initial value of trial division algorithm for balanced modulus to decrease computation loops,” in Proceedings of the International Joint Conference on Computer Science and Software Engineering, Chonburi, pp. 143-147, Jul. 10–12 (2019).
[14] M. E. Wu, R. Tso, and H. M. Sun, “On the improvement of Fermat factorization using a continued fraction technique,” Future Generation Computer Systems, vol. 30, no. 1, pp. 162–168 (2014).
[15] K. Somsuk, “The improvement of initial value closer to the target for Fermat’s factorization algorithm,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 21, no. 7-8, pp. 1573–1580 (2018).
[16] K. Omar and L. Szalay, “Sufficient conditions for factoring a class of large integers,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 13, pp. 95-103 (2010).
[17] H. W. Lenstra, “Factoring integers with elliptic curves,” Annals of Mathematics, vol. 126, no. 3, pp. 649–673 (1987).
[18] N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, pp. 103–109 (1987).
[19] V. S. Miller, “Uses of elliptic curves in cryptography,” Lecture Notes in Computer Science, vol. 218, pp. 417–428 (1986).
[20] S. D. Sumit, S. Brahmjit, and J. Poonam, “Demystifying elliptic curve cryptography: Curve selection, implementation and countermeasures to attacks,” Journal of Interdisciplinary Mathematics, vol. 23, no. 2, pp. 463–470 (2020).
[21] K. Somsuk, “The improvement of elliptic curve factorization method to recover RSA’s prime factors,” Symmetry, vol. 13, pp. 1-15 (2021).
[22] J. M. Pollard, “Theorems of factorization and primality testing,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 76, no. 3, pp. 521-528 (1974).
[23] K. Somsuk, “An efficient variant of Pollard’s p − 1 for the case that all prime factors of the p − 1 in B-smooth,” Symmetry, vol. 14, pp. 1-17 (2022).
[24] P. Sharma, A. K. Gupta, and A. Vijay, “Notice of violation of IEEE publication principles: Modified integer factorization algorithm using V-factor method,” in Proceedings of the International Conference on Advanced Computing & Communication Technologies, Rohtak, Haryana, pp. 423-425, Jan. 7–8 (2012).
[25] K. Somsuk, “Improving the initial values of V-factor suitable for balanced modulus,” International Journal of Electrical and Computer Engineering, vol. 10, no. 6, pp. 6446-6452 (2020).
[26] D. Boneh and G. Durfee, “Cryptanalysis of RSA with private key d less than N^0.292,” Lecture Notes in Computer Science, vol. 1592, pp. 1-11 (1999).
[27] K. Somsuk, “A new methodology to find private key of RSA based on Euler totient function,” Baghdad Science Journal, vol. 18, no. 2, pp. 338-348 (2021).
[28] K. Somsuk, “The improved estimation of the least upper bound to search for RSA’s private key,” KSII Transactions on Internet and Information Systems, vol. 16, no. 6, pp. 2074-2093 (2022).
[29] K. Somsuk, “The new weakness of RSA and the algorithm to solve this problem,” KSII Transactions on Internet and Information Systems, vol. 14, no. 9, pp. 3841-3857 (2020).

Views: 372Downloads: 152Citations: 0