{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T23:15:00Z","timestamp":1782774900635,"version":"3.54.5"},"reference-count":35,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>Let (N,e) be a public key of the RSA cryptosystem, and d be the corresponding private key. In practice, we usually choose a small e  for quick encryption. In this paper, we improve partial private key exposure attacks against RSA with a small public exponent e. The key idea is that under such a setting we can usually obtain more information about the prime factor of N and then by solving a univariate modular polynomial with Coppersmith's method, N can be factored in polynomial time. Compared to previous results, we reduce the number of d's leaked bits needed to mount the attack by log_2 (e) bits. Furthermore, our experiments show that for 1024-bit N, our attack can achieve the theoretical bound on a personal computer, which verified our attack. <\/jats:p>","DOI":"10.62056\/ahjbhey6b","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T15:13:33Z","timestamp":1728314013000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":2,"title":["Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-7085-377X","authenticated-orcid":false,"given":"Yansong","family":"Feng","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02jkmyk67","id-type":"ROR","asserted-by":"publisher"}],"name":"Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences","place":["Beijing, NJ, 08544, China"]},{"id":[{"id":"https:\/\/ror.org\/05qbk4x57","id-type":"ROR","asserted-by":"publisher"}],"name":"School of Mathematical Sciences, University of Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0372-1757","authenticated-orcid":false,"given":"Abderrahmane","family":"Nitaj","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04cr3xz70","id-type":"ROR","asserted-by":"publisher"}],"name":"Normandie University","place":["Caen, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5591-0234","authenticated-orcid":false,"given":"Yanbin","family":"Pan","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02jkmyk67","id-type":"ROR","asserted-by":"publisher"}],"name":"Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences","place":["Beijing, NJ, 08544, China"]},{"id":[{"id":"https:\/\/ror.org\/05qbk4x57","id-type":"ROR","asserted-by":"publisher"}],"name":"School of Mathematical Sciences, University of Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:rivest1978method","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A Method for Obtaining Digital Signatures and Public-Key\n  Cryptosystems","volume":"21","author":"Ronald L. Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref2:wiener1990cryptanalysis","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1109\/18.54902","article-title":"Cryptanalysis of short RSA secret exponents","volume":"36","author":"Michael J. Wiener","year":"1990","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref3:boneh1999cryptanalysis","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-48910-X_1","article-title":"Cryptanalysis of RSA with Private Key Less than\n  ${N}^{0.292}$","volume":"1592","author":"Dan Boneh","year":"1999"},{"key":"ref4:herrman2009attacking","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-642-10366-7_29","article-title":"Attacking Power Generators Using Unravelled Linearization:\n  When Do We Output Too Much?","volume":"5912","author":"Mathias Herrmann","year":"2009"},{"key":"ref5:herrman2010maximizing","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-642-13013-7_4","article-title":"Maximizing Small Root Bounds by Linearization and\n  Applications to Small Secret Exponent RSA","volume":"6056","author":"Mathias Herrmann","year":"2010"},{"key":"ref6:kunihiro2012unified","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-28496-0_16","article-title":"A Unified Framework for Small Secret Exponent Attack on\n  RSA","volume":"7118","author":"Noboru Kunihiro","year":"2011"},{"key":"ref7:takayasu2016generalize","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-662-49387-8_4","article-title":"How to Generalize RSA Cryptanalyses","volume":"9615","author":"Atsushi Takayasu","year":"2016"},{"key":"ref8:miller1975riemann","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1145\/800116.803773","article-title":"Riemann's Hypothesis and Tests for Primality","author":"Gary L. Miller","year":"1975"},{"key":"ref9:may2004computing","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-540-28628-8_13","article-title":"Computing the RSA Secret Key Is Deterministic Polynomial\n  Time Equivalent to Factoring","volume":"3152","author":"Alexander May","year":"2004"},{"key":"ref10:coron2007deterministic","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/S00145-006-0433-6","article-title":"Deterministic Polynomial-Time Equivalence of Computing the\n  RSA Secret Key and Factoring","volume":"20","author":"Jean-S\u00e9bastien Coron","year":"2007","journal-title":"J. Cryptol."},{"key":"ref11:zhou2022third","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/978-3-031-22972-5_18","article-title":"A Third is All You Need: Extended Partial Key Exposure\n  Attack on CRT-RSA with Additive Exponent Blinding","volume":"13794","author":"Yuanyuan Zhou","year":"2022"},{"key":"ref12:coppersmith1996finding","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-68339-9_14","article-title":"Finding a Small Root of a Univariate Modular Equation","volume":"1070","author":"Don Coppersmith","year":"1996"},{"key":"ref13:coppersmith1997small","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/S001459900030","article-title":"Small Solutions to Polynomial Equations, and Low Exponent\n  RSA Vulnerabilities","volume":"10","author":"Don Coppersmith","year":"1997","journal-title":"J. Cryptol."},{"key":"ref14:boneh1998attack","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/3-540-49649-1_3","article-title":"An Attack on RSA Given a Small Fraction of the Private Key\n  Bits","volume":"1514","author":"Dan Boneh","year":"1998"},{"key":"ref15:blomer2003new","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-540-45146-4_2","article-title":"New Partial Key Exposure Attacks on RSA","volume":"2729","author":"Johannes Bl\u00f6mer","year":"2003"},{"key":"ref16:ernst2005partial","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/11426639_22","article-title":"Partial Key Exposure Attacks on RSA up to Full Size\n  Exponents","volume":"3494","author":"Matthias Ernst","year":"2005"},{"key":"ref17:aono2009new","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-00468-1_3","article-title":"A New Lattice Construction for Partial Key Exposure Attack\n  for RSA","volume":"5443","author":"Yoshinori Aono","year":"2009"},{"key":"ref18:takayasu2019partial","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/J.TCS.2018.08.021","article-title":"Partial key exposure attacks on RSA: Achieving the\n  Boneh-Durfee bound","volume":"761","author":"Atsushi Takayasu","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref19:suzuki2020extended","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/J.TCS.2020.07.004","article-title":"Extended partial key exposure attacks on RSA:\n  Improvement up to full size decryption exponents","volume":"841","author":"Kaichi Suzuki","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref20:boneh1998attack-full","volume-title":"Exposing an RSA Private Key Given a Small Fraction of its\n  Bits","author":"Dan Boneh","year":"1998"},{"key":"ref21:ajtai1998shortest","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/276698.276705","article-title":"The Shortest Vector Problem in L\\({}_{\\mbox{2}}\\) is\n  NP-hard for Randomized Reductions (Extended Abstract)","author":"Mikl\u00f3s Ajtai","year":"1998"},{"key":"ref22:lenstra1982factoringa","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring Polynomials with Rational Coefficients","volume":"261","author":"Arjen K Lenstra","year":"1982","journal-title":"Mathematische Annalen"},{"key":"ref23:may2003new","volume-title":"New RSA Vulnerabilities Using Lattice Reduction Methods","author":"Alexander May","year":"2003"},{"key":"ref24:howgrave-graham1997finding","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BFB0024458","article-title":"Finding Small Roots of Univariate Modular Equations\n  Revisited","volume":"1355","author":"Nick Howgrave-Graham","year":"1997"},{"key":"ref25:may2009implicit","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-00468-1_1","article-title":"Implicit Factoring: On Polynomial Time Factoring Given Only\n  an Implicit Hint","volume":"5443","author":"Alexander May","year":"2009"},{"key":"ref26:may2021partial","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-030-92062-3_4","article-title":"Partial key exposure attack on short secret exponent\n  CRT-RSA","author":"Alexander May","year":"2021"},{"key":"ref27:may2022approximate","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-031-07082-2_6","article-title":"Approximate divisor multiples\u2013factoring with only a third\n  of the secret CRT-exponents","author":"Alexander May","year":"2022"},{"key":"ref28:meers2023solving","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-981-99-8730-6_2","article-title":"Solving the Hidden Number Problem for CSIDH and CSURF\n  via Automated Coppersmith","volume":"14441","author":"Jonas Meers","year":"2023"},{"key":"ref29:lu2015solving","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-662-48797-6_9","article-title":"Solving linear equations modulo unknown divisors:\n  revisited","author":"Yao Lu","year":"2015"},{"key":"ref30:bleichenbacher1998chosen","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFB0055716","article-title":"Chosen ciphertext attacks against protocols based on the\n  RSA encryption standard PKCS# 1","author":"Daniel Bleichenbacher","year":"1998"},{"key":"ref31:machie2013network","volume-title":"Network security traceback attack and react in the United\n  States Department of Defense network","author":"Edmond K Machie","year":"2013"},{"key":"ref32:de2002cryptanalysis","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/S002000100088","article-title":"Cryptanalysis of RSA with Small Prime Difference","volume":"13","author":"Benne de Weger","year":"2002","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"ref33:micheli2024recovering","doi-asserted-by":"publisher","DOI":"10.62056\/ahjbksdja","article-title":"Survey: Recovering cryptographic keys from partial\n  information, by example","volume":"1","author":"Gabrielle De Micheli","year":"2024","journal-title":"IACR Communications in Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/3006-5496","issn-type":"electronic"},{"key":"ref34:ryan23fast","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-38548-3_1","article-title":"Fast Practical Lattice Reduction Through Iterated\n  Compression","volume":"14083","author":"Keegan Ryan","year":"2023"},{"key":"ref35:boudot2020comparing","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-030-56880-1_3","article-title":"Comparing the difficulty of factorization and discrete\n  logarithm: a 240-digit experiment","author":"Fabrice Boudot","year":"2020"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:30Z","timestamp":1733866110000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":35,"URL":"https:\/\/doi.org\/10.62056\/ahjbhey6b","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-85"}}