Re: length of exponents

[David A Wagner <daw@CS.Berkeley.EDU>]

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 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).

---

• Next by Date: subscribe ipsec@ans.net
• Next by thread: Re: length of exponents
• Index(es):
  • Main
  • Thread