Publications

2024

1. Two-Step Attack

   Practical Attacks on Small Private Exponent RSA

   Yansong Feng, Zhen Liu, Abderrahmane Nitaj, and 1 more author

   2024

   Abs Bib PDF

   It is well known that the best small private exponent attack against RSA is that when the private exponent d < N^0.292, one can factor the RSA modulus N = pq. However, the bound N^0.292 is very difficult to achieve directly since we need to deal with some lattice with very high dimension, which seems infeasible by now. Recently, Li et al. proposed a practical attack that can solve cases when d approaches N^0.292 within a month for 1024 bit N. In this paper, we propose an improved practical small private exponent attack by enumerating the most significant bits of p + q. Together with some skills in implementations, we can also achieve the bound N^0.292, but with significantly less time compared to previous work.

   @misc{feng2024practial,
     title = {Practical Attacks on Small Private Exponent RSA},
     author = {Feng, Yansong and Liu, Zhen and Nitaj, Abderrahmane and Pan, Yanbin},
     year = {2024},
   }

2. 

   Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA

   Yansong Feng, Abderrahmane Nitaj, and Yanbin Pan

   CIC, 2024

   Abs Bib PDF Code

   Let (N,e) be a public key of the RSA cryptosystem, and (N,d) be the corresponding private key. In practice, we usually choose a small e for encryption. In this paper, we improve Partial Key Exposure attacks on standard RSA on secret exponents d with small public exponent e. Compared to previous results, we reduced it by \log_N(e) bits. We turn it into solving univariate modular polynomials, so we don’t rely on the assumptions of the Coppersmith method (for multivariate polynomials). Moreover, our experiments show that for 1024-bit N, our algorithm can achieve the theoretical bound on a personal computer.

   @article{feng2024small,
     title = {Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA},
     author = {Feng, Yansong and Nitaj, Abderrahmane and Pan, Yanbin},
     journal = {CIC},
     year = {2024},
   }

3. 👌: \mathcal{O}_K

   Pre-Processing on \\mathcal{O}_K Brings More: Solving γ-SVP in Order-Ideal Lattices

   Yihang Cheng, Yansong Feng, Hengyi Luo, and 1 more author

   2024

   Bib

   @misc{cheng2024pre,
     author = {Cheng, Yihang and Feng, Yansong and Luo, Hengyi and Pan, Yanbin},
     title = {Pre-Processing on \$\mathcal\{O\}_K\$ Brings More: Solving $\gamma$-SVP in Order-Ideal Lattices},
     year = {2024},
   }

4. 

   Newton Polytope-Based Strategy for Finding Roots of Multivariate Polynomials

   Yansong Feng, Abderrahmane Nitaj, and Yanbin Pan

   2024

   Abs Bib PDF

   Coppersmith’s method, combined with the Jochemsz-May strategy, is widely used to find the small roots of multivariate polynomials for cryptanalysis. At Asiacrypt’23, Meers and Nowakowski improved the Jochemsz-May strategy from a single polynomial equation to a system of polynomial equations and proposed a new method, called Automated Coppersmith. Note that it is typically a tedious and non-trivial task to determine asymptotic upper bounds for Coppersmith’s method and manual analysis has to be performed anew when a new set of polynomials is considered. By making certain heuristic assumption, Meers and Nowakowski showed that the bound can be obtained using Lagrange interpolation with the computer, but it is still time-consuming. Moreover, we find that sometimes the interpolation method may get stuck in local convergence, which will result in an incorrect bound when a natural termination strategy is employed in the method. In this paper, we revisit the Jochemsz-May strategy as well as the work of Meers and Nowakowski and point out that the bound can be obtained by calculating the leading coefficient of some Hilbert function, which is exactly the volume of the corresponding Newton polytope. To this end, we introduce the concept of Sumsets theory and propose a series of related results and algorithms. Compared with the Automated Coppersmith, we overcome the issue of getting stuck in local convergence and directly eliminate the time-consuming calculation for f^m in Automated Coppersmith when m is large, which brings a 1000x\sim1200x improvement in running time for some polynomials in our experiment. Additionally, our new method offers a new perspective to understand Automated Coppersmith, thus providing proof of Meers and Nowakowski’s Heuristic 2 for the system of a single polynomial.

   @misc{feng2024newton,
     title = {Newton Polytope-Based Strategy for Finding
     Roots of Multivariate Polynomials},
     author = {Feng, Yansong and Nitaj, Abderrahmane and Pan, Yanbin},
     year = {2024},
   }

5. 

   Solving Modular Linear Equations via Automated Coppersmith and its Applications

   Yansong Feng, Zhen Liu, Abderrahmane Nitaj, and 1 more author

   2024

   Abs Bib

   At Asiacrypt’23, Meers and Nowakowski introduced a new automated method called Automated Coppersmith, which can be viewed as a generalization of Jochemsz-May Strategy for systems of polynomial equations. It selects monomials first, then constructs polynomials to construct the lattice in Coppersmith method. However, their strategy arises a new heuristic assumption. In this paper, We try to eliminate this heuristic assumption on linear equation systems. Finally, we apply this method to analyze the Generalized Extended Implicit Factorization Problem (G-EIFP), a generalization of the Extended Implicit Factorization Problem (EIFP), even when the shared contiguous bits are arbitrary.

   @misc{feng2024solving,
     title = {Solving Modular Linear Equations via Automated Coppersmith and its Applications},
     author = {Feng, Yansong and Liu, Zhen and Nitaj, Abderrahmane and Pan, Yanbin},
     year = {2024},
   }

6. Embedding

   Embedding Integer Lattices as Ideals into Polynomial Rings

   Yihang Cheng, Yansong Feng, and Yanbin Pan

   ISSAC, 2024

   Abs Bib PDF Code

   Many lattice-based crypstosystems employ ideal lattices for high efficiency. However, the additional algebraic structure of ideal lattices usually makes us worry about the security, and it is widely believed that the algebraic structure will help us solve the hard problems in ideal lattices more efficiently. In this paper, we study the additional algebraic structure of ideal lattices further and find that a given ideal lattice in a polynomial ring can be embedded as an ideal into infinitely many different polynomial rings by the coefficient embedding. We design an algorithm to verify whether a given full-rank lattice in \mathbbZ^n is an ideal lattice and output all the polynomial rings that the given lattice can be embedded into as an ideal with time complexity \mathcalO(n^3B(B+\log n), where n is the dimension of the lattice and B is the upper bound of the bit length of the entries of the input lattice basis. We would like to point out that Ding and Lindner proposed an algorithm for identifying ideal lattices and outputting a single polynomial ring that the input lattice can be embedded into with time complexity \mathcalO(n^5B^2) in 2007. However, we find a flaw in Ding and Lindner’s algorithm that causes some ideal lattices can’t be identified by their algorithm.

   @article{cheng2024embedding,
     author = {Cheng, Yihang and Feng, Yansong and Pan, Yanbin},
     title = {Embedding Integer Lattices as Ideals into  Polynomial Rings},
     journal = {ISSAC},
     year = {2024},
   }

7. PPFE Attack

   Partial Prime Factor Exposure Attacks on Some RSA Variants

   Yansong Feng, Abderrahmane Nitaj, and Yanbin Pan

   Theoretical Computer Science, 2024

   Abs Bib PDF Code

   In this paper, we consider five variants of the RSA cryptosystem, where the modulus is N=pq, and the public key e and the secret key d satisfy ed−k(p2+p+1)(q2+q+1)=1 or ed−k(p2−1)(q2−1)=1. Our results show that if a certain amount of the most significant bits of p are known so that |p−p0|=Nβ with a known p0, then one can factor the RSA modulus with a better bound than low private exponent attacks. We also present the experimental results to verify our analysis.

   @article{feng2024partial,
     title = {Partial Prime Factor Exposure Attacks on Some RSA Variants},
     journal = {Theoretical Computer Science},
     year = {2024},
     author = {Feng, Yansong and Nitaj, Abderrahmane and Pan, Yanbin},
   }

2023

1. GIFP

   Generalized Implicit Factorization Problem

   Yansong Feng, Abderrahmane Nitaj, and Yanbin Pan

   SAC, 2023

   Abs Bib PDF Code

   The Implicit Factorization Problem (IFP) was first introduced by May and Ritzenhofen at PKC’09, which concerns the factorization of two RSA moduli N_1=p_1q_1 and N_2=p_2q_2, where p_1 and p_2 share a certain consecutive number of least significant bits. Since its introduction, many different variants of IFP have been considered, such as the cases where p_1 and p_2 share most significant bits or middle bits at the same positions. In this paper, we consider a more generalized case of IFP, in which the shared consecutive bits can be located at \textitany positions in each prime, not necessarily required to be located at the same positions as before. We propose a lattice-based algorithm to solve this problem under specific conditions, and also provide some experimental results to verify our analysis.

   @article{feng2023generalized,
     author = {Feng, Yansong and Nitaj, Abderrahmane and Pan, Yanbin},
     title = {Generalized Implicit Factorization Problem},
     journal = {SAC},
     year = {2023},
   }

2022

1. Rangasamy

   On Rangasamy’s outsourcing algorithm for solving quadratic congruence equations

   Xiulan Li, Yansong Feng, and Yanbin Pan

   2022

   Abs Bib PDF

   Outsourcing computation is a desired approach for IoT (Internet of Things) devices to transfer their burdens of heavy computations to those nearby, resource-abundant cloud servers. Recently, Rangasamy presented a passive attack against two outsourcing algorithms proposed by Zhang et al. for solving quadratic congruence equations, which is widely used in IoT applications. Furthermore, he also proposed a modified algorithm to fix these schemes and claimed that his algorithm was correct and enabled secure and verifiable delegation of solving quadratic congruence equations in IoTs. However, we show that Rangasamy’s modified algorithm has a flaw which makes it incorrect and also propose some further attacks to break the security claim, even when the flaw has been corrected.

   @misc{li2022rangasamy,
     title = {On Rangasamy's outsourcing algorithm for solving quadratic congruence equations},
     author = {Li, Xiulan and Feng, Yansong and Pan, Yanbin},
     year = {2022},
     eprint = {2203.10751},
     archiveprefix = {arXiv},
     primaryclass = {cs.CR},
   }