NEW ATTACKS ON PRIME POWER RSA MODULUS N = prq

In this paper we present three new attacks on the Prime Power RSA modulusN=prq. The firstattack is based on the equationeX−NY+ (apr+bqr−1)Y=Zwherea,bare suitably positiveintegers satisfyinggcd(a,b) = 1. Using continued fraction we show thatYXcan be recovered amongthe convergents of the continued fraction expansion ofeN+1. Hence one can factor the modulusN=prqin polynomial time. LetNi=priqifori= 1,...,k, withk≥2 andr≥2. Thesecond and third attacks works based on LLL algorithm whenkRSA public keys (Ni,ei) aresuch that there existkrelations of the formeix−Niyi+ (apri+bqri−1)yi=zior of the formeixi−Niy+ (apri+bqri−1)y=ziwhere the parametersx,xi,y,yi,ziare suitably small in termsof the prime factors of the moduli. Hence we show that our approach enable us to simultaneouslyfactor thekRSA moduliNi=priqi.