[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