| Autor: |
Feng, Yansong, Nitaj, Abderrahmane, Pan, Yanbin |
| Rok vydání: |
2023 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1007/978-3-031-53368-6_18 |
| Popis: |
The Implicit Factorization Problem was first introduced by May and Ritzenhofen at PKC'09. This problem aims to factorize two RSA moduli $N_1=p_1q_1$ and $N_2=p_2q_2$ when their prime factors share a certain number of least significant bits (LSBs). They proposed a lattice-based algorithm to tackle this problem and extended it to cover $k>2$ RSA moduli. Since then, several variations of the Implicit Factorization Problem have been studied, including the cases where $p_1$ and $p_2$ share some most significant bits (MSBs), middle bits, or both MSBs and LSBs at the same position. In this paper, we explore a more general case of the Implicit Factorization Problem, where the shared bits are located at different and unknown positions for different primes. We propose a lattice-based algorithm and analyze its efficiency under certain conditions. We also present experimental results to support our analysis. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
