{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T05:04:56Z","timestamp":1744261496058,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T00:00:00Z","timestamp":1725235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T00:00:00Z","timestamp":1725235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R &D Program of China","doi-asserted-by":"crossref","award":["2022YFB3103800"],"award-info":[{"award-number":["2022YFB3103800"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1936209","62002353","62202231","62202230"],"award-info":[{"award-number":["U1936209","62002353","62202231","62202230"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2021M701726"],"award-info":[{"award-number":["2021M701726"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Jiangsu Funding Program for Excellent Postdoctoral Talent","award":["2022ZB270"],"award-info":[{"award-number":["2022ZB270"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Partial key exposure attacks present a significant threat to RSA-type cryptosystems. These attacks factorize the RSA modulus by utilizing partial knowledge of the decryption exponent, which is typically revealed by side-channel attacks, cold boot attacks, etc. In practice, the RSA implementations typically employ countermeasures to resist physical attacks, such as additive exponent blinding <jats:inline-formula><jats:alternatives><jats:tex-math>$$d' = d + r \\varphi (N)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>\u2032<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mi>\u03c6<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>N<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with unknown random blinding factor <jats:italic>r<\/jats:italic>. Although there are a couple of partial key exposure attacks on blinding RSA, these attacks require a considerable amount of leakage and fail to work when <jats:italic>e<\/jats:italic> is up to full size. In this paper, we propose new partial key exposure attacks on RSA with additive exponent blinding, focusing on leakage scenarios where the Most Significant Bits (MSBs) or Least Significant Bits (LSBs) of <jats:inline-formula><jats:alternatives><jats:tex-math>$$d'$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>\u2032<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are revealed. For the case where <jats:italic>e<\/jats:italic> is small, we first recover partial information of <jats:italic>p<\/jats:italic> by solving the quadratic congruence equation, and then find the small roots of the integer equation to recover entire private key. Our method relaxes the attack requirements, for instance, we reduce the amount of MSBs for a successful attack from 75 to 25% when <jats:inline-formula><jats:alternatives><jats:tex-math>$$e \\approx N^{0.25}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>e<\/mml:mi>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>N<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>0.25<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$r\\approx N^{0}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>N<\/mml:mi>\n                      <mml:mn>0<\/mml:mn>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Furthermore, we propose new attacks using the unique algebraic relationship in blinding RSA, which extend the attack to the case where <jats:italic>e<\/jats:italic> is of full size.<\/jats:p>","DOI":"10.1186\/s42400-024-00214-y","type":"journal-article","created":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T03:16:18Z","timestamp":1725246978000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["New partial key exposure attacks on RSA with additive exponent blinding"],"prefix":"10.1186","volume":"7","author":[{"given":"Ziming","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongbin","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuejun","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,2]]},"reference":[{"key":"214_CR1","doi-asserted-by":"crossref","unstructured":"Aono Y (2009) A new lattice construction for partial key exposure attack for RSA. In: Public key cryptography\u2014PKC 2009, 12th international conference on practice and theory in public key cryptography, Irvine, CA, USA, March 18\u201320, 2009. Proceedings, pp 34\u201353","DOI":"10.1007\/978-3-642-00468-1_3"},{"key":"214_CR2","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer J, May A (2003) New partial key exposure attacks on RSA. In: Advances in cryptology\u2014CRYPTO 2003, 23rd annual international cryptology conference, Santa Barbara, California, USA, August 17\u201321, 2003, Proceedings, pp 27\u201343","DOI":"10.1007\/978-3-540-45146-4_2"},{"key":"214_CR3","first-page":"203","volume":"46","author":"D Boneh","year":"2002","unstructured":"Boneh D (2002) Twenty years of attacks on the RSA cryptosystem. Notices o Ams 46:203\u2013213","journal-title":"Notices o Ams"},{"key":"214_CR4","doi-asserted-by":"crossref","unstructured":"Boneh D, Durfee G, Frankel Y (1998) An attack on RSA given a small fraction of the private key bits. In: Advances in cryptology\u2014ASIACRYPT \u201998, international conference on the theory and applications of cryptology and information security, Beijing, China, October 18\u201322, 1998, Proceedings, pp 25\u201334","DOI":"10.1007\/3-540-49649-1_3"},{"key":"214_CR5","unstructured":"Botan (2023) Botan, a Crypto and TLS for Modern C++ library, Version: 3.2.0. https:\/\/github.com\/randombit\/botan. https:\/\/github.com\/randombit\/botan\/blob\/master\/src\/lib\/pubkey\/rsa\/rsa.cpp"},{"key":"214_CR6","doi-asserted-by":"crossref","unstructured":"Cimato S, Mella S, Susella R (2015) New results for partial key exposure on RSA with exponent blinding. In: SECRYPT 2015: Proceedings of the 12th international conference on security and cryptography, Colmar, Alsace, France, 20\u201322 July, 2015, pp 136\u2013147","DOI":"10.5220\/0005571701360147"},{"key":"214_CR7","doi-asserted-by":"crossref","unstructured":"Cimato S, Mella S, Susella R (2015) Partial key exposure attacks on RSA with exponent blinding. In: E-business and telecommunications: 12th international joint conference, ICETE 2015, Colmar, France, July 20\u201322, 2015, Revised Selected Papers, pp 364\u2013385","DOI":"10.1007\/978-3-319-30222-5_17"},{"key":"#cr-split#-214_CR8.1","doi-asserted-by":"crossref","unstructured":"Coppersmith D (1996) Finding a small root of a bivariate integer equation","DOI":"10.1007\/3-540-68339-9_16"},{"key":"#cr-split#-214_CR8.2","unstructured":"factoring with high bits known. In: Advances in cryptology-EUROCRYPT '96, international conference on the theory and application of cryptographic techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, pp 178-189"},{"key":"214_CR9","doi-asserted-by":"crossref","unstructured":"Coppersmith D (1996) Finding a small root of a univariate modular equation. In: Advances in Cryptology\u2014EUROCRYPT \u201996, international conference on the theory and application of cryptographic techniques, Saragossa, Spain, May 12\u201316, 1996, Proceeding, pp 155\u2013165","DOI":"10.1007\/3-540-68339-9_14"},{"key":"214_CR10","doi-asserted-by":"crossref","unstructured":"Coron J (2004) Finding small roots of bivariate integer polynomial equations revisited. In: Advances in cryptology\u2014EUROCRYPT 2004, international conference on the theory and applications of cryptographic techniques, Interlaken, Switzerland, May 2\u20136, 2004, Proceedings, pp 492\u2013505","DOI":"10.1007\/978-3-540-24676-3_29"},{"key":"214_CR11","doi-asserted-by":"crossref","unstructured":"Ernst M, Jochemsz E, May A, Weger B (2005) Partial key exposure attacks on RSA up to full size exponents. In: Advances in cryptology\u2014 EUROCRYPT 2005, 24th annual international conference on the theory and applications of cryptographic techniques, Aarhus, Denmark, May 22\u201326, 2005, Proceedings, pp 371\u2013386","DOI":"10.1007\/11426639_22"},{"key":"214_CR12","doi-asserted-by":"crossref","unstructured":"Herrmann M, May A (2008) Solving linear equations modulo divisors: on factoring given any bits. In: Advances in cryptology\u2014ASIACRYPT 2008, 14th international conference on the theory and application of cryptology and information security, Melbourne, Australia, December 7\u201311, 2008. Proceedings, pp 406\u2013424","DOI":"10.1007\/978-3-540-89255-7_25"},{"key":"214_CR13","doi-asserted-by":"publisher","DOI":"10.1201\/9781420075199","volume-title":"Cryptanalysis of RSA and its variants","author":"MJ Hinek","year":"2009","unstructured":"Hinek MJ (2009) Cryptanalysis of RSA and its variants. CRC Press, New York"},{"key":"214_CR14","doi-asserted-by":"crossref","unstructured":"Howgrave-Graham N (1997) Finding small roots of univariate modular equations revisited. In: Cryptography and coding, 6th IMA international conference, Cirencester, UK, December 17\u201319, 1997, Proceedings, pp 131\u2013142","DOI":"10.1007\/BFb0024458"},{"key":"214_CR15","doi-asserted-by":"crossref","unstructured":"Jochemsz E, May A (2006) A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. In: Advances in cryptology\u2014ASIACRYPT 2006, 12th international conference on the theory and application of cryptology and information security, Shanghai, China, December 3\u20137, 2006, Proceedings, pp 267\u2013282","DOI":"10.1007\/11935230_18"},{"key":"214_CR16","doi-asserted-by":"crossref","unstructured":"Joye M, Lepoint T (2012) Partial key exposure on RSA with private exponents larger than N. In: Information security practice and experience: 8th international conference, ISPEC 2012, Hangzhou, China, April 9\u201312, 2012. Proceedings, pp 369\u2013380","DOI":"10.1007\/978-3-642-29101-2_25"},{"key":"214_CR17","doi-asserted-by":"crossref","unstructured":"Kocher PC (1996) Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Advances in cryptology\u2014CRYPTO \u201996, 16th annual international cryptology conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings, pp 104\u2013113","DOI":"10.1007\/3-540-68697-5_9"},{"issue":"4","key":"214_CR18","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra AK, Lenstra HW, Lov\u00e1sz L (1982) Factoring polynomials with rational coefficients. Math Ann 261(4):515\u2013534","journal-title":"Math Ann"},{"key":"214_CR19","unstructured":"Libgcrypt (2021) Libgcrypt, the gnu crypto library, Version: 1.9. https:\/\/github.com\/gpg\/libgcrypt. https:\/\/github.com\/gpg\/libgcrypt\/blob\/master\/cipher\/rsa.c"},{"key":"214_CR20","unstructured":"MbedTLS (2023) MbedTLS, a TLS and SSL library, Version: 3.5.1. https:\/\/github.com\/Mbed-TLS\/mbedtls, available at https:\/\/github.com\/Mbed-TLS\/mbedtls\/blob\/development\/library\/rsa.c"},{"key":"214_CR21","doi-asserted-by":"crossref","unstructured":"Novak R (2002) SPA-based adaptive chosen-ciphertext attack on RSA implementation. In: Public key cryptography, 5th International workshop on practice and theory in public key cryptosystems, PKC 2002, Paris, France, February 12\u201314, 2002, Proceedings, pp 252\u2013262","DOI":"10.1007\/3-540-45664-3_18"},{"issue":"2","key":"214_CR22","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest RL, Shamir A, Adleman LM (1978) A method for obtaining digital signatures and public-key cryptosystems. Commun ACM 21(2):120\u2013126","journal-title":"Commun ACM"},{"key":"214_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139165464","volume-title":"A computational introduction to number theory and algebra","author":"V Shoup","year":"2005","unstructured":"Shoup V (2005) A computational introduction to number theory and algebra. Cambridge University Press, Cambridge"},{"key":"214_CR24","doi-asserted-by":"crossref","unstructured":"Steinfeld R, Zheng Y (2001) An advantage of low-exponent RSA with modulus primes sharing least significant bits. In: Topics in cryptology\u2014CT-RSA 2001, The cryptographer\u2019s Track at RSA conference 2001, San Francisco, CA, USA, April 8\u201312, 2001, Proceedings, pp 52\u201362","DOI":"10.1007\/3-540-45353-9_5"},{"key":"214_CR25","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2020.07.004","volume":"841","author":"K Suzuki","year":"2020","unstructured":"Suzuki K, Takayasu A, Kunihiro N (2020) Extended partial key exposure attacks on RSA: improvement up to full size decryption exponents. Theor Comput Sci 841:62\u201383","journal-title":"Theor Comput Sci"},{"key":"214_CR26","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2018.08.021","volume":"761","author":"A Takayasu","year":"2019","unstructured":"Takayasu A, Kunihiro N (2019) Partial key exposure attacks on RSA: achieving the Boneh\u2013Durfee bound. Theor Comput Sci 761:51\u201377","journal-title":"Theor Comput Sci"},{"key":"214_CR27","doi-asserted-by":"crossref","unstructured":"Takayasu A, Kunihiro N (2014) Partial key exposure attacks on RSA: achieving the Boneh-Durfee bound. In: Selected areas in cryptography: SAC 2014\u201421st international conference, Montreal, QC, Canada, August 14\u201315, 2014, Revised Selected Papers, pp 345\u2013362","DOI":"10.1007\/978-3-319-13051-4_21"},{"key":"214_CR28","doi-asserted-by":"crossref","unstructured":"Zhou Y, Pol J, Yu Y, Standaert F (2022) A third is all you need: Extended partial key exposure attack on CRT-RSA with additive exponent blinding. In: Advances in cryptology: ASIACRYPT 2022\u201428th international conference on the theory and application of cryptology and information security, Taipei, Taiwan, December 5\u20139, 2022, Proceedings, Part IV, pp 508\u2013536","DOI":"10.1007\/978-3-031-22972-5_18"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00214-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-024-00214-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00214-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T03:23:59Z","timestamp":1725247439000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-024-00214-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,2]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["214"],"URL":"https:\/\/doi.org\/10.1186\/s42400-024-00214-y","relation":{},"ISSN":["2523-3246"],"issn-type":[{"type":"electronic","value":"2523-3246"}],"subject":[],"published":{"date-parts":[[2024,9,2]]},"assertion":[{"value":"17 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"26"}}