{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T20:04:03Z","timestamp":1773691443257,"version":"3.50.1"},"reference-count":18,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:00:00Z","timestamp":1749168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>In this paper, we present a novel method to solve trivariate polynomial modular equations of the form x(y2+Ay+B)+z\u22610\u00a0(mod\u00a0e). Our approach integrates Coppersmith\u2019s method with lattice basis reduction to efficiently solve the former equation. Several variants of RSA are based on the cubic Pell equation x3+fy3+f2z3\u22123fxyz\u22611\u00a0(mod\u00a0N), where f is a cubic nonresidue modulus N=pq. In these variants, the public exponent e and the private exponent d satisfy ed\u22611\u00a0(mod\u00a0\u03c8(N)) with \u03c8(N)=p2+p+1q2+q+1. Moreover, d can be written in the form d\u2261v0z0\u00a0(mod\u00a0\u03c8(N)) with any z0 satisfying gcd(z0,\u03c8(N))=1. In this paper, we apply our method to attack the variants when d\u2261v0z0\u00a0(mod\u00a0\u03c8(N)) and when |z0| and |v0| are suitably small. We also show that our method significantly improves the bounds of the private exponents d of the previous attacks on the variants, particularly in the scenario of small private exponents and in the scenarios where partial information about the primes is available.<\/jats:p>","DOI":"10.3390\/cryptography9020040","type":"journal-article","created":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T09:02:03Z","timestamp":1749200523000},"page":"40","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Improved Attack on the RSA Variant Based on Cubic Pell Equation"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-7251-3322","authenticated-orcid":false,"given":"Mohammed","family":"Rahmani","sequence":"first","affiliation":[{"name":"ACSA Laboratory, Department of Mathematics and Computer Science, Sciences Faculty, Mohammed First University, Oujda 60000, Morocco"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0372-1757","authenticated-orcid":false,"given":"Abderrahmane","family":"Nitaj","sequence":"additional","affiliation":[{"name":"LMNO, CNRS, UNICAEN, Caen Normandie University, 14000 Caen, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3744-4559","authenticated-orcid":false,"given":"Abdelhamid","family":"Tadmori","sequence":"additional","affiliation":[{"name":"Faculty of Sciences and Technology Al Hoceima, Abdelmalek Essaadi University, BP 34. Ajdir, Al Hoceima 32003, Morocco"}]},{"given":"Mhammed","family":"Ziane","sequence":"additional","affiliation":[{"name":"ACSA Laboratory, Department of Mathematics and Computer Science, Sciences Faculty, Mohammed First University, Oujda 60000, Morocco"}]}],"member":"1968","published-online":{"date-parts":[[2025,6,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A Method for Obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1109\/18.54902","article-title":"Cryptanalysis of short RSA secret exponents","volume":"36","author":"Wiener","year":"1990","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","first-page":"1","article-title":"Cryptanalysis of RSA with private key d less than N0.292","volume":"Volume 1592","author":"Boneh","year":"1999","journal-title":"Advances in Cryptology\u2014Eurocrypt\u201999"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s001459900030","article-title":"Small solutions to polynomial equations, and low exponent RSA vulnerabilities","volume":"10","author":"Coppersmith","year":"1997","journal-title":"J. Cryptol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/978-3-319-76620-1_6","article-title":"A Novel RSA-Like Cryptosystem Based on a Generalization of the R\u00e9dei Rational Functions","volume":"Volume 10737","author":"Kaczorowski","year":"2018","journal-title":"Number-Theoretic Methods in Cryptology"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/j.ffa.2006.05.004","article-title":"An efficient probabilistic public-key cryptosystem over quadratic fields quotients","volume":"13","author":"Castagnos","year":"2007","journal-title":"Finite Fields Their Appl."},{"key":"ref_7","first-page":"91","article-title":"Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers","volume":"Volume 1","author":"Elkamchouchi","year":"2002","journal-title":"Proceedings of the 8th International Conference on Communication Systems, ICCS 2002"},{"key":"ref_8","first-page":"27","article-title":"A New RSA-Type Scheme Based on Singular Cubic Curves with equation y2 \u2261 x3 + bx2 (mod N)","volume":"78","author":"Kuwakado","year":"1995","journal-title":"IEICE Trans. Fundam."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1017\/S0004972700037382","article-title":"A cubic analogue of the RSA cryptosystem","volume":"68","author":"Said","year":"2003","journal-title":"Bull. Aust. Math. Soc."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"114549","DOI":"10.1016\/j.tcs.2024.114549","article-title":"Partial prime factor exposure attacks on some RSA variants","volume":"999","author":"Feng","year":"2024","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/978-3-540-68164-9_12","article-title":"Another generalization of Wiener\u2019s attack on RSA","volume":"Volume 5023","author":"Vaudenay","year":"2008","journal-title":"Africacrypt 2008"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_13","unstructured":"May, A. (2003). New RSA Vulnerabilities Using Lattice Reduction Methods. [PhD Thesis, University of Paderborn]."},{"key":"ref_14","first-page":"131","article-title":"Finding small roots of univariate modular equations revisited","volume":"Volume 1355","year":"1997","journal-title":"Proceedings of the IMA International Conference on Cryptography and Coding"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/11935230_18","article-title":"A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants","volume":"Volume 4284","author":"Jochemsz","year":"2006","journal-title":"Proceedings of the ASIACRYPT 2006"},{"key":"ref_16","first-page":"140","article-title":"An improved analysis on three variants of the RSA cryptosystem","volume":"Volume 10143","author":"Peng","year":"2016","journal-title":"Proceedings of the International Conference on Information Security and Cryptology"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/j.tcs.2021.08.001","article-title":"Cryptanalysis of the RSA variant based on cubic Pell equation","volume":"889","author":"Zheng","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","unstructured":"(2025, May 05). HPC-MARWAN, National Center for Scientific and Technical Research (CNRST), Rabat, Morocco. Available online: http:\/\/hpc.marwan.ma\/index.php\/en\/."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/2\/40\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:47:47Z","timestamp":1760032067000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/2\/40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,6]]},"references-count":18,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["cryptography9020040"],"URL":"https:\/\/doi.org\/10.3390\/cryptography9020040","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,6]]}}}