Let $X$ be a point on an elliptic curve such that $X = [x]G$, where $G$ is a generator. Let us assume that we know $x$ is something $x = 65t + 1$ where $t$ is an integer.

Now if I know that the key exist somewhere between a given range $[A, B]$ then which algorithm would be best to apply to find the key $x$?

Will it be brute-force or it will be better with BSGS or pollard-rho?

  • 1
    $\begingroup$ Welcome to Cryptography.se What is the origin of this question? First of all, if you know $x = 65t + 1$ then let $x' = x -1$ and the question is now find $x'$ such that $X' = [x']G = [x]G - G$. For ranges, the Pollard's lambda ( kangaroos ) is the beast. Bruteforce newer helps for $65$ since it only reduces $6$ bits, while Pollard's rho reduced with square-root. $\endgroup$
    – kelalaka
    Nov 14 at 7:43
  • $\begingroup$ Of course, one can combine Pollard's lambda with the knowledge of the special form of $x$ to reduce the search to an interval of length $(B-A)/65$ (gaining 3 bits compared to Pollard's lambda in the interval $[A,B]$ itself). $\endgroup$ Nov 15 at 13:53


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.

Browse other questions tagged or ask your own question.