Second International Workshop on Practice and Theory in Public Key Cryptography, PKC'99
(March 1--3, 1999, Kamakura, Kanagawa, Japan),
H. Imai and Y. Zheng (Eds.),
Volume 1560 of
Lecture Notes in Computer Science,
Springer-Verlag.
Abstract:
At Eurocrypt '96, Coppersmith presented a novel application
of lattice reduction to find small roots of a univariate
modular polynomial equation. This led to rigorous polynomial
attacks against RSA with low public exponent, in some particular
settings such as encryption of stereotyped messages,
random padding, or Hastad-like broadcast applications.
Theoretically, these are the most powerful known attacks against low-exponent RSA.
However, the practical behaviour of Coppersmith's method was unclear.
On the one hand, the method requires
reductions of high-dimensional lattices with huge entries,
which could be out of reach.
On the other hand, it is well-known
that lattice reduction algorithms output better results
than theoretically expected, which might allow
better bounds than those given by Coppersmith's theorems.
In this paper, we present extensive experiments
with Coppersmith's method, and discuss
various trade-offs together with practical improvements.
Overall, practice meets theory.
The warning is clear: one should be very cautious
when using the low-exponent RSA encryption scheme, or one should
use larger exponents.