{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:05:03Z","timestamp":1753895103756,"version":"3.41.2"},"reference-count":27,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,6,26]],"date-time":"2024-06-26T00:00:00Z","timestamp":1719360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62472438"],"award-info":[{"award-number":["62472438"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172433"],"award-info":[{"award-number":["62172433"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006407","name":"Natural Science Foundation of Henan Province","doi-asserted-by":"publisher","award":["242300421414"],"award-info":[{"award-number":["242300421414"]}],"id":[{"id":"10.13039\/501100006407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>At PKC 2009, May and Ritzenhofen proposed the implicit factorization problem (IFP). They showed that it is undemanding to factor two h-bit RSA moduli N1=p1q1, N2=p2q2 where q1, q2 are both \u03b1h-bit, and p1, p2 share uh&gt;2\u03b1h the least significant bits (LSBs). Subsequent works mainly focused on extending the IFP to the cases where p1, p2 share some of the most significant bits (MSBs) or the middle bits (MBs). In this paper, we propose a novel generalized IFP where p1 and p2 share an arbitrary number of bit blocks, with each block having a consistent displacement in its position between p1 and p2, and we solve it successfully based on Coppersmith\u2019s method. Specifically, we generate a new set of shift polynomials to construct the lattice and optimize the structure of the lattice by introducing a new variable z=p1. We derive that we can factor the two moduli in polynomial time when u&gt;2(n+1)\u03b1(1\u2212\u03b1^1\/(n+1)) with p1, p2 sharing n blocks. Further, no matter how many blocks are shared, we can theoretically factor the two moduli as long as u&gt;2\u03b1ln(1\/\u03b1). In addition, we consider two other cases where the positions of the shared blocks are arbitrary or there are k&gt;2 known moduli. Meanwhile, we provide the corresponding solutions for the two cases. Our work is verified by experiments. <\/jats:p>","DOI":"10.62056\/anjbhey6b","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":0,"title":["Implicit Factorization with Shared Any Bits"],"prefix":"10.62056","author":[{"given":"Chunzhi","family":"Zhao","sequence":"first","affiliation":[{"name":"Information Engineering University","place":["Zhengzhou, 450001, China"]}]},{"given":"Junqi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Information Engineering University","place":["Zhengzhou, 450001, China"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9168-2438","authenticated-orcid":false,"given":"Jinzheng","family":"Cao","sequence":"additional","affiliation":[{"name":"Information Engineering University","place":["Zhengzhou, 450001, China"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6149-4807","authenticated-orcid":false,"given":"Qingfeng","family":"Cheng","sequence":"additional","affiliation":[{"name":"Information Engineering University","place":["Zhengzhou, 450001, China"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2790-7254","authenticated-orcid":false,"given":"Fushan","family":"Wei","sequence":"additional","affiliation":[{"name":"Information Engineering University","place":["Zhengzhou, 450001, China"]}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:RSA1978","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":"R. L. Rivest","year":"1978","journal-title":"Commun. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0001-0782","issn-type":"electronic"},{"key":"ref2:Copper1996","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","author":"Don Coppersmith","year":"1996"},{"key":"ref3:LLL1982","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring Polynomials with Rational Coefficients.","volume":"261","author":"W Lenstra H","year":"1982","journal-title":"Mathematische Annalen"},{"key":"ref4:Copper1997","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":"Journal of Cryptology"},{"key":"ref5:BM2003","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","author":"Johannes Bl\u00f6mer","year":"2003"},{"key":"ref6:JM2006","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/11935230_18","article-title":"A Strategy for Finding Roots of Multivariate Polynomials\n  with New Applications in Attacking RSA Variants","author":"Ellen Jochemsz","year":"2006"},{"key":"ref7:MNS2022","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-031-07082-2_6","article-title":"Approximate Divisor Multiples \u2013 Factoring\n  with\u00a0Only\u00a0a\u00a0Third of\u00a0the\u00a0Secret CRT-Exponents","author":"Alexander May","year":"2022"},{"key":"ref8:MR2009","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","author":"Alexander May","year":"2009"},{"key":"ref9:FMR2010","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-642-13013-7_5","article-title":"Implicit Factoring with Shared Most Significant and Middle\n  Bits","author":"Jean-Charles Faug\u00e8re","year":"2010"},{"key":"ref10:HR2023","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-031-31368-4_6","article-title":"The Hidden Number Problem with\u00a0Small Unknown Multipliers:\n  Cryptanalyzing MEGA in\u00a0Six Queries and\u00a0Other Applications","author":"Nadia Heninger","year":"2023"},{"key":"ref11:SM2011","doi-asserted-by":"publisher","first-page":"4002","DOI":"10.1109\/TIT.2011.2137270","article-title":"Approximate Integer Common Divisor Problem Relates to\n  Implicit Factorization","volume":"57","author":"S. Sarkar","year":"2011","journal-title":"IEEE Trans. Inf. Theor."},{"key":"ref12:LZL2013","doi-asserted-by":"publisher","first-page":"243","DOI":"10.3934\/amc.2013.7.243","article-title":"Improved bounds for the implicit factorization problem","volume":"7","author":"Yao Lu","year":"2013","journal-title":"Adv. Math. Commun."},{"key":"ref13:SLH2014","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-319-01766-2_30","article-title":"Implicit Factoring with Shared Middle Discrete Bits","author":"Meng Shi","year":"2014"},{"key":"ref14:PHL2015","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-22425-1_5","article-title":"Implicit Factorization of RSA Moduli Revisited (Short\n  Paper)","author":"Liqiang Peng","year":"2015"},{"key":"ref15:LPZ2016","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/978-3-319-31301-6_26","article-title":"Towards Optimal Bounds for Implicit Factorization Problem","author":"Yao Lu","year":"2016"},{"key":"ref16:WQL2017","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-017-9176-5","article-title":"A better bound for implicit factorization problem with\n  shared middle bits","volume":"61","author":"Shixiong Wang","year":"2017","journal-title":"Science China Information Sciences"},{"key":"ref17:FNP2023","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-031-53368-6_18","article-title":"Generalized Implicit Factorization Problem","author":"Yansong Feng","year":"2024"},{"key":"ref18:HM2008","isbn-type":"print","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-540-89255-7_25","article-title":"Solving Linear Equations Modulo Divisors: On Factoring Given\n  Any Bits","author":"Mathias Herrmann","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540892557"},{"key":"ref19:PHX2014","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-319-06734-6_11","article-title":"Further Improvement of Factoring RSA Moduli with Implicit\n  Hint","author":"Liqiang Peng","year":"2014"},{"key":"ref20:NA2015","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s12190-014-0806-1","article-title":"Implicit factorization of unbalanced RSA moduli","volume":"48","author":"Abderrahmane Nitaj","year":"2015","journal-title":"Journal of Applied Mathematics and Computing"},{"key":"ref21:SZZ2019","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-981-13-7123-3_34","article-title":"A Method for Solving Generalized Implicit Factorization\n  Problem","author":"Zhelei Sun","year":"2019"},{"key":"ref22:ZM2023","doi-asserted-by":"publisher","first-page":"103562","DOI":"10.1016\/j.jisa.2023.103562","article-title":"Generalized implicit-key attacks on RSA","volume":"77","author":"Mengce Zheng","year":"2023","journal-title":"Journal of Information Security and Applications"},{"key":"ref23:Sarka","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-25578-6_7","article-title":"Partial Key Exposure: Generalized Framework to Attack\n  RSA","author":"Santanu Sarkar","year":"2011"},{"volume-title":"New RSA vulnerabilities using lattice reduction methods.","year":"2003","author":"Alexander May","key":"ref24:MAY2003"},{"key":"ref25:HG1997","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BFb0024458","article-title":"Finding small roots of univariate modular equations\n  revisited","author":"Nicholas Howgrave-Graham","year":"1997"},{"key":"ref26:NS2005","isbn-type":"print","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/11426639_13","article-title":"Floating-Point LLL Revisited","author":"Phong Q. Ngu\u00ean","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540320555"},{"key":"ref27:AONO2013","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-39059-3_7","article-title":"Minkowski Sum Based Lattice Construction for Multivariate\n  Simultaneous Coppersmith's Technique and Applications to RSA","author":"Yoshinori Aono","year":"2013"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:09Z","timestamp":1733866089000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":27,"URL":"https:\/\/doi.org\/10.62056\/anjbhey6b","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-06-26","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-21"}}