1
$\begingroup$

For generator point $G$ in the secp256k1 curve, I want to find a value $k$ such that: $$h\equiv(k\,G)_X\,(k-d)\pmod n$$ where $n$ is the group order, and $(k\,G)_X$ indicates the x-coordinate (mod n) of the resulting point after the multiplication by $k$. Assume $h$ and $d$ are fixed scalar values that I've been given.

Is it possible to calculate $k$?

Without the multiplication by $(k - d)$, this would just be the ECC discrete log problem. Does having that extra multiplication make it easier to calculate some $k$, or is there a way to show that it still reduces to the discrete log problem?

In my experiments with smaller fields, it appears that no such $k$ value exists about 35% of the time.

$\endgroup$
4
  • $\begingroup$ I'd be surprised is this was sizably easier than the DLP, and would not be surprised if it was much harder: I fail to think of a $\mathcal O(\sqrt n\,\ln(n)\ln(\ln(n)))$ algorithm to solve this, when there are for the DLP. $\endgroup$
    – fgrieu
    Aug 1, 2022 at 20:06
  • $\begingroup$ @fgrieu I was actually hoping as much. It would be nice to have a proof that it's at least as hard, but it certainly makes sense intuition-wise. Thanks. $\endgroup$ Aug 1, 2022 at 20:29
  • 1
    $\begingroup$ cross-posted math.se $\endgroup$
    – kelalaka
    Aug 3, 2022 at 23:03
  • $\begingroup$ Once more, $(kG)_X$ is only well defined modulo $p$. It is not well defined modulo $n$. $\endgroup$ Aug 10, 2022 at 5:30

0

Your Answer

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