Secret Exponent Attacks on RSA-type Schemes with Moduli N = p r q

Abstract. We consider RSA-type schemes with modulus N = p r q for r ≥ 2. We present two new attacks for small secret exponent d. Both approaches are applications of Coppersmith’s method for solving modular univariate polynomial equations [5]. From these new attacks we directly derive partial key exposure attacks, i.e. attacks when the secret exponent is not necessarily small but when a fraction of the secret key bits is known to the attacker. Interestingly, all of these attacks work for public exponents e of arbitrary size. Additionally, we present partial key exposure attacks for the value dp = d mod p−1 which is used in CRT-variants like Takagi’s scheme [11]. Our results show that RSA-type schemes that use moduli of the form N = p r q are more susceptible to attacks that leak bits of the secret key than the original RSA scheme. Keywords: N = p r q, Coppersmith’s method, Partial Key Exposure Attack