Small Secret-Key Attack on a Takagi's Variant of RSA
For a variant of RSA with modulus N = p(r)q and ed equivalent to 1 (mod (p-1)(q-1)), we show that d is to be recovered if d < N((2-root 2)/(r+1)). (Note that phi(N) not equal (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 equivalent to 0 (mod e) under the condition tion that Y'z = N. Our result cannot be obtained from the gencrii. method of Jochemsz-May.
rsa trivariate polynomial lattice lll