{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:08:08Z","timestamp":1760058488731,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2025,4,12]],"date-time":"2025-04-12T00:00:00Z","timestamp":1744416000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Several RSA variants enforce a constraint between their public and private keys through the relation ed\u22611(mod(p2\u22121)(q2\u22121)), where p and q are the prime factors of their RSA modulus N=pq. In this paper, we introduce a novel attack on RSA variant schemes where the public exponent satisfies an equation of the form eu\u2261z(mod(p2\u22121)(q2\u22121)), with sufficiently small |z|, |u|, in a scenario where the attacker has access to an approximation of one of the prime factors. Our new attack utilizes Coppersmith\u2019s method, combined with lattice basis reduction techniques, to efficiently recover the prime factors of the RSA modulus in these scenarios. This method offers a significant improvement over prior attacks on RSA variants with small private exponents or partial prime information.<\/jats:p>","DOI":"10.3390\/a18040223","type":"journal-article","created":{"date-parts":[[2025,4,14]],"date-time":"2025-04-14T04:42:07Z","timestamp":1744605727000},"page":"223","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Cryptanalysis of Some RSA Variants"],"prefix":"10.3390","volume":"18","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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0372-1757","authenticated-orcid":false,"given":"Abderrahmane","family":"Nitaj","sequence":"additional","affiliation":[{"name":"The Nicolas Oresme Laboratory of Mathematics, University of Caen Normandy, 14000 Caen, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mhammed","family":"Ziane","sequence":"additional","affiliation":[{"name":"ACSA Laboratory, Department of Mathematics and Computer Science, Sciences Faculty, Mohammed First University, Oujda 60000, Morocco"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,4,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"Diffie","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","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_3","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_4","unstructured":"Boneh, D., and Durfee, G. (1592). Cryptanalysis of RSA with private key d less than N0.292, Advances in Cryptology-Eurocrypt\u201999. Lecture Notes in Computer Science, Springer."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1049\/el:19820617","article-title":"Fast decipherment algorithm for RSA public-key cryptosystem","volume":"18","author":"Quisquater","year":"1982","journal-title":"Electron. Lett."},{"key":"ref_6","unstructured":"Collins, T., Hopkins, D., Langford, S., and Sabin, M. (1998). Public Key Cryptographic Apparatus and Method. (#5,848,159), US Patent."},{"key":"ref_7","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_8","unstructured":"Elkamchouchi, H., Elshenawy, K., and Shaban, H. (2002, January 28\u201328). Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers. Proceedings of the The 8th International Conference on Communication Systems, Singapore."},{"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","unstructured":"Smith, P.J., and Lennon, M.J.J. (1993, January 12\u201314). LUC: A New Public Key System. Proceedings of the ninth IFIP International Symposium on Computer Security, Toronto, ON, Canada."},{"key":"ref_11","first-page":"203","article-title":"Twenty years of attacks on the RSA cryptosystem","volume":"46","author":"Boneh","year":"1999","journal-title":"Notices Amer. Math. Soc."},{"key":"ref_12","first-page":"140","article-title":"An improved analysis on three variants of the RSA cryptosystem","volume":"10143","author":"Peng","year":"2016","journal-title":"Int. Conf. Inf. Secur. Cryptol."},{"key":"ref_13","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_14","doi-asserted-by":"crossref","unstructured":"Vaudenay, S. (2008). Another Generalization of Wiener\u2019s Attack on RSA, Springer. Africacrypt 2008 LNCS.","DOI":"10.1007\/978-3-540-68164-9"},{"key":"ref_15","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_16","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/BF01457454","article-title":"Lov\u00e1sz, L. Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_17","unstructured":"May, A. (2003). New RSA Vulnerabilities Using Lattice Reduction Methods. [Ph.D. Thesis, University of Paderborn]."},{"key":"ref_18","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_19","doi-asserted-by":"crossref","unstructured":"Howgrave-Graham, N. (1997, January 17\u201319). Finding small roots of univariate modular equations revisited. Proceedings of the IMA International Conference on Cryptography and Coding, LNCS 1355, Cirencester, UK.","DOI":"10.1007\/BFb0024458"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Jochemsz, E., and May, A. (2006). A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants, Springer. ASIACRYPT 2006, LNCS 4284.","DOI":"10.1007\/11935230_18"},{"key":"ref_21","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_22","unstructured":"(2025, April 08). The Sage Developers: SageMath, the Sage Mathematics Software System (Version 10.4) (2025). Available online: https:\/\/www.sagemath.org."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/4\/223\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:13:22Z","timestamp":1760030002000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/4\/223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,12]]},"references-count":22,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,4]]}},"alternative-id":["a18040223"],"URL":"https:\/\/doi.org\/10.3390\/a18040223","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,4,12]]}}}