Asymptotic Bound for RSA Variant with Three Decryption Exponents
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$.
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.
