{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:39:43Z","timestamp":1775839183620,"version":"3.50.1"},"reference-count":21,"publisher":"Walter de Gruyter GmbH","issue":"2","license":[{"start":{"date-parts":[[2017,5,16]],"date-time":"2017-05-16T00:00:00Z","timestamp":1494892800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61472417"],"award-info":[{"award-number":["61472417"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,6,1]]},"abstract":"Abstract<\/jats:title>\n \n In this paper we study an RSA variant with moduli of the form\n \n \n \n \n N<\/m:mi>\n =<\/m:mo>\n \n \n p<\/m:mi>\n r<\/m:mi>\n <\/m:msup>\n \u2062<\/m:mo>\n \n q<\/m:mi>\n l<\/m:mi>\n <\/m:msup>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n {N=p^{r}q^{l}}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n (\n \n \n \n \n r<\/m:mi>\n ><\/m:mo>\n l<\/m:mi>\n \u2265<\/m:mo>\n 2<\/m:mn>\n <\/m:mrow>\n <\/m:math>\n {r>l\\geq 2}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ).\nThis variant was mentioned by Boneh, Durfee and Howgrave-Graham [2]. Later Lim, Kim, Yie and Lee [11] showed that this variant is much faster than the standard RSA moduli in the step of decryption procedure. There are two proposals of RSA variants when\n \n \n \n \n N<\/m:mi>\n =<\/m:mo>\n \n \n p<\/m:mi>\n r<\/m:mi>\n <\/m:msup>\n \u2062<\/m:mo>\n \n q<\/m:mi>\n l<\/m:mi>\n <\/m:msup>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n {N=p^{r}q^{l}}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . In the first proposal, the encryption exponent\n e<\/jats:italic>\n and the decryption exponent\n d<\/jats:italic>\n satisfy\n \n \n \n \n \n e<\/m:mi>\n \u2062<\/m:mo>\n d<\/m:mi>\n <\/m:mrow>\n \u2261<\/m:mo>\n \n 1<\/m:mn>\n mod<\/m:mo>\n \n \n p<\/m:mi>\n \n r<\/m:mi>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n <\/m:msup>\n \u2062<\/m:mo>\n \n q<\/m:mi>\n \n l<\/m:mi>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n <\/m:msup>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n p<\/m:mi>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n q<\/m:mi>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n ed\\equiv 1\\bmod p^{r-1}q^{l-1}(p-1)(q-1)<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , whereas in the second proposal\n \n \n \n \n \n e<\/m:mi>\n \u2062<\/m:mo>\n d<\/m:mi>\n <\/m:mrow>\n \u2261<\/m:mo>\n \n 1<\/m:mn>\n mod<\/m:mo>\n \n \n (<\/m:mo>\n \n p<\/m:mi>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n q<\/m:mi>\n -<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n ed\\equiv 1\\bmod(p-1)(q-1)<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We prove that for the first case if\n \n \n \n \n d<\/m:mi>\n <<\/m:mo>\n \n N<\/m:mi>\n \n 1<\/m:mn>\n -<\/m:mo>\n \n \n (<\/m:mo>\n \n \n 3<\/m:mn>\n \u2062<\/m:mo>\n r<\/m:mi>\n <\/m:mrow>\n +<\/m:mo>\n l<\/m:mi>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n \u2062<\/m:mo>\n \n \n (<\/m:mo>\n \n r<\/m:mi>\n +<\/m:mo>\n l<\/m:mi>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n \n -<\/m:mo>\n 2<\/m:mn>\n <\/m:mrow>\n <\/m:msup>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:msup>\n <\/m:mrow>\n <\/m:math>\n {d<N^{1-({3r+l}){(r+l)^{-2}}}}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , one can factor\n N<\/jats:italic>\n in polynomial time. We also show that polynomial time factorization is possible if\n \n \n \n \n d<\/m:mi>\n <<\/m:mo>\n \n N<\/m:mi>\n \n \n (<\/m:mo>\n \n 7<\/m:mn>\n -<\/m:mo>\n \n 2<\/m:mn>\n \u2062<\/m:mo>\n \n 7<\/m:mn>\n <\/m:msqrt>\n <\/m:mrow>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n \/<\/m:mo>\n \n (<\/m:mo>\n \n 3<\/m:mn>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n r<\/m:mi>\n +<\/m:mo>\n l<\/m:mi>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:msup>\n <\/m:mrow>\n <\/m:math>\n {d<N^{({7-2\\sqrt{7}})\/{(3(r+l))}}}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for the second case. Finally, we study the case when few bits of one prime are known to the attacker for this variant of RSA. We show that given\n \n \n \n \n \n min<\/m:mi>\n \u2061<\/m:mo>\n \n (<\/m:mo>\n \n l<\/m:mi>\n \n r<\/m:mi>\n +<\/m:mo>\n l<\/m:mi>\n <\/m:mrow>\n <\/m:mfrac>\n ,<\/m:mo>\n \n \n 2<\/m:mn>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n r<\/m:mi>\n -<\/m:mo>\n l<\/m:mi>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n \n r<\/m:mi>\n +<\/m:mo>\n l<\/m:mi>\n <\/m:mrow>\n <\/m:mfrac>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n \u2062<\/m:mo>\n \n \n log<\/m:mi>\n 2<\/m:mn>\n <\/m:msub>\n \u2061<\/m:mo>\n p<\/m:mi>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n {\\min(\\frac{l}{r+l},\\frac{2(r-l)}{r+l})\\log_{2}p}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n least significant bits of one prime, one can factor\n N<\/jats:italic>\n in polynomial time.\n <\/jats:p>","DOI":"10.1515\/jmc-2016-0025","type":"journal-article","created":{"date-parts":[[2017,5,16]],"date-time":"2017-05-16T06:00:31Z","timestamp":1494914431000},"page":"117-130","source":"Crossref","is-referenced-by-count":17,"title":["Cryptanalysis of an RSA variant with moduli\n N<\/i>\n =\n \n p\n r<\/sup>\n q\n l<\/sup>\n <\/i>"],"prefix":"10.1515","volume":"11","author":[{"given":"Yao","family":"Lu","sequence":"first","affiliation":[{"name":"The University of Tokyo , Tokyo , Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liqiang","family":"Peng","sequence":"additional","affiliation":[{"name":"Institute of Information Engineering , Chinese Academy of Sciences , Beijing , P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santanu","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology , Madras , India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2017,5,16]]},"reference":[{"key":"2025120600314644456_j_jmc-2016-0025_ref_001_w2aab3b7e1546b1b6b1ab2ab1Aa","doi-asserted-by":"crossref","unstructured":"D. Boneh and G. Durfee,\nCryptanalysis of RSA with private key d less than N0.292{{{N}}^{0.292}},\nIEEE Trans. Inform. Theory 46 (2000), no. 4, 1339\u20131349.","DOI":"10.1109\/18.850673"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_002_w2aab3b7e1546b1b6b1ab2ab2Aa","unstructured":"D. Boneh, G. Durfee and N. Howgrave-Graham,\nFactoring N=pr\u2062q{{N}=p^{r}q} for large r,\nAdvances in Cryptology \u2013 CRYPTO 1999,\nLecture Notes in Comput. Sci. 1666,\nSpringer, Berlin (1999), 787\u2013787."},{"key":"2025120600314644456_j_jmc-2016-0025_ref_003_w2aab3b7e1546b1b6b1ab2ab3Aa","doi-asserted-by":"crossref","unstructured":"D. Coppersmith,\nSmall solutions to polynomial equations, and low exponent RSA vulnerabilities,\nJ. Cryptologyy 10 (1997), no. 4, 233\u2013260.","DOI":"10.1007\/s001459900030"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_004_w2aab3b7e1546b1b6b1ab2ab4Aa","doi-asserted-by":"crossref","unstructured":"J. S. Coron, J. C. Faug\u00e8re, G. Renault and R. Zeitoun,\nFactoring N=pr\u2062qs{{N}=p^{r}q^{s}} for large r and s,\nTopics in Cryptology \u2013 CT-RSA 2016,\nLecture Notes in Comput. Sci. 9610,\nSpringer, Berlin (2016), 448\u2013464;\nhttps:\/\/eprint.iacr.org\/2015\/071.","DOI":"10.1007\/978-3-319-29485-8_26"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_005_w2aab3b7e1546b1b6b1ab2ab5Aa","doi-asserted-by":"crossref","unstructured":"M. Herrmann and A. May,\nSolving linear equations modulo divisors: On factoring given any bits,\nAdvances in Cryptology \u2013 ASIACRYPT 2008,\nLecture Notes in Comput. Sci. 5350,\nSpringer, Berlin (2008), 406\u2013424.","DOI":"10.1007\/978-3-540-89255-7_25"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_006_w2aab3b7e1546b1b6b1ab2ab6Aa","doi-asserted-by":"crossref","unstructured":"M. Herrmann and A. May,\nMaximizing small root bounds by linearization and applications to small secret exponent RSA,\nPublic Key Cryptography \u2013 PKC 2010,\nLecture Notes in Comput. Sci. 6056,\nSpringer, Berlin (2010), 53\u201369.","DOI":"10.1007\/978-3-642-13013-7_4"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_007_w2aab3b7e1546b1b6b1ab2ab7Aa","doi-asserted-by":"crossref","unstructured":"N. Howgrave-Graham,\nFinding small roots of univariate modular equations revisited,\nCrytography and Coding \u2013 IMACC 1997,\nLecture Notes in Comput. Sci. 1355,\nSpringer, Berlin (1997), 131\u2013142.","DOI":"10.1007\/BFb0024458"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_008_w2aab3b7e1546b1b6b1ab2ab8Aa","doi-asserted-by":"crossref","unstructured":"K. Itoh, N. Kunihiro and K. Kurosawa,\nSmall secret key attack on a variant of RSA (due to Takagi),\nTopics in Cryptology \u2013 CT-RSA 2008,\nLecture Notes in Comput. Sci. 4964,\nSpringer, Berlin (2008), 387\u2013406.","DOI":"10.1007\/978-3-540-79263-5_25"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_009_w2aab3b7e1546b1b6b1ab2ab9Aa","doi-asserted-by":"crossref","unstructured":"N. Kunihiro, N. Shinohara and T. Izu,\nA unified framework for small secret exponent attack on RSA,\nSelected Areas in Cryptography \u2013 SAC 2011,\nLecture Notes in Comput. Sci. 7118,\nSpringer, Berlin (2012), 260\u2013277.","DOI":"10.1007\/978-3-642-28496-0_16"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_010_w2aab3b7e1546b1b6b1ab2ac10Aa","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra, H. W. Lenstra and L. Lov\u00e1sz,\nFactoring polynomials with rational coefficients,\nMath. Ann. 261 (1982), no. 4, 515\u2013534.","DOI":"10.1007\/BF01457454"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_011_w2aab3b7e1546b1b6b1ab2ac11Aa","doi-asserted-by":"crossref","unstructured":"S. Lim, S. Kim, I. Yie and H. Lee.,\n,\nProgress in Cryptology \u2013 INDOCRYPT 2000,\nLecture Notes in Comput. Sci. 1977,\nSpringer, Berlin (2000), 283\u2013294.","DOI":"10.1007\/3-540-44495-5_25"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_012_w2aab3b7e1546b1b6b1ab2ac12Aa","doi-asserted-by":"crossref","unstructured":"Y. Lu, R. Zhang and D. Lin,\nFactoring multi-power RSA modulus N=pr\u2062q{{N}=p^{r}q} with partial known bits,\nInformation Security and Privacy \u2013 ACISP 2013,\nLecture Notes in Comput. Sci. 7959,\nSpringer, Berlin (2013), 57\u201371.","DOI":"10.1007\/978-3-642-39059-3_5"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_013_w2aab3b7e1546b1b6b1ab2ac13Aa","doi-asserted-by":"crossref","unstructured":"Y. Lu, R. Zhang, L. Peng and D. Lin,\nSolving linear equations modulo unknown divisors: revisited,\nAdvances in Cryptology \u2013 ASIACRYPT 2015,\nLecture Notes in Comput. Sci. 9452,\nSpringer, Berlin (2015), 189\u2013213;\nhttps:\/\/eprint.iacr.org\/2014\/343.","DOI":"10.1007\/978-3-662-48797-6_9"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_014_w2aab3b7e1546b1b6b1ab2ac14Aa","doi-asserted-by":"crossref","unstructured":"A. May,\nSecret exponent attacks on RSA-type schemes with moduli N=pr\u2062q{N=p^{r}q},\nPublic Key Cryptography \u2013 PKC 2004,\nLecture Notes in Comput. Sci. 2947,\nSpringer, Berlin (2004), 218\u2013230.","DOI":"10.1007\/978-3-540-24632-9_16"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_015_w2aab3b7e1546b1b6b1ab2ac15Aa","doi-asserted-by":"crossref","unstructured":"T. Okamoto and S. Uchiyama,\nA new public-key cryptosystem as secure as factoring,\nAdvances in Cryptology \u2013 EUROCRYPT 1998,\nLecture Notes in Comput. Sci. 1403,\nSpringer, Berlin (1998), 308\u2013318.","DOI":"10.1007\/BFb0054135"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_016_w2aab3b7e1546b1b6b1ab2ac16Aa","doi-asserted-by":"crossref","unstructured":"R. Rivest and A. Shamir,\nEfficient factoring based on partial information,\nAdvances in Cryptology \u2013 EUROCRYPT 1985,\nLecture Notes in Comput. Sci. 219,\nSpringer, Berlin (1986), 31\u201334.","DOI":"10.1007\/3-540-39805-8_3"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_017_w2aab3b7e1546b1b6b1ab2ac17Aa","doi-asserted-by":"crossref","unstructured":"S. Sarkar,\nSmall secret exponent attack on RSA variant with modulus N=pr\u2062q{N=p^{r}q},\nDes. Codes Cryptogr. 73 (2014), no. 2, 383\u2013392.","DOI":"10.1007\/s10623-014-9928-6"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_018_w2aab3b7e1546b1b6b1ab2ac18Aa","doi-asserted-by":"crossref","unstructured":"T. Takagi,\nFast RSA-type cryptosystems using n-adic expansion,\nAdvances in Cryptology \u2013 CRYPTO 1997,\nLecture Notes in Comput. Sci. 1294,\nSpringer, Berlin (1997), 372\u2013384.","DOI":"10.1007\/BFb0052249"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_019_w2aab3b7e1546b1b6b1ab2ac19Aa","doi-asserted-by":"crossref","unstructured":"T. Takagi,\nFast RSA-type cryptosystem modulo pk\u2062q{p^{k}q},\nAdvances in Cryptology \u2013 CRYPTO 1998,\nLecture Notes in Comput. Sci. 1462,\nSpringer, Berlin (1998), 318\u2013326.","DOI":"10.1007\/BFb0055738"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_020_w2aab3b7e1546b1b6b1ab2ac20Aa","doi-asserted-by":"crossref","unstructured":"M. J. Wiener,\nCryptanalysis of short RSA secret exponents,\nIEEE Trans. Inform. Theory 36 (1990), no. 3, 553\u2013558.","DOI":"10.1109\/18.54902"},{"key":"2025120600314644456_j_jmc-2016-0025_ref_021_w2aab3b7e1546b1b6b1ab2ac21Aa","unstructured":"The EPOC and the ESIGN Algorithms, IEEE P1363: Protocols from other families of Public-Key algorithms, 1998, http:\/\/grouper.ieee.org\/groups\/1363\/StudyGroup\/NewFam.html."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jmc.2017.11.issue-2\/jmc-2016-0025\/jmc-2016-0025.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0025\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0025\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:33:45Z","timestamp":1764981225000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2016-0025\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,16]]},"references-count":21,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,5,16]]},"published-print":{"date-parts":[[2017,6,1]]}},"alternative-id":["10.1515\/jmc-2016-0025"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2016-0025","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"value":"1862-2984","type":"electronic"},{"value":"1862-2976","type":"print"}],"subject":[],"published":{"date-parts":[[2017,5,16]]}}}