• Archives
• Malaysian Journal of Mathematical Sciences, August 2017, Vol. 11(S)
• View

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: sadiqshehuzezi@gmail.com

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

picture_as_pdf Fullpaper  Downloaded: 3     Abstract Viewed: 0