Skip to main content
Cryptography

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

2
  • $\begingroup$ For the second problem (kudos for simplifying it), on secp256k1 one of the least prohibitively costly algorithm I come up with takes $G'=((p+1)/2)G$ (which has an unusually small $\overline{x_{kG}}$, allowing slightly optimized point addition) then computes $k'G'$ for $k'$ increasing from $1$, until one has $\overline{x_{k'G'}}\geq n$. It's then easy to get your $k$ from $k'$. We expect $p/(p-n)\approx2^{127.7}$ point additions of $G'$. This indeed in only marginally less costly than ECDLP. However that a brute force algorithm is impractical is far from proof that there is no practical one. $\endgroup$ Commented Dec 8, 2024 at 6:05
  • 1
    $\begingroup$ @fgrieu You can do faster iteration by doing repeated doubling, rather than adding a constant (the multiplicative order of 2 mod $n$ is high enough to never cycle), and for each iteration you can consider 6 points (original, its negation, and for each the 3 points obtained by multiplying the X coordinate with powers of $\sqrt[3]{1}$, exploiting the GLV endomorphism). Also, you can batch convert from jacobian to affine coordinates to avoid ~all modular inverses. But yes, none of this changes the fact that it needs close to $2^{128}$ operations. $\endgroup$ Commented Dec 8, 2024 at 15:55