TOTAL VIEWS: 7126
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.
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