# Cryptanalysis on prime power RSA modulus of the form $$N = p^r q$$

## Authors

• Muhammad Rezal Kamel Ariffin UNIVERSITY PUTRA MALAYSIA
• Sadiq Shehu UNIVERSITY PUTRA MALAYSIA

2016-09-21

## Keywords:

Continued fraction, Diophantine approximations, Factorization, LLL algorithm, RSA prime power, Simultaneous.

## Abstract

Let $$N = p^r q$$ be an RSA prime power modulus for $$r \geq 2$$ and $$q < p < 2 q$$. This paper propose three new attacks. In the first attack we consider the class of public exponents satisfying an equation $$e X - N Y = u p^r + \frac{q^r}{u} + Z$$ for suitably small positive integer $$u$$. Using continued fraction we show that $$\frac{Y}{X}$$ can be recovered among the convergents of the continued fraction expansion of $$\frac{e}{N}$$ and leads to the successful factorization of $$N p^r q$$. Moreover we show that the number of such exponents is at least $$N^{\frac{r+3}{2(r+1)}-\varepsilon}$$ where $$\varepsilon \geq 0$$ is arbitrarily small for large $$N$$. The second and third attacks works when $$k$$ RSA public keys $$(N_i,e_i)$$ are such that there exist $$k$$ relations of the shape $$e_i x - N_i y_i = p_i^r u + \frac{q_i^r}{u} + z_i$$ or of the shape $$e_i x_i - N_i y = p_i^r u + \frac{q_i^r}{u} + z_i$$ where the parameters $$x$$, $$x_i$$, $$y$$, $$y_i$$, $$z_i$$ are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enable us to simultaneously factor the $$k$$ prime power RSA moduli $$N_i$$.

## References

[1] Boneh, D., Durfee, G., Cryptanalysis of RSA with private key d less than N0.292, Advances in Cryptology - Eurocryptâ€™99, Lecture Notes in Computer Science Vol. 1592, Springer-Verlag, (1999), 1â€“11.

[2] Blomer, J., May, A., A generalized Wiener attack on RSA, In Public Key Cryptography - PKC 2004, volume 2947 of Lecture Notes in Computer Science, Springer-Verlag (2004), 1â€“13.

[3] Howgrave-Graham, N., Seifert, J. P., Extending Wieners attack in the presence of many decrypting exponents, In Secure Networking- CQRE (Secure)â€™99, LNCS 1740, Springer-Verlag (1999), 153â€“166.

[4] Hardy, G.H., Wright, E.M., An Introduction to the Theory of Numbers, Oxford University Press, London (1975).

[5] Hinek, J., On the Security of Some Variants of RSA, Phd. Thesis, Waterloo, Ontario, Canada (2007)

[6] Hinek, M. Jason, Lattice attacks in cryptography: A partial overview, School of Computer Science, University of Waterloo, Canada (2004).

[7] Lenstra, A.K. , Lenstra, H.W., L. Lovasz, L., Factoring polynomials with rational coefficients, Mathematische Annalen, Vol. 261, (1982), 513â€“534.

[8] May, A., New RSA Vulnerabilities Using Lattice Reduction Methods, PhD. thesis, University of Paderborn (2003).

[9] Nitaj, A., Ariffin, M. R. K., Nassr, D. I., and Bahig, H. M., New Attacks on the RSA Cryptosystem, Progress in Cryptology- AFRICACRYPT 2014. Springer International Publishing, (2014), 178â€“198.

[10] Nitaj, Abderrahmane, Diophantine and Lattice Cryptanalysis of the RSA Cryptosystem. Artificial Intelligence, Evolutionary Computing and Metaheuristics. Springer Berlin Heidelberg, (2013), 139â€“168.

[11] Nitaj, Abderrahmane, Cryptanalysis of RSA Using the Ratio of the Primes, Progress in Cryptology-AFRICACRYPT 2009. Springer Berlin Heidelberg, (2009), 98â€“115.

[12] Nitaj, Abderrahmane, and Tajjeeddine Rachidi, New Attacks on RSA with Moduli N = prq. Codes, Cryptology, and Information Security. Springer International Publishing, (2015), 352â€“360.

[13] Nitaj, Abderrahmane, A New Vulnerable Class of Exponents in RSA. (2011).

[14] Rivest, R., Shamir, A., Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21.2 (1978), 120â€“126.

[15] Sarkar, S., Small secret exponent attack on RSA variant with modulus N = prq, Designs, Codes and Cryptography, Volume 73, Issue 2, (2015), 383â€“392.

[16] Takagi, T., Fast RSA-type cryptosystem modulo pkq. In Advances in Cryptology-Cryptoâ€™98, Springer, (1998), 318â€“326.

[17] Wiener, M., Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information Theory, Vol. 36, (1990), 553â€“558.