6
$\begingroup$

What would be the method of choice to compute the private key from the public key on a baby analog of secp256k1, say with $p$ and $n$ 144-bit?

What would be the pros and cons of Pollard's rho and Pollard's kangaroo ?

How can the special properties of a Koblitz curve be put to use?

$\endgroup$

2 Answers 2

4
+200
$\begingroup$

Solving discrete logarithms in $144$-bit groups is hard Even scaling down to 144-bits is likely beyond current capability. To my knowledge the largest elliptic curve problem tackled with "black box" methods is sect113r1 which was attacked by Bernstein et al in 2016. The computation took 2 months on 120 FPGAs (not all FPGAs ran for the full 2 months). Their paper also tackles a 118-bit group which uses automorphism structure (see comment below on Koblitz curves).

As the naive costing posits 72-bits of work for a 144-bit group and 56.5-bits of work for a 113-bit group, one might ask why these efforts seem to lag behind the collision/exhaustive results of hash functions and block ciphers. The reason lies in the unit of work which for Pollard attacks is a group operation and for hash and block ciphers is roughly a single encryption/compression. These operations can differ in resources consumption by orders of magnitude.

Rho or Kangaroo Conceptually the Pollard rho and kangaroo algorithms are similar (indeed the use of the terms is rho, lambda and kangaroo frequently overlap and not consistently). One can think of the rho algorithm as an instance of the kangaroo approach where we have a single kangaroo that collides with itself. The rho algorithm is probably slightly easier to implement and Floyd's cycle-finding trick avoids issues with declaring kangaroo traps too early so that the wild kangaroo never hits them. However, the kangaroo approach lends itself much better towards parallelising as a herd of kangaroos can be implemented across several processors. Any two of these kangaroos colliding will solve our problem is roughly the same number of group operations, but now the group operations can be computed in parallel. For this reason kangaroo algorithms are the ones that record-breaking attempts use.

Special Properties of Koblitz curves The best way that I know to use the structure of Koblitz curves is to mod out by the automorphism group which is of order 6, so that instead of $\sqrt n$ in the complexity we get $\sqrt{n/6}$ which saves about 1.3-bits of work. Note that all elliptic curves have an automorphism of order 2 from point negation so that this is really only a speed up of about 0.8 bits. The idea is to use steps in our kangaroo method that respect the automorphism and then only look to collide on equivalence classes of the automorphism. For Koblitz curves this means declaring a collision if two points match $y$-coordinates ignoring sign. The 2010 paper of Duursma, Gaudry and Morain is good place to read up on these ideas.

$\endgroup$
0
$\begingroup$

One method would be to look whether the curve is twist secure. If the curve E is not twist secure, then there exists E' such that E is extended by square root of non-square mod p. If you send a point nP which is not on E but on E' and the other party multiplies its private key m to form Q, if the E' has a smaller subgroup, then you can compute the private key from the counter party because you now have small range to brute force to find m from Q.

$\endgroup$
1
  • 1
    $\begingroup$ This is not a fully satisfying answer, because A) secp256k1 is twist-secure (source). And there is low probability that a curve constructed as secp256k1 appears to be is not twist-secure. B) The attack described would not "compute the private key from the public key": it requires participation of an entity with the private key. $\endgroup$
    – fgrieu
    May 15, 2023 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.