International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Implicit Factorization with Shared Any Bits

Authors:
Chunzhi Zhao , Information Engineering University
Junqi Zhang , Information Engineering University
Jinzheng Cao , Information Engineering University
Qingfeng Cheng , Information Engineering University
Fushan Wei , Information Engineering University
Download:
DOI: 10.62056/anjbhey6b
URL: https://cic.iacr.org//p/1/3/8
Search ePrint
Search Google
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.

BibTeX
@article{cic-2024-34819,
  title={Implicit Factorization with Shared Any Bits},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 3},
  url={https://cic.iacr.org//p/1/3/8},
  doi={10.62056/anjbhey6b},
  author={Chunzhi Zhao and Junqi Zhang and Jinzheng Cao and Qingfeng Cheng and Fushan Wei},
  year=2024
}