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$.
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$– tyloCommented 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-sushiCommented 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-sushiCommented Apr 5, 2017 at 19:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ FYI, Pollard's preferred name for the algorithm is the kangaroo algorithm, according to his web site. $\endgroup$ Commented Aug 3, 2017 at 20:37
$\begingroup$
$\endgroup$
2
The Babystep/giantstep algorithm can find $n$ in $O(\sqrt{\text{Upper Bound}})$ time
-
$\begingroup$ If the Upper Bound was about 99 bits, would this be a feasible attack or are there better ones? $\endgroup$ Commented 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$– ponchoCommented Apr 5, 2017 at 16:07