{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T14:42:18Z","timestamp":1784126538116,"version":"3.55.0"},"reference-count":31,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:00:00Z","timestamp":1662768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Scientific Research Deanship at University of Ha\u2019il\u2014Saudi Arabia","award":["RG-21 124"],"award-info":[{"award-number":["RG-21 124"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The RSA (Rivest\u2013Shamir\u2013Adleman) asymmetric-key cryptosystem is widely used for encryptions and digital signatures. Let (n,e) be the RSA public key and d be the corresponding private key (or private exponent). One of the attacks on RSA is to find the private key d using continued fractions when d is small. In this paper, we present a new technique to improve a small private exponent attack on RSA using continued fractions and multicore systems. The idea of the proposed technique is to find an interval that contains \u03d5(n), and then propose a method to generate different points in the interval that can be used by continued fraction and multicore systems to recover the private key, where \u03d5 is Euler\u2019s totient function. The practical results of three small private exponent attacks on RSA show that we extended the previous bound of the private key that is discovered by continued fractions. When n is 1024 bits, we used 20 cores to extend the bound of d by 0.016 for de Weger, Maitra-Sarkar, and Nassr et al. attacks in average times 7.67 h, 2.7 h, and 44 min, respectively.<\/jats:p>","DOI":"10.3390\/sym14091897","type":"journal-article","created":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T22:37:28Z","timestamp":1663108648000},"page":"1897","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Small Private Exponent Attacks on RSA Using Continued Fractions and Multicore Systems"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8137-7939","authenticated-orcid":false,"given":"Hatem M.","family":"Bahig","sequence":"first","affiliation":[{"name":"Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5550-3372","authenticated-orcid":false,"given":"Dieaa I.","family":"Nassr","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0703-5826","authenticated-orcid":false,"given":"Mohammed A.","family":"Mahdi","sequence":"additional","affiliation":[{"name":"Information and Computer Science Department, College of Computer Science and Engineering, University of Ha\u2019il, Hail, Ha\u2019il 81481, Saudi Arabia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9448-6168","authenticated-orcid":false,"given":"Hazem M.","family":"Bahig","sequence":"additional","affiliation":[{"name":"Information and Computer Science Department, College of Computer Science and Engineering, University of Ha\u2019il, Hail, Ha\u2019il 81481, Saudi Arabia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2022,9,10]]},"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":"1484","DOI":"10.1137\/S0097539795293172","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"26","author":"Shor","year":"1997","journal-title":"SIAM J. Comput."},{"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","doi-asserted-by":"crossref","first-page":"1339","DOI":"10.1109\/18.850673","article-title":"Cryptanalysis of RSA with private key d less than N0.292","volume":"46","author":"Boneh","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","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_6","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s002000100088","article-title":"Cryptanalysis of RSA with Small Prime Difference","volume":"13","year":"2002","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer, J., and May, A. (2004). A Generalized Wiener Attack on RSA. Public Key Cryptography\u2014PKC 2004, Proceedings of the 7th International Workshop on Theory and Practice in Public Key Cryptography, Singapore, 1\u20134 March 2004, Springer. Lecture Notes in Computer Science (Volume 2947).","DOI":"10.1007\/978-3-540-24632-9_1"},{"key":"ref_8","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. Advances in Cryptology\u2014ASIACRYPT 2006, Proceedings of the 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, China, 3\u20137 December 2006, Springer. Lecture Notes in Computer Science (Volume 4284).","DOI":"10.1007\/11935230_18"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Maitra, S., and Sarkar, S. (2008). Revisiting Wiener\u2019s Attack\u2014New Weak Keys in RSA. Information Security, Proceedings of the 11th International Conference, ISC 2008, Taipei, Taiwan, 15\u201318 September 2008, Springer. Lecture Notes in Computer Science (Volume 5222).","DOI":"10.1007\/978-3-540-85886-7_16"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Nitaj, A., Ariffin, M.R.K., Nassr, D.I., and Bahig, H.M. (2014). New Attacks on the RSA Cryptosystem. Progress in Cryptology\u2014AFRICACRYPT 2014, Proceedings of the P7th International Conference on Cryptology in Africa, Marrakesh, Morocco, 28\u201330 May 2014, Springer International Publishing.","DOI":"10.1007\/978-3-319-06734-6_12"},{"key":"ref_11","first-page":"51","article-title":"Performance Analysis of Fermat Factorization Algorithms","volume":"11","author":"Bahig","year":"2020","journal-title":"Int. J. Adv. Comput. Sci. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bahig, H.M., Bahig, H.M., and Kotb, Y. (2020). Fermat Factorization using a Multi-Core System. Int. J. Adv. Comput. Sci. Appl., 11.","DOI":"10.14569\/IJACSA.2020.0110444"},{"key":"ref_13","first-page":"51","article-title":"Speeding Up Fermat\u2019s Factoring Method using Precomputation","volume":"6","author":"Bahig","year":"2022","journal-title":"Ann. Emerg. Technol. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Nassr, D.I., Bahig, H.M., Bhery, A., and Daoud, S.S. (April, January 31). A new RSA vulnerability using continued fractions. Proceedings of the 2008 IEEE\/ACS International Conference on Computer Systems and Applications, Doha, Qatar.","DOI":"10.1109\/AICCSA.2008.4493604"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1142\/S0129054120500045","article-title":"A Unified Method for Private Exponent Attacks on RSA Using Lattices","volume":"31","author":"Bahig","year":"2020","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Jones, W.B., and Thron, W.J. (1984). Continued Fractions: Analytic Theory and Applications. Encyclopedia of Mathematics and Its Applications, Cambridge University Press.","DOI":"10.1017\/CBO9780511759550"},{"key":"ref_17","unstructured":"Cuyt, A.A., Petersen, V., Verdonk, B., Waadeland, H., and Jones, W.B. (2008). Handbook of Continued Fractions for Special Functions, Springer. [1st ed.]."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Steinfeld, R., Contini, S., Pieprzyk, J., and Wang, H. (2005). Converse Results to the Wiener Attack on RSA, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-540-30580-4_13"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Stein, W. (2008). Elementary Number Theory: Primes, Congruences, and Secrets: A Computational Approach, Springer. Undergraduate Texts in Mathematics.","DOI":"10.1007\/b13279"},{"key":"ref_20","first-page":"101","article-title":"Continued fractions and RSA with small secret exponent","volume":"29","author":"Dujella","year":"2004","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_21","unstructured":"May, A. (2003). New RSA Vulnerabilities Using Lattice Reduction Methods. [Ph.D. Thesis, University of Paderborn]. Available online: http:\/\/www.cs.uni-paderborn.de\/uploads\/tx_sibibtex\/bp.pdf."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2150038","DOI":"10.1142\/S0218126621500389","article-title":"A New Side-Channel Attack on Reduction of RSA CRT Montgomery Method Based","volume":"30","author":"Kaedi","year":"2020","journal-title":"J. Circuits Syst. Comput."},{"key":"ref_23","unstructured":"GNU, MP (2022, August 01). The GNU Multiple Precision Arithmetic Library, 6.2.1 ed. Available online: http:\/\/gmplib.org\/."},{"key":"ref_24","unstructured":"OpenMP Architecture Review Board (2022, August 01). OpenMP Application Program Interface Version 5.2. Available online: https:\/\/www.openmp.org\/wp-content\/uploads\/OpenMP-API-Specification-5-2.pdf."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Bahig, H., Bhery, A., and Nassr, D. (2012). Cryptanalysis of Multi-Prime RSA with Small Prime Difference. Information and Communications Security, Proceedings of the 14th International Conference, ICICS 2012, Hong Kong, China, 29\u201331 October 2012, Springer. Lecture Notes in Computer Science (Volume 7618).","DOI":"10.1007\/978-3-642-34129-8_4"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.tcs.2022.05.010","article-title":"Improving small private exponent attack on the Murru-Saettone cryptosystem","volume":"923","author":"Nassr","year":"2022","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.tcs.2017.09.009","article-title":"A generalized attack on RSA type cryptosystems","volume":"704","author":"Bunder","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Nitaj, A., Kamel Ariffin, M.R., Hanisah Adenan, N.N., and Azman Abu, N. (2021). Classical Attacks on a Variant of the RSA Cryptosystem. Progress in Cryptology\u2014LATINCRYPT 2021, Proceeding of the 7th International Conference on Cryptology and Information Security in Latin America, Bogot\u00e1, Colombia, 6\u20138 October 2021, Springer. Lecture Notes in Computer Science (Volume 12912).","DOI":"10.1007\/978-3-030-88238-9_8"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"53788","DOI":"10.1109\/ACCESS.2022.3175519","article-title":"Security Issues of Novel RSA Variant","volume":"10","author":"Nitaj","year":"2022","journal-title":"IEEE Access"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Abd Ghafar, A.H., Kamel Ariffin, M.R., and Asbullah, M.A. (2020). A New LSB Attack on Special-Structured RSA Primes. Symmetry, 12.","DOI":"10.3390\/sym12050838"},{"key":"ref_31","unstructured":"Durfee, G. (2002). Cryptanalysis of RSA Using Algebraic and Lattice Methods. [Ph.D. Thesis, Stanford University]. Available online: http:\/\/theory.stanford.edu\/~gdurf\/durfee-thesis-phd.pdf."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/9\/1897\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:29:04Z","timestamp":1760142544000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/9\/1897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,10]]},"references-count":31,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2022,9]]}},"alternative-id":["sym14091897"],"URL":"https:\/\/doi.org\/10.3390\/sym14091897","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,10]]}}}