Hill Publishing Group | contact@hillpublisher.com

Hill Publishing Group

Location:Home / Journals / Journal of Applied Mathematics and Computation /


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

Date: December 18,2020 |Hits: 3240 Download PDF How to cite this paper
Sadiq Shehu, Saidu Isah Abubakar*, Zaid Ibrahim

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

*Corresponding author: Saidu Isah Abubakar


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

Volumes & Issues

Free HPG Newsletters

Add your e-mail address to receive free newsletters from Hill Publishing Group.

Contact us

Hill Publishing Group

8825 53rd Ave

Elmhurst, NY 11373, USA

E-mail: contact@hillpublisher.com

Copyright © 2019 Hill Publishing Group Inc. All Rights Reserved.