Can we reverse elliptic curve function mul?

Question

I have an elliptic curve system with only one point P. Let's say the client A and server B generate a secret R1 and R2.

A is sending X1 = mul(R1, P) to B and B is sending X2 = mul(R2, P) to A then shared secret is the same for both : S = X1R2 = X2R1

The system only have one point and i have X1,X2 and P. I'm trying to compute the shared secret, by calculating R1 and R2. However the curve function is hard to reverse because of the n = n // 2.

The function :

#R is the private number generated client/server side
# P is the point
def mul(R, P):
         
        Q = P.copy()
        Q2 = PointInf()
        while R > 0:
            if R % 2 == 1:
                Q2 = add(Q2, Q)
            Q = add(Q, Q)

            R //= 2
    
        return Q2

On small number n, we can easily reverse the function and find R because there is not a lot of iteration so we can make a aproximation and then bruteforce, but what can we do for big R (my case is 175 iterations) .

Is that mathematically possible ?

Answer 1

What you are describing is Diffie-Hellman on some group with neutral PointInf() [hereafter noted $\infty$] and law add() [hereafter noted $\boxplus$]. The problem statement does not say which, but the title suggests an Elliptic Curve group over some finite field. Function mul(R, P) computes scalar multiplication $R\boxtimes P=\underbrace{P\boxplus \ldots\boxplus P}_{R\text{ terms}}$. From associativity of $\boxplus$ it follows $R\boxtimes P$ is well-defined, and that $R_1\boxtimes (R_2\boxtimes P)=(R_1\times R_2)\boxtimes P=(R_2\times R_1)\boxtimes P=R_2\boxtimes (R_1\boxtimes P)$ [where $\times$ is integer multiplication].

I'm trying to compute the shared secret, by calculating $R_1$ and $R_2$.

$R_2\boxtimes P$ and $R_1\boxtimes P$ are known, thus an attacker only needs to compute $R_1$ or $R_2$ to recover the shared $S$.

On small number $n$, we can easily reverse the function and find $R$ because there is not a lot of iterations, so we can make an approximation and then bruteforce, but what can we do for big $R$ (my case is 175 iterations).

If indeed we are on an Elliptic Curve over some finite field, I don't see how we can "make an approximation". I'll assume both $R_i$ are random in $[0,n)$ with $n\boxtimes P=\infty$ or a similar interval, and $\log_2(n)\approx175$.

Can we reverse Elliptic Curve multiplication?

Finding $R$ given $R\boxtimes P$ and $P$ is the Discrete Logarithm Problem. It's the best known general method to find $S$. The best known general methods to solve the DLP (e.g. distributed Pollard's rho with distinguished points) have cost in the order of $2\sqrt n$ additions, and that's out of reach (unless one can invest billions in designing, producing and running specialized gear). However

• there are much better algorithms for some Elliptic Curves (e.g. supersingular, or when $n$ is composite).
• perhaps one of the $R_i$ is not really random
• perhaps some extra information leaks (like the time required for the computation of $R\boxplus P$, or CPU cache lines used by that computation; both could help).
• or perhaps this is a devious CTF and the problem does not call for finding $S$.