{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:06Z","timestamp":1759638606245,"version":"3.37.3"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,2]]},"abstract":"<jats:p> Let [Formula: see text] be an RSA public key with private exponent [Formula: see text] where [Formula: see text] and [Formula: see text] are large primes of the same bit size. At Eurocrypt 96, Coppersmith presented a polynomial-time algorithm for finding small roots of univariate modular equations based on lattice reduction and then succussed to factorize the RSA modulus. Since then, a series of attacks on the key equation [Formula: see text] of RSA have been presented. In this paper, we show that many of such attacks can be unified in a single attack using a new notion called Coppersmith\u2019s interval. We determine a Coppersmith\u2019s interval for a given RSA public key [Formula: see text] The interval is valid for any variant of RSA, such as Multi-Prime RSA, that uses the key equation. Then we show that RSA is insecure if [Formula: see text] provided that we have approximation [Formula: see text] of [Formula: see text] with [Formula: see text] [Formula: see text] The attack is an extension of Coppersmith\u2019s result. <\/jats:p>","DOI":"10.1142\/s0129054120500045","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T09:17:18Z","timestamp":1583745438000},"page":"207-231","source":"Crossref","is-referenced-by-count":6,"title":["A Unified Method for Private Exponent Attacks on RSA Using Lattices"],"prefix":"10.1142","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8137-7939","authenticated-orcid":false,"given":"Hatem M.","family":"Bahig","sequence":"first","affiliation":[{"name":"Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}]},{"given":"Dieaa I.","family":"Nassr","sequence":"additional","affiliation":[{"name":"Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}]},{"given":"Ashraf","family":"Bhery","sequence":"additional","affiliation":[{"name":"Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}]},{"given":"Abderrahmane","family":"Nitaj","sequence":"additional","affiliation":[{"name":"Laboratoire de Math\u00e9matiques Nicolas Oresme, Universit\u00e9 de Caen, Basse Normandie, France"}]}],"member":"219","published-online":{"date-parts":[[2020,3,6]]},"reference":[{"key":"S0129054120500045BIB001","first-page":"159","volume":"2003","author":"Alison C.","year":"2003","journal-title":"IACR Cryptology ePrint Archive"},{"key":"S0129054120500045BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34129-8_4"},{"key":"S0129054120500045BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/18.850673"},{"key":"S0129054120500045BIB004","first-page":"1","volume":"5","author":"Boneh D.","year":"2002","journal-title":"CryptoBytes"},{"key":"S0129054120500045BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900030"},{"key":"S0129054120500045BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s002000100088"},{"key":"S0129054120500045BIB009","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/3-540-36492-7_25","volume-title":"Selected Areas in Cryptography","volume":"2595","author":"Hinek J.","year":"2002"},{"key":"S0129054120500045BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0024458"},{"key":"S0129054120500045BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/11935230_18"},{"key":"S0129054120500045BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"S0129054120500045BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85886-7_16"},{"key":"S0129054120500045BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/AICCSA.2008.4493604"},{"key":"S0129054120500045BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68164-9_12"},{"key":"S0129054120500045BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06734-6_12"},{"key":"S0129054120500045BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"S0129054120500045BIB020","first-page":"315","volume-title":"IACR Cryptology ePrint Archive","volume":"2008","author":"Sarkar S.","year":"2008"},{"key":"S0129054120500045BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-004-0164-6"},{"key":"S0129054120500045BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89641-8_4"},{"key":"S0129054120500045BIB023","first-page":"3","volume-title":"Information Security and Cryptology - ICISC 2014 - 17th International Conference","author":"Takayasu A.","year":"2014"},{"key":"S0129054120500045BIB024","doi-asserted-by":"publisher","DOI":"10.1109\/18.54902"},{"key":"S0129054120500045BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39059-3_4"},{"key":"S0129054120500045BIB026","doi-asserted-by":"publisher","DOI":"10.1587\/transfun.E97.A.1533"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120500045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T09:17:29Z","timestamp":1583745449000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120500045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2]]},"references-count":22,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["10.1142\/S0129054120500045"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120500045","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2020,2]]}}}