-1
$\begingroup$

I'm working with the secp256k1 elliptic curve and have point doubling and point addition formulas for this curve.

If a point is given $Q_x$ and $Q_y$

Qx = 112711660439710606056748659173929673102114977341539408544630613555209775888121
Qy = 25583027980570883691656905877401976406448868254816295069919888960541586679410

performing point doubling on the given points $Q_x$, $Q_y$ will get the below output

Rx1 = 115780575977492633039504758427830329241728645270042306223540962614150928364886
Ry1 = 78735063515800386211891312544505775871260717697865196436804966483607426560663

Performing point addition on the given points $Q_x$, $Q_y$ will get

Rx2 = 103388573995635080359749164254216598308788835304023601477803095234286494993683
Ry2 = 37057141145242123013015316630864329550140216928701153669873286428255828810018

Now, I'm looking for a way to convert $R_x1$, $R_y1$ to $R_x2$, $R_y2$ without knowing the original given values $Q_x$, $Q_y$. Is there a method or algorithm to achieve this conversion?

$\endgroup$
3
  • 2
    $\begingroup$ Ah, I finally understood what the question means: "Performing point addition on the given points (Qx, Qy)" should be read as "Performing point addition on the given point $Q$ and the known generator $G$ of secp256k1". The stated (Rx2, Ry2) match that reading. So we have $R_1=2Q$ and $R_2=Q+G$. And it's wanted a way to compute the coordinates of $R_2$ from the coordinates of $R_1$. $\endgroup$
    – fgrieu
    Oct 1 at 19:24
  • $\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Cryptography Meta, or in Cryptography Chat. Comments continuing discussion may be removed. $\endgroup$
    – fgrieu
    Oct 3 at 13:54
  • $\begingroup$ Is anything wrong with the detailed answer given? $\endgroup$
    – kodlu
    Oct 7 at 18:32

1 Answer 1

2
$\begingroup$

We are working in the elliptic curve group named secp256k1 over prime field $\mathbb F_p$. The group law is noted $+$, known as point addition (point doubling in the special case of adding a point/element to itself). The group's unity (aka neutral, aka point at infinity) is noted $\mathcal O$. Other elements of the group are noted with capital letters $P$, $Q$, $R$, $G$ and have coordinates $x$ and $y$ in $\mathbb F_p$ with $y^2=x^3+7$ in $\mathbb F_p$, that is $y^2\equiv x^3+7\pmod p$, that is $x^3+7-y^2$ is a multiple of $p$.

The operations necessary to compute the group law $+$ are there, including when we use point doubling or point addition, coverage for the specials cases of adding $\mathcal O$, and of a result that is $\mathcal O$. Formulas formerly in the question did not cover that.

Scalar multiplication aka point multiplication: When $k\in\mathbb N$ and $P$ is an element of the group, we note $k\,P$ for the point $\underbrace{P+P\ldots+P}_{k\text{ terms }P}$ when $k>0$, and $0\,P=\mathcal O$. Usual algebra applies: $(j+k)\,P=(j\,P)+(k\,P)$ and $(j\,k)\,P=j\,(k\,P)$.

The group has known prime order $n$ (that is $n$ elements including $\mathcal O$, with $n$ a known prime). It follows that for any point $P$ in the group, $n\,P=\mathcal O$. That also allows to extend the definition of $k\,P$ to negative $k$.


The question boils down to: knowing that $R_1=2\,Q$ and $R_2=Q+G$, how do we compute the coordinates of $R_2$ from the coordinates of $R_1$ ?


We want to eliminate $Q$ from the two equations. We multiply $R_1=2\,Q$ by the integer $t=2^{-1}\bmod n$ (which is well-defined since $n$ is odd), to get $t\,R_1=t\,(2\,Q)$, thus $t\,R_1=(2t)\,Q$, thus $t\,R_1=(1+i\,n)\,Q$ for some integer $i$, thus $t\,R_1=Q+(i\,(n\,Q))$, thus $t\,R_1=Q+(i\,\mathcal O)$, thus $t\,R_1=Q+\mathcal O$, thus $t\,R_1=Q$. Substituting in $R_2=Q+G$, we get the desired $R_2=(t\,R_1)+G$, with $t\,=\,2^{-1}\bmod n\,=\,(n+1)/2$.

All there remains to do is implement point multiplication. There are methods to compute $t\,R_1$ much faster than with $t-1$ point additions (like with $\approx \log_2(t)$ point doublings and about half as many point additions), much like we can compute $12\times345$ faster than with $11$ additions of $345$ (we compute $x_2=345+345$; $x_4=x_2+x_2$; $x_8=x_4+x_4$; $x_{12}=x_8+x_4$ which is $12\times345$). This is a standard programming exercise, algorithm in the aforementioned wiki on point multiplication.

It's pretty simple. Try it online!

# constants part of the definition of secp256k1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

def add(Q,G):   # point addition, without handling of special cases
    Qx,Qy = Q; Gx,Gy = G
    s = (Qy-Gy)*pow(Qx-Gx,-1,p)%p
    Rx = (s**2-Qx-Gx)%p
    return Rx,(s*(Qx-Rx)-Qy)%p

def dbl(Q):     # point doubling, without handling of special case
    Qx,Qy = Q
    s = (3*Qx**2)*pow(2*Qy,-1,p)%p
    Rx = (s**2-Qx*2)%p
    return Rx,(s*(Qx-Rx)-Qy)%p

def mul(k,P):   # point multiplication, using right-to-left binary multiplication
    Q = (0,0); k %= n
    if k and P[1]: # neither 0*P = O nor k*O = O
        while not k&1:
            P = dbl(P); k >>= 1
        Q = P; k >>= 1
        while k:
            P = dbl(P)
            if k&1: Q = add(P,Q)
            k >>=1
    return Q

R1 = (115780575977492633039504758427830329241728645270042306223540962614150928364886,78735063515800386211891312544505775871260717697865196436804966483607426560663)
Q  = mul((n+1)//2,R1)    # we get Q from R1
R2 = add(Q,G)            # and compute R2
print(R2)

If speed was important, there are so-called point halving equations that allow computing $(2^{-1}\bmod n)\,R_1$ considerably faster than by point multiplication. That's being discussed here.

$\endgroup$
1
  • $\begingroup$ Well, only almost: because the code for add(Q,G) is taken from the original question, it does not handle Q one of $G$, $-G$, or $\mathcal O$, that is R1 one of $2G$, $-2G$, or $\mathcal O$. @AvirilSmith $\endgroup$
    – fgrieu
    Oct 8 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.