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$.