2
$\begingroup$

Are there any special attacks I can apply if I know the upper bound for $n$ (meaning $0 \le n \le \text{Upper Bound}$) in the equation $Q = nP$, where $P$ is the base point and I'm trying to solve for $n$.

$\endgroup$
3
  • 3
    $\begingroup$ How is this question different from the other one you posted 2 hours ago? (Except that it is more general, since in this case you don't mention to know the factorization of the group order). $\endgroup$
    – tylo
    Apr 5, 2017 at 16:02
  • $\begingroup$ @tylo As that Q was posted as an answer to his/her other question, it was converted to a comment $\endgroup$
    – e-sushi
    Apr 5, 2017 at 19:21
  • $\begingroup$ @user45697 It would definitely help answerers if you'ld provide some context. After all, not everyone will follow the link(s) to your previous questions. While you're at it, you could also describe your research efforts et al... to prevent answerers from repeating the obvious (which you might already know), and to help users to provide more on-point answers to your question. Thanks. $\endgroup$
    – e-sushi
    Apr 5, 2017 at 19:24

2 Answers 2

1
$\begingroup$

As mentioned in your answer to your other similar question, Pollard's $\lambda$ algorithm is still a good choice. If your search interval is $[a,b]$, then it may find the result in $O(\sqrt{b-a})$ time using very small storage.

That "may" in the previous paragraph illustrates the trade-off you must consider. Baby step, giant step requires more memory, but it is deterministic and thus guaranteed to finish in $O(\sqrt{b-a})$ time. Pollard's $\lambda$ can be parallelized which could speed up the run time (depending on your resources), but as it's probabilistic, the run time is not guaranteed at all.

$\endgroup$
1
  • 1
    $\begingroup$ FYI, Pollard's preferred name for the algorithm is the kangaroo algorithm, according to his web site. $\endgroup$ Aug 3, 2017 at 20:37
0
$\begingroup$

The Babystep/giantstep algorithm can find $n$ in $O(\sqrt{\text{Upper Bound}})$ time

$\endgroup$
2
  • $\begingroup$ If the Upper Bound was about 99 bits, would this be a feasible attack or are there better ones? $\endgroup$
    – user45697
    Apr 5, 2017 at 15:51
  • 1
    $\begingroup$ @user45697: unless you have significant resources, it's probably outside your budget. $O(\sqrt{\text{UB}})$ is the best you can do with a generic (group-based) attack, and so any attack will likely require at least $O(2^{50})$ point additions or equivalent; that, in itself, is likely above your budget (assuming your 'budget' is what a single laptop can do). BS/GS also requires a lot of memory; you can reduce it, but at the cost of increasing the time... $\endgroup$
    – poncho
    Apr 5, 2017 at 16:07

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.