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
    https://doi.org/10.14419/ijamr.v5i4.6494
  • Continued fraction, Diophantine approximations, Factorization, LLL algorithm, RSA prime power, Simultaneous.

  • 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. [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.

  • Downloads

    Additional Files

  • How to Cite

    Ariffin, M. R. K., & Shehu, S. (2016). Cryptanalysis on prime power RSA modulus of the form \(N = p^r q\). International Journal of Applied Mathematical Research, 5(4), 167-175. https://doi.org/10.14419/ijamr.v5i4.6494