[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

length of exponents



Ref:  Your note of Thu, 30 Nov 1995 19:19:53 -0800 (PST) (attached)

daw@CS.Berkeley.EDU writes:
 >
 > hugo@watson.ibm.com writes:
 > > If one uses 160 long exponents the security becomes at most 2^80 because
 > > of Shanks/Pollard attacks that require roughly 2^{t/2} operations to find an
 > > exponent whose length is t (this number is independent of the modulus
 > > length).
 >
 > I think this is sound advice.
 >
 > As I've mentioned in private email, Wiener & van Oorschot's results
 > on efficient parallel collision search seem relevant here.
 >
 > In particular, I believe their methods can be used to parallelize
 > Shanks' & Pollard's attacks on short exponents, without incurring
 > extra time or space penalties.

This is right, and the parallelization applies to their improved attacks
on short exponent Diffie-Hellman as well.

 >
 > This underscores the recommendation to use > 128 bit exponents,
 > since a parallelizable attack requiring 2^64 operations is right
 > on the edge of feasibility (whereas a serial-only attack might
 > not be as much of a concern).

Right. A crucial issue that I failed to point out to.Thanks for clarifying
that.

Hugo