Score:2

Can we reverse elliptic curve function mul?

cn flag

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 ?

Score:2
ng flag

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$.
cn flag
Ok. Thanks for the explanation. Yes indeed R is fully random and really big so yeah guessing is completely impossible. Gonna check the supersingular algorithm and distributed Pollard's to check if this can help me in my problem (it is indeed a ctf ). When you say Extra information leaks, what information could help us to recover R1 or R2 ?
fgrieu avatar
ng flag
@ThibaultPoncetta: see updated butlast bullet. [update: see penultimate bullet point]
cn flag
butlast bullet ? Do you have another word to describe it ? I don't find a traduction of this ^^.
fgrieu avatar
ng flag
In my _butlast bullet (point)_, the _butlast_ is trying to mean: before the last (it's common in computer science, but I don't know if it's attested elsewhere as a single word [update: see comment below, it has a different meaning]). And [_bullet_](https://en.wikipedia.org/wiki/Bullet_(typography)) is a typographical term, designating the symbol (often a black disc) introducing an item in a list. I'm not a native English speaker, so beware of my explanations about that!
cn flag
okay! thanks. first time seeing bullet word like this.
us flag
This is getting off-topic, but as a native speaker of American English who has studied CS for over 20 years, this is the first time I've ever seen the word "butlast." I would use "penultimate" to mean the $(n-1)$th item in a list of $n$ items, or even "next-to-last" to sound less fancy. A quick search (i.e., I might be missing other usages) shows "butlast" being used to mean items 1 through $n-1$ -- all items but the last -- rather than only the $(n-1)$th item.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.