Proceedings of International Mathematical Sciences

Yazarlar: Saıdu ISAH ABUBAKAR, Ibrahim ZAİD, Sadiq SHEHU, Rufa'ı AHMAD

Konular:Bilgisayar Bilimleri, Disiplinler Arası Uygulamalar

DOI:10.47086/pims.827108

Anahtar Kelimeler:Diophantine;,Attack;,Prime power;,Moduli;,Continued fraction;

Özet: 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

---