Implicit Factorization with Shared Any Bits
Authors
Chunzhi Zhao, Junqi Zhang, Jinzheng Cao, Qingfeng Cheng, Fushan Wei
Jinzheng Cao
Information Engineering University, Zhengzhou, China
caojinzheng at 126 dot com
caojinzheng at 126 dot com
Qingfeng Cheng
Information Engineering University, Zhengzhou, China
qingfengc2008 at sina dot com
qingfengc2008 at sina dot com
Fushan Wei
Information Engineering University, Zhengzhou, China
weifs831020 at 163 dot com
weifs831020 at 163 dot com
Abstract
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 αh-bit, and p1, p2 share uh>2αh 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’s 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>2(n+1)α(1−α^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>2αln(1/α). In addition, we consider two other cases where the positions of the shared blocks are arbitrary or there are k>2 known moduli. Meanwhile, we provide the corresponding solutions for the two cases. Our work is verified by experiments.
References
[Aon13]
Yoshinori Aono. Minkowski Sum Based Lattice Construction for Multivariate Simultaneous Coppersmith's Technique and Applications to RSA. In Colin Boyd and Leonie Simpson, editors, Information Security and Privacy, pages 88–103, Berlin, Heidelberg. 2013. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-39059-3_7
[BM03]
Johannes Blömer and Alexander May. New Partial Key Exposure Attacks on RSA. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, pages 27–43, Berlin, Heidelberg. 2003. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-45146-4_2
[Cop96]
Don Coppersmith. Finding a Small Root of a Univariate Modular Equation. In Ueli Maurer, editor, Advances in Cryptology - EUROCRYPT 1996, pages 155–165, Berlin, Heidelberg. 1996. Springer Berlin Heidelberg. DOI: 10.1007/3-540-68339-9_14
[Cop97]
Don Coppersmith. Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. Journal of Cryptology, 10:233–260, 1997. DOI: 10.1007/s001459900030
[FMR10]
Jean-Charles Faugère, Raphaël Marinier, and Guénaël Renault. Implicit Factoring with Shared Most Significant and Middle Bits. In Phong Q. Nguyen and David Pointcheval, editors, Public Key Cryptography - PKC 2010, pages 70–87, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-13013-7_5
[FNP24]
Yansong Feng, Abderrahmane Nitaj, and Yanbin Pan. Generalized Implicit Factorization Problem. In Claude Carlet, Kalikinkar Mandal, and Vincent Rijmen, editors, Selected Areas in Cryptography - SAC 2023, pages 369–384, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-53368-6_18
[HG97]
Nicholas Howgrave-Graham. Finding small roots of univariate modular equations revisited. In Michael Darnell, editor, Crytography and Coding, pages 131–142, Berlin, Heidelberg. 1997. Springer Berlin Heidelberg. DOI: 10.1007/BFb0024458
[HM08]
Mathias Herrmann and Alexander May. Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits. In Josef Pieprzyk, editor, Advances in Cryptology - ASIACRYPT 2008, pages 406–424, Berlin, Heidelberg. 2008. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-89255-7_25
[HR23]
Nadia Heninger and Keegan Ryan. The Hidden Number Problem with Small Unknown Multipliers: Cryptanalyzing MEGA in Six Queries and Other Applications. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, Public-Key Cryptography - PKC 2023, pages 147–176, Cham. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-31368-4_6
[JM06]
Ellen Jochemsz and Alexander May. A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants. In Xuejia Lai and Kefei Chen, editors, Advances in Cryptology - ASIACRYPT 2006, pages 267–282, Berlin, Heidelberg. 2006. Springer Berlin Heidelberg. DOI: 10.1007/11935230_18
[LLL82]
W Lenstra H, K Lenstra A, and L Lovász. Factoring Polynomials with Rational Coefficients.. Mathematische Annalen, 261:515–534, 1982. DOI: 10.1007/BF01457454
[LPZ+16]
Yao Lu, Liqiang Peng, Rui Zhang, Lei Hu, and Dongdai Lin. Towards Optimal Bounds for Implicit Factorization Problem. In Orr Dunkelman and Liam Keliher, editors, Selected Areas in Cryptography - SAC 2015, pages 462–476, Cham. 2016. Springer International Publishing. DOI: 10.1007/978-3-319-31301-6_26
[LZL13]
Yao Lu, Rui Zhang, and Dongdai Lin. Improved bounds for the implicit factorization problem. Adv. Math. Commun., 7:243–251, 2013. DOI: 10.3934/amc.2013.7.243
[May03]
Alexander May. New RSA vulnerabilities using lattice reduction methods.. PhD thesis, Paderborn University, 2003.
[MNS22]
Alexander May, Julian Nowakowski, and Santanu Sarkar. Approximate Divisor Multiples – Factoring with Only a Third of the Secret CRT-Exponents. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022, pages 147–167, Cham. 2022. Springer International Publishing. DOI: 10.1007/978-3-031-07082-2_6
[MR09]
Alexander May and Maike Ritzenhofen. Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint. In Stanisław Jarecki and Gene Tsudik, editors, Public Key Cryptography - PKC 2009, pages 1–14, Berlin, Heidelberg. 2009. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-00468-1_1
[NA15]
Abderrahmane Nitaj and Muhammad Rezal Kamel Ariffin. Implicit factorization of unbalanced RSA moduli. Journal of Applied Mathematics and Computing, 48:349–363, 2015. DOI: 10.1007/s12190-014-0806-1
[NS05]
Phong Q. Nguên and Damien Stehlé. Floating-Point LLL Revisited. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, pages 215–233, Berlin, Heidelberg. 2005. Springer Berlin Heidelberg. DOI: 10.1007/11426639_13
[PHL+15]
Liqiang Peng, Lei Hu, Yao Lu, Zhangjie Huang, and Jun Xu. Implicit Factorization of RSA Moduli Revisited (Short Paper). In Keisuke Tanaka and Yuji Suga, editors, Advances in Information and Computer Security, pages 67–76, Cham. 2015. Springer International Publishing. DOI: 10.1007/978-3-319-22425-1_5
[PHX+14]
Liqiang Peng, Lei Hu, Jun Xu, Zhangjie Huang, and Yonghong Xie. Further Improvement of Factoring RSA Moduli with Implicit Hint. In David Pointcheval and Damien Vergnaud, editors, Progress in Cryptology - AFRICACRYPT 2014, pages 165–177, Cham. 2014. Springer International Publishing. DOI: 10.1007/978-3-319-06734-6_11
[RSA78]
R. L. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM, 21(2):120–126, February 1978. DOI: 10.1145/359340.359342
[Sar11]
Santanu Sarkar. Partial Key Exposure: Generalized Framework to Attack RSA. In Daniel J. Bernstein and Sanjit Chatterjee, editors, Progress in Cryptology - INDOCRYPT 2011, pages 76–92, Berlin, Heidelberg. 2011. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-25578-6_7
[SLH14]
Meng Shi, Xianghui Liu, and Wenbao Han. Implicit Factoring with Shared Middle Discrete Bits. In W. Eric Wong and Tingshao Zhu, editors, Computer Engineering and Networking, pages 255–263, Cham. 2014. Springer International Publishing. DOI: 10.1007/978-3-319-01766-2_30
[SM11]
S. Sarkar and S. Maitra. Approximate Integer Common Divisor Problem Relates to Implicit Factorization. IEEE Trans. Inf. Theor., 57(6):4002–4013, June 2011. DOI: 10.1109/TIT.2011.2137270
[SZZ+19]
Zhelei Sun, Tianwei Zhang, Xiaoxia Zheng, Liuqing Yang, and Liqiang Peng. A Method for Solving Generalized Implicit Factorization Problem. In Songlin Sun, Meixia Fu, and Lexi Xu, editors, Signal and Information Processing, Networking and Computers, pages 284–290, Singapore. 2019. Springer Singapore. DOI: 10.1007/978-981-13-7123-3_34
[WQLF17]
Shixiong Wang, Longjiang Qu, Chao Li, and Shaojing Fu. A better bound for implicit factorization problem with shared middle bits. Science China Information Sciences, 61, 2017. DOI: 10.1007/s11432-017-9176-5
[Zhe23]
Mengce Zheng. Generalized implicit-key attacks on RSA. Journal of Information Security and Applications, 77:103562, 2023. DOI: 10.1016/j.jisa.2023.103562
History
Submitted: 2024-06-26
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Chunzhi Zhao, Junqi Zhang, Jinzheng Cao, Qingfeng Cheng, and Fushan Wei, Implicit Factorization with Shared Any Bits. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/anjbhey6b.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.