2
$\begingroup$

Are there any (recent) estimates of cost of attack on DSA by solving the discrete logarithm? I'm especially interested in attacks that use Pollard's rho algorithm.

Are there any optimized implementations of Pollard's rho algorithm that can be used to estimate such costs?

$\endgroup$
  • $\begingroup$ Pollard-rho needs roughly $O(\sqrt{q})$ time, where $q$ is the order of the subgroup used, this (usually) should give you enough insight whether or not to use a particular subgroup. $\endgroup$ – SEJPM Dec 13 '15 at 22:27
  • $\begingroup$ DSS specifies the required size of $q$. I'm interested in attacks when one uses $q$ with prescribed size. $\endgroup$ – user29817 Dec 13 '15 at 22:37
  • $\begingroup$ You can't "optimize" Pollard Rho. It is what it is. You can however (a) modify the algorithm to use various trade-offs, or (b) optimize the implementations of the underlying arithmetic operations. In the former case you will get a different algorithms. which might or might not be faster depending on a lot of factors. In the latter case you might get a speed up by a constant factor. $\endgroup$ – Henrick Hellström Dec 14 '15 at 9:32
  • $\begingroup$ DSS requires at least $q$ to be of size at least 160 bits. This means Pollard-Rho would roughly need $2^{80}$ operation (best case) which is considered "infeasible, but mitigation to larger sizes is strongly recommended". $\endgroup$ – SEJPM Dec 14 '15 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.