Public key exponent attacks on multi-prime power modulus using continued fraction expansion method

Zaid Ibrahim, Sadiq Shehu, Saidu Isah Abubakar Β· Caliphate Journal of Science and Technology Β· 2023

This paper proposes three public key exponent attacks of breaking the security of the prime power modulus 𝑁=𝑝2π‘ž2 where 𝑝 and π‘ž are distinct prime numbers of the same bit size. The first approach shows that the RSA prime power modulus 𝑁=𝑝2π‘ž2 for q<𝑝<2q using key equation π‘’π‘‘βˆ’π‘˜πœ™(𝑁)=1 where πœ™(𝑁)= 𝑝2π‘ž2(π‘βˆ’1)(π‘žβˆ’1) can be broken by recovering the secret keys π‘˜ /𝑑 from the convergents of the continued fraction expansion of e/π‘βˆ’2𝑁3/4 +𝑁1/2 . The paper also reports the second and third approaches of factoring 𝑛 multi-prime power moduli 𝑁𝑖=𝑝𝑖2 π‘žπ‘–2 simultaneously through exploiting generalized system of equations π‘’π‘–π‘‘βˆ’π‘˜π‘–πœ‘(𝑁𝑖)=1 and π‘’π‘–π‘‘π‘–βˆ’π‘˜πœ‘(𝑁𝑖)=1 respectively. This can be achieved in polynomial time through utilizing Lenstra Lenstra Lovasz (LLL) algorithm and simultaneous Diophantine approximations method for 𝑖=1,2,…,𝑛.

Read the paper Β· More papers on PaperTik