New Jochemsz–May Cryptanalytic Bound for RSA System Utilizing Common Modulus <i>N</i> = <i>p</i>²<i>q</i>

Abstract

This paper describes an attack on the Rivest, Shamir and Adleman (RSA) cryptosystem utilizing the modulus N=p2q where p and q are two large balanced primes. Let e1,e2Nγ be the integers such that d1,d2Nδ be their multiplicative inverses. Based on the two key equations e1d1−k1ϕ(N)=1 and e2d2−k2ϕ(N)=1 where ϕ(N)=p(p−1)(q−1), our attack works when the primes share a known amount of least significant bits (LSBs) and the private exponents share an amount of most significant bits (MSBs). We apply the extended strategy of Jochemsz–May to find the small roots of an integer polynomial and show that N can be factored if δ1110+94α−12β−12γ−130180γ+990α−180β+64. Our attack improves the bounds of some previously proposed attacks that makes the RSA variant vulnerable.

Keywords

• factoring
• least significant bits (LSBs)
• most significant bits (MSBs)
• multiplicative inverse
• Jochemsz–May extended strategy