Asymptotic Bound for RSA Variant with Three Decryption Exponents

Year 2023, , 1 - 6, 30.04.2023

Saıdu Isah Abubakar Ibrahim Zaid Amınu Alhajı Ibrahım

https://doi.org/10.33187/jmsm.1135988

Abstract

This paper presents a cryptanalysis attack on the RSA variant with modulus $N=p^rq$ for $r\geq 2$ with three public and private exponents $(e_1,d_1),$ $(e_2,d_2),$ $(e_3,d_3)$ sharing the same modulus $N$ where $p$ and $q$ are consider to prime having the same bit size. Our attack shows that we get the private exponent $\sigma_1\sigma_2\sigma_3<\left(\frac{r-1}{r+1}\right)^4$, which makes the modulus vulnerable to Coppersmith's attacks and can lead to the factorization of $N$ efficiently
where $d_1 The asymptotic bound of our attack is greater than the bounds for May \cite{May}, Zheng and Hu \cite{Z}, and Lu et al. \cite{Y} for $2\leq r \leq 10$ and greater than Sarkar's \cite{Sarkar1} and \cite{Sarkar} bounds for $5 \leq r \leq10$.

Keywords

Asymptotic, Bound, Cryptanalysis, Decryption, Exponents, RSA variants

Thanks

I want to appreciate you for giving me this opportunity to submit my article into your reputable journal. I hope you will find our work suitable for publication in this journal. Thank you

References

• [1] A. May, Secret exponent attacks on RSA-type schemes with moduli N = prq, Proceedings of 7th International Workshop on Theory and Practice in Public Key Cryptography, (2004), 218-230.
• [2] M. Zheng, H. Hu, Cryptanalysis of prime power RSA with two private exponents, Sci. China Inf. Sci., 58 (2015), 8 pages.
• [3] Y. Lu, R. Zhang, L. Peng, D. Lin, Solving linear equations modulo unknown divisors: Revisited, International Conference in the Theory and Application of Cryptology and Information Security, (2015), 189-213.
• [4] S. Sarkar, Small secret exponent attack on RSA variant with modulus N = prq, Des. Codes Cryptogr. 73(2) (2014), 383-392.
• [5] S. Sarkar, Revisiting Prime Power RSA, Discrete Applied Mathematics, 203 (2016), 127-133.
• [6] R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120-126.
• [7] M. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Trans. Inf. Theory, 36(3) (1990), 553-558.
• [8] S. I. Abubakar, M. R. K. Ariffin, M. A. Asbullah, A new simultaneous diophantine attack upon RSA moduli N = pq, In Cryptology and Information Security Conference, (2018), 119-131.
• [9] M. K. R. Ariffin, S. I. Abubakar, F. Yunos, M. A. Asbullah, New cryptanalytic attack on RSA modulus N = pq using small prime difference method, Cryptography, 3(1) (2019), 2.
• [10] T. Takagi, Fast RSA-type cryptosystem modulo pkq, Advances in Cryptology-CRYPTO, 1998 (1998), 318-326.
• [11] D. Boneh, G. Durfee, N. Howgrave-Graham, Factoring N = prq for large r, Proceedings of 19th Annual International Cryptology Conference, (1990) (1990), 326-337.
• [12] A. Takayasu, N. Kunihiro, Better lattice construction for solving multivariate linear equations modulo unknown divisors, Proceedings of the 18th Australian Conference (ACISP 2013), (2013), 118-135.
• [13] A. Nitaj, Diophantine and lattice cryptanalysis of the RSA cryptosystem, Artificial Intelligence, Evolutionary Computing and Metaheuristics, (2013), 139-168.
• [14] A. K. Lenstra, H. W. Lenstra, L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 513-534.
• [15] N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Darnell M. Cryptography and Coding, (1997), 131-142.