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

Abstract

This paper proposes three public key exponent attacks of breaking the security of the prime power modulus ?=?²?² where ? and ? are distinct prime numbers of the same bit size. The first approach shows that the RSA prime power modulus ?=?²?² for q<?<2q using key equation ??−??(?)=1 where ?(?)= ?²?²(?−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 ?_?=?_?² ?_?² 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,…,?.