0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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
    Commented Nov 14, 2023 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$
    – Mehdi Tibouchi
    Commented Nov 15, 2023 at 13:53

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.