Abstract:
At Asiacrypt '99, Sun, Yang and Laih proposed three RSA variants
with short secret exponent that resisted all known
attacks, including the recent Boneh-Durfee attack from Eurocrypt '99
that improved Wiener's attack on RSA with short secret exponent.
The resistance comes from the use of unbalanced primes $p$ and $q$.
In this paper, we extend the Boneh-Durfee attack
to break two out of the three proposed variants.
While the Boneh-Durfee attack was based
on Coppersmith's lattice-based technique
for finding small roots to bivariate modular polynomial equations,
our attack is based on its generalization
to trivariate modular polynomial equations.
The attack is heuristic but works well in practice,
as the Boneh-Durfee attack.
In particular, we were able to break in a few minutes the numerical
examples proposed by Sun, Yang and Laih.
The results illustrate once again the fact
that one should be very cautious
when using short secret exponent with RSA.