Implicit Factorization with Shared Any Bits

Chunzhi Zhao; Junqi Zhang; Jinzheng Cao; Qingfeng Cheng; Fushan Wei

doi:10.62056/anjbhey6b

Implicit Factorization with Shared Any Bits

Authors

Chunzhi Zhao, Junqi Zhang, Jinzheng Cao, Qingfeng Cheng, Fushan Wei

Chunzhi Zhao

Information Engineering University, Zhengzhou, China
zhaochunzhi2022 at 126 dot com

Junqi Zhang

Information Engineering University, Zhengzhou, China
zhangjunqi001 at 126 dot com

Jinzheng Cao

Information Engineering University, Zhengzhou, China
caojinzheng at 126 dot com

Qingfeng Cheng

Information Engineering University, Zhengzhou, China
qingfengc2008 at sina dot com

Fushan Wei

Information Engineering University, Zhengzhou, China
weifs831020 at 163 dot com

Keywords: RSA Implicit factorization problem Coppersmith's method

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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[Cop97]

Don Coppersmith. Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. Journal of Cryptology, 10:233–260, 1997. DOI: 10.1007/s001459900030

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[May03]

Alexander May. New RSA vulnerabilities using lattice reduction methods.. PhD thesis, Paderborn University, 2003.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/anjbhey6b

History

Submitted: 2024-06-26
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.

@article{CiC-1-3-8,
    author = "Zhao, Chunzhi and Zhang, Junqi and Cao, Jinzheng and Cheng, Qingfeng and Wei, Fushan",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Implicit Factorization with Shared Any Bits",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/anjbhey6b"
}

TY - JOUR
AU - Zhao, Chunzhi
AU - Zhang, Junqi
AU - Cao, Jinzheng
AU - Cheng, Qingfeng
AU - Wei, Fushan
PY  - 2024
TI  - Implicit Factorization with Shared Any Bits
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/anjbhey6b
UR  - https://doi.org/10.62056/anjbhey6b
AB  - <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 αh-bit, and p1, p2 share uh&gt;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&gt;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&gt;2αln(1/α). 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. </p>
ER  -

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.