Malaysian Journal of Mathematical Sciences, August 2017, Vol. 11(S)
Special Issue: The 5th International Cryptology and Information Security Conference (New Ideas in Cryptology)
New Attacks on Prime Power \(N=p^rq\) Using Good Approximation of \(\phi(N)\)
Shehu, S. and Ariffin, M.R.K.
Corresponding Email: [email protected]
Received date: -
Accepted date: -
Abstract:
This paper proposes three new attacks. Our first attack is based on the RSA key equation \(ed-k\phi(N)=1\) where \(\phi(N)=p^{r-1}(p-1)(q-1)\). Let \(q < p < 2q\) and \(2p^{\frac{3r+2}{r+1}}\left | p^{\frac{r-1}{r+1}} - q^{\frac{r-1}{r+1}} \right |<\frac{1}{6}N^{\gamma} \) with \(d=N^{\delta}\). If \(\delta<\frac{1-\gamma}{2}\) we shows that \(\frac{k}{d}\) can be recovered among the convergents of the continued fractions expansions of \(\frac{e}{N-2N^{\frac{r}{r+1}}+N^{\frac{r-1}{r+1}}}\). We furthered our analysis on \(j\) prime power moduli \(N_{i}=p_{i}^rq_{i}\) satisfying a variant of the above mentioned condition. We utilized the LLL algorithm on \(j\) prime power public keys \((N_{i}, e_{i})\) with \(N_{i}=p_{i}^rq_{i}\) and we were able to factorize the \(j\) prime power moduli \(N_{i}=p_{i}^rq_{i}\) simultaneously in polynomial time.
Keywords: Prime Power, Factorization, LLL algorithm, Simultaneous diophantine approximations, Continued fractions
