Article http://dx.doi.org/10.26855/jamc.2020.12.014

Polynomial Time Attacks for Modulus N = p^2 q^2


Sadiq Shehu, Saidu Isah Abubakar*, Zaid Ibrahim

Department of Mathematics, Faculty of Science, Sokoto State University, Sokoto, Nigeria.

*Corresponding author: Saidu Isah Abubakar

Published: December 18,2020


This research proposes three polynomial time attacks on prime power modulus  In the first attack, we show that if ,then the decryption exponent  can be found from the convergent of te continued fraction expansion of where approximation of φ(N) is prove to be  . We present second and third attacks on j multi prime power moduli  by transforming system of equation and into simultaneous Diophantine approximation problem from which we apply lattice basis reduction techniques to find unknown integers and , which leads to successful factorization of j moduli in polynomial time for  .


[1] Batina, L., Mentens, N., Sakiyama, K., Preneel, B., & Verbauwhede, I. (2007). Public-Key Cryptography. EEE In-ternational Symposium on Circuits and Systems, 1831-1834.

[2] Diffie W., & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644-654.

[3] Rivest, R., Shamir, A., Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosys-tems. Communications of the ACM, 21(2), 120-126.

[4] Atsushi Fujioka, Tatsuki Okamoto, & Shoji Miyaguchi. (1991). ESIGN: An Efficient Digital Signature Implemen-tation for Smart Cards. In: Workshop on the Theory and Application of Cryptographic Techniques, Springer, 446-457.

[5] Okamoto, T., & Uchiyama, S. (1998). A New Public-Key Cryptosystem as Secure as Factoring. In: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 308-318.

[6] Nishioka, M., Satoh, H., & Sakurai, K. (2001). Design and Analysis of Fast Provably Secure Public-Key Crypto-systems Based on A Modular Squaring. Springer, Berlin, Heidelberg, 81-102.

[7] Ariffin, K. Rezal, M., Asbullah, M. A., Abu, N. A., & Mahad, Z. (2013). A New Efficient Asymmetric Cryptosystem Based on the Integer Factorization Problem of N = p2q. Malaysian Journal of Mathematical Sciences, 7(S), 19-37.

[8] Sarkar, S. (2014). Small Secret Exponent Attack on RSA Variant with Modulus N = prq. Designs, Codes and Cryp-tography, 73(2), 383-392.

[9] Asbullah, M. A., & M. R. K. Arin. (2015). New Attacks on RSA with Modulus N = p2q Using Continued Fractions. Journal of Physics, Conference Series, 622(1). IOP Publishing.

[10] Lim, S., Kim, S., Yie, I., & Lee, H. (2000). A Generalized Takagi-Cryptosystem with a Modulus of the Form prqs. International Conference on Cryptology, Springer India, 283-294.

[11] Lu, Yao, Liqiang Peng, & Santanu Sarkar. (2017). Cryptanalysis of an RSA Variant with Moduli N = prql’. Journal of Mathematical Cryptology, 11(2), 117-130.

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

[13] Lenstra, A. K., Lenstra, H. W., & L. Lovasz. (1982). Factoring Polynomials with Rational Coefficients. Mathemati-scheAnnalen, 261, 513-534.

[14] Nitaj, A., Arin, M. R. K., Nassr, D. I., & Bahig, H. M. (2014). New Attacks on the RSA Cryptosystem. Progress in Cryptology-AFRICACRYPT. Springer International Publishing, 178-198.

How to cite this paper

Polynomial Time Attacks for Modulus N = p^2 q^2

How to cite this paper: Sadiq Shehu, Saidu Isah Abubakar, Zaid Ibrahim. (2020) Polynomial Time Attacks for Modulus N = p^2 q^2. Journal of Applied Mathematics and Computation, 4(4), 230-240.

DOI: http://dx.doi.org/10.26855/jamc.2020.12.014