Diophantine Attack on Prime Power With Modulus $N=p^rq$

Abstract

The importance of keeping information secret cannot be overemphasized especially in today,s digital world where eavesdroppers are rampant in our chanels of communication. This made the use of strong encryption schemes inevitable in order to safeguard the security of our system. RSA cryptosystem and its variants have been designed to provide confidentiality and integrity of data in our medium of communication. This paper reports new short decryption exponent attack on prime power with modulus $N=p^rq$ for $r\geq 2$ using continued fraction method which makes it vulnerable to Diophantine attack and breaks the security of the cryptosystem by factoring the modulus into its prime factors since the hardness relies on the integer factorization problem. The paper also shows that if the short decryption exponent $d <\frac{1}{\sqrt{2}}\sqrt{N- 2^{\frac{2r+1}{r+1}} N^{\frac{r}{r+1}}}$, then one of the convergents $\frac{k}{d}$ can be found from the continued fraction expansion of $\frac{e}{N-\left\lceil 2^{\frac{2r+1}{r+1}} N^{\frac{r}{r+1}}\right\rceil}$ which leads to the successful factorization of prime power modulus $N=p^rq$ in polynomial time. The second part of the paper presents new findings on simultaneous factorization of $t$ prime power with moduli $N_s=p^r_sq_s$ for $s=1,\ldots, t$ using simultaneous Diophantine approximations and lattice basis reduction methods which produces the prime factors of the form $(p_s,q_s)$ for $s=1,\ldots, t$ in polynomial time where solutions of four system of equations of the form $e_sd-k_s\phi(N_s)=1$, $e_sd_s-k\phi(N_s)=1$, $e_sd-k_s\phi(N_s)=z_s$ and $e_sd_s-k\phi(N_s)=z_s$ are provided. Our results increases the short decryption exponent bounds of some reported works

Keywords

• Diophantine;
• Attack;
• Prime power;
• Moduli;
• Continued fraction;

References

1. 1. M. K. Dubey, N. Ratan, R. Verma, N. Saxena, Cryptanalytic attacks and countermeasures on RSA, in: P. K. (2014): In Proceedings of the Third International Conference on Soft Computing for Problem Solving, Springer, 2014, 10--18.
2. 2. T. Fujioka, A. Okamoto, S. Miyaguchi, ESIGN: An efficient digital signature implementation for smart cards, in: Advances in Cryptology EUROCRYPT 91, Lecture Notes in Computer Science, Springer, 1991, 446--457.
3. 3. T. Okamoto, S. Uchiyama, A new public-key cryptosystem as secure as factoring, in: Advances in Cryptology EUROCRYPT’98, Lecture Notes in Computer Science, Springer, 1998, 308--318.
4. 4. T. Takagi, Fast RSA-type cryptosystem modulo $p^kq$, in: Advances in Cryptology CRYPTO ’98. CRYPTO 1998. Lecture Notes in Computer Science, Springer, 1998, 318--326.
5. 5. A. May, Secret exponent attacks on RSA-type schemes with moduli $N = p^rq$, in: Public Key Cryptography-PKC 2004, Springer, 2004, 218--230.
6. 6. S. Sarkar, Small secret exponent attack on RSA variant with modulus $N =p^2q$, in: Proceedings International Workshop on Coding and Cryptography-WCC 2013, Norway and INRIA, 2013, 215--222.
7. 7. R. Lu, Y. Zhang, D. Lin, New results on solving linear equations modulo unknown divisors and its applications, IACR Cryptology eprint \textbf{1} (1-4) (2014) 343--354.
8. 8. S. Sarkar, Revisiting prime power RSA, Discrete Applied Mathematics \textbf{203}(C) (2016) 127--133.

9. 9. K. Itoh, K. Kunihiro, K. Kurosawa, Small secret key attack on a variant of RSA (due to takagi), in: CT-RSA 2008, in:LNCS, 2008, 387--406.
10. 10. J. Bl¨omer, A. May, A generalized Wiener attack on RSA, in: International Workshop on Public Key Cryptography, Springer, 2004, 1--13.
11. 11. J. Hinek, On the security of some variants of RSA, Phd thesis, Universiti Waterloo, Ontario, Canada (2007).
12. 12. A. Nitaj, M. Ariffin, D. Nassr, H. Bahig, New Attacks on the RSA cryptosystem, in: Progress in Cryptology AFRICACRYPT 2014. Lecture Notes in Computer Science, \textbf{8469}, Springer, 2014, 178--198.
13. 13. S. Shehu, M. Ariffin, New attacks on prime power RSA $N = p^rq$ using good approximation of $\phi(N)$, Malaysian Journal of Mathematical Sciences special issues:The 5th International Cryptology and Information Security Conference(New Ideas in ) \textbf{11}(S) (2017) 121--138.
14. 14. H. Lenstra, A.K. Lenstra, L. Lovsz, Factoring polynomials with rational coefficients, Mathematische Annalen (1982) 513--534.
15. 15. Nitaj, Diophantine and lattice cryptanalysis of the RSA cryptosystem, in: Artificial Intelligence, Evolutionary Computing and Metaheuristics, Springer, 2013, 139--168.
16. 16. X. Wang, X. G., M. Wang, X. Meng, Mathematical Foundations of Public Key Cryptography, CRC Press, Boca Rating London New York, 2016.