Open Access
Research Article
Cryptanalysis of a cubic Pell variant of RSA with primes sharing least significant bits
Nurul Nur Hanisah AdenanInstitute for Mathematical Research Universiti Putra MalaysiaSerdang, Selangor, 43400, Malaysia0000-0002-5957-1524View full profile → , *Abderrahmane NitajCorresponding authorabderrahmane.nitaj@unicaen.frDepartment of Mathematics Normandie Univ UNICAEN, CNRS, LMNONormandie Univ Laboratoire de Mathématiques Nicolas Oresme Université de Caen NormandieCaen, 14000, France0000-0002-0372-1757View full profile → , Muhammad Rezal Kamel AriffinDepartment of Mathematics and Statistics Universiti Putra Malaysia; Institute for Mathematical Research Universiti Putra MalaysiaDepartment of Mathematics and Statistics Universiti Putra MalaysiaSerdang, Selangor, 43400, Malaysia0000-0001-5000-354XView full profile → , Nur Azman AbuFaculty of Information Technology and Communication Universiti Teknikal Malaysia Melaka, Malaysia0000-0003-4624-3123View full profile →
* Corresponding author · click or hover a name for details
- Received:
- 14 Jun 2022
- Published Online:
- 29 Jul 2024
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-1333
- Pages:
- 1263–1280
Abstract
In this paper, we push further the cryptanalysis of a cryptosystem of the RSA’s variant which utilized a cubic Pell equation with the key equation ed − k(p2 + p + 1)(q2 + q + 1) = 1 where N = pq is an RSA modulus, e, N are publicized, while d, p, q are kept private. We consider the case where the prime factors share an amount of their least significant bits (LSBs), that is p and q satisfy p – q = 2m u where m is known, and u is unknown. Through this work, we show that via Coppermith’s method and lattice basis reduction, it is feasible to retrieve the secret key d and factor N for larger values of d.
Keywords
Subject Classifications
11T7114G50
References
[1] Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than N0.292, Advances in Cryptology-Eurocrypt’99, Lecture Notes in Computer Science 1592, pp. 1-11, Springer, Berlin, Heidelberg, (1999). 10.1007/3-540-48910-X_1[2] Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, 10(4), 233-260, (1997)[3] Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited, In: IMA International Conference on Cryptography and Coding, LNCS 1355, pp. 131-142, Springer, Berlin, Heidelberg (1997). 10.1007/BFb0024458.[4] Jochemsz, E., May, A.: A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, In: ASIACRYPT 2006, LNCS 4284, pp. 267-282, Springer-Verlag (2006). 10.1007/11935230_18.[5] Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients, Mathematische Annalen, 261, pp. 513-534, (1982).[6] May, A.: New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis, University of Paderborn, Germany (2003).[7] Murru N., Saettone F.M.: A novel rsa-like cryptosystem based on a generalization of the rédei rational functions. In: Kaczorowski J., Pieprzyk J., Pomykala J. (eds) Number-Theoretic Methods in Cryptology. NuTMiC 2017. Lecture Notes in Computer Science, 10737 pp. 91-103, Springer, Cham, (2018) . 10.1007/978-3-319-76620-1_6.[8] Nitaj, A.: Another generalization of Wiener’s attack on RSA, In: Vaudenay, S. (Ed.) Africacrypt 2008. LNCS, 5023, pp. 174-190. Springer, Heidelberg (2008). 10.1007/978-3-540-68164-9_12.[9] Nitaj, A., Arrifin, M.R.K., D.I. Nassr, Bahig, H.M.: New attacks on the RSA cryptosystem, in D. Pointcheval and D. Vergnaud (Eds.): AFRICACRYPT 2014, LNCS 8469, pp. 178-198, Springer (2014).[10] Nitaj, A., Arrifin, M.R.K., Adenan, N.N.H., Abu, N.A.: Classical attacks on a variant of the RSA cryptosystem, LATINCRYPT 2021, pp.151-167, Springer (2021).[11] Nitaj, A., Arrifin, M.R.K., Adenan, N.N.H., Lau, T.S.C., Chen, J.: Security issues of novel RSA variant, IEEE Access, 10, 53788-53796, (2002).[12] Rivest, R., Shamir, A., Adleman, L.: A Method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM,21(2), 120-126 (1978).[13] Steinfeld, R., Zheng, Y.: On the security of RSA with primes sharing least-significant bits. Appl. Algebra Eng. Commun. Comput. 15(3-4), 179-200 (2004).[14] Sun, H.M., Wu, M.E., Steinfeld, R., Guo, J., Wang, H.: Cryptanalysis of short exponent RSA with primes sharing least significant bits. in MK Franklin, LCK Hui & DS Wong (eds), Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings. vol. 5339 LNCS, Lecture Notes in Computer Science (2008).[15] Wiener, M.: Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information Theory,36(3), 553-558 (1990).[16] Zheng, M., Kunihiro, N., Yao, Y: Cryptanalysis of the RSA variant based on cubic Pell equation, Theoretical Computer Science, 889, 135-144, (2021).
Views: 305Downloads: 7Citations: 1
