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

Authors : Saıdu ISAH ABUBAKAR, Ibrahim ZAİD, Sadiq SHEHU, Rufa\`ı AHMAD

Pages : 103-128

Doi:10.47086/pims.827108

View : 10 | Download : 7

Publication Date : 2020-12-30

Article Type : Research Paper

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 $insert ignore into journalissuearticles values(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\\phiinsert ignore into journalissuearticles values(N_s);=1$, $e_sd_s-k\\phiinsert ignore into journalissuearticles values(N_s);=1$, $e_sd-k_s\\phiinsert ignore into journalissuearticles values(N_s);=z_s$ and $e_sd_s-k\\phiinsert ignore into journalissuearticles values(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,