Small Secret Key Attack on a Takagi's Variant of RSA

摘要

For a variant of RSA with modulus N = p'q and ed ≡ 1 (mod (p - 1 )(q - 1)), we show that d is to be recovered if d < N~((2-2~(1/2))/(r+1)). (Note that φ(N) ≠ (p - 1)(q - 1).) Boneh-Durfee's result for the standard RSA is obtained as a special case for r = 1. Technically, we develop a method for finding a small root of a trivariate polynomial equation f(x,y,z) = x(y - 1)(z - 1) + 1 ≡ 0 (mod e) under the condition that y~rz = N. Our result cannot be obtained from the generic method of Jochemsz-May.