Secret exponent attacks on RSA-type schemes with moduli \(N=p^rq\). (English) Zbl 1198.94113

Bao, Feng (ed.) et al., Public key cryptography – PKC 2004. 7th international workshop on theory and practice in public key cryptography, Singapore, March 1–4, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21018-0/pbk). Lecture Notes in Computer Science 2947, 218-230 (2004).
Summary: We consider RSA-type schemes with modulus \(N=p^rq\) for \(r\geq 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 [D. Coppersmith, J. Cryptology 10, No. 4, 233–260 (1997; Zbl 0912.11056)]. 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 \(d_p = d\bmod p-1\) which is used in CRT-variants like Takagi’s scheme [T. Takagi, “Fast RSA-type cryptosystem modulo \(p^k q\)”, Lect. Notes Comput. Sci. 1462, 318–326 (1998; Zbl 0931.94041)]. Our results show that RSA-type schemes that use moduli of the form \(N=p^rq\) are more susceptible to attacks that leak bits of the secret key than the original RSA scheme.
For the entire collection see [Zbl 1049.94003].


94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Full Text: DOI