So for some context I've been playing with some crypto challenges, and ran into this interesting problem.
There's Montgomery curve
A on its twist with small-ish order
K*A == 0), and
B which is some unknown multiple of
We can brute force every value from
K by generating
C.ladder(A,i) and checking if it equals
B. That's uncomfortably slow even for fairly small
I tried to optimize it a bit, generating
0*A, 1*A, 2*A, 3*A, ... by chained differential addition (from
7*A we can generate
8*A quite quickly etc.) instead of running ladder for each value, and that's about 10x-ish faster, but still not great and $O(K)$.
So if we worked on something which allowed arbitrary point addition, we could just pick
sqrt(K) generate a bunch of baby step values
(U-1)*A, a bunch of giant step values
B+2*(-U*A) etc., and then when we find a collision between those two series by hashing then we know that
k*A == B-j*U*A, so
B=(k+j*U)*A, solving it in $O(\sqrt K)$.
Now awkwardly Montgomery curves don't allow arbitrary addition or subtractions, so what's the options?
- convert to some other kind of curve (like Weierstrass) for sake of the attack, then convert result back? The obvious formulas are for points on the curve, not on its twist, but there could be some way to convert it?.
- is there's some clever way to use differential addition to get those series I want?
- is there some other algorithm which doesn't suffer from this problem?