Discrete logarithm on Montgomery curve twist

Question

So for some context I've been playing with some crypto challenges, and ran into this interesting problem.

There's Montgomery curve C, point A on its twist with small-ish order K (so K*A == 0), and B which is some unknown multiple of A.

We can brute force every value from 0 to K by generating C.ladder(A,i) and checking if it equals B. That's uncomfortably slow even for fairly small K.

I tried to optimize it a bit, generating 0*A, 1*A, 2*A, 3*A, ... by chained differential addition (from A, 6*A, and 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 U about sqrt(K) generate a bunch of baby step values 0*A, 1*A, 2*A, ..., (U-1)*A, a bunch of giant step values B+0*(-U*A),B+1*(-U*A), 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?

Answer 1

So I guess I'll answer myself as I finally figured it out:

• twist of a curve is a curve - all possible curves with same A are isomorphic to either $B=1$ (your base curve if you use usual curve) or $B=-1$ (your twist curve) curve, so just pick whichever and be consistent.
• every Montgomery curve has Weierstrass curve. Your choice of B matters which one you get exactly, but end result will be same.
• (not every Weierstrass curve has Montgomery curve, but you already have equivalent curve - your original twist curve)
• so map points to Weierstrass form, get logarithms by baby step giant step (or other fast algorithm), map points back, for each prime on the twist you'll get two answers ($k$ and $-k$).
• if there are z primes, then $2^z$ answers can be reduced to just $4$ in $O(z)$ steps with Chinese Reminder Theorem and filter.
• that doesn't give you unique answer, but very small number ($4x4$ in my case), so you can just test them all.

I didn't completely follow the math for factors of $2$ and duplicate primes. Twist order has factor of $2^2$ and then only unique primes, that's presumably why it's been $4$ not $2$.

I'm sure there's some way to optimize higher powers of same prime, I just didn't need it.