2

Please tell me if there is a formula for A-B, (That is, subtraction of two points / minus). I know how two points are added, A + B this addition is described in detail

(Please tell me how you can change the formula to subtract two points / minus) A-B

  • There are many different types of elliptic curves. Please note that the given answers apply to secp256k1, the curve used in Bitcoin. – nickler Jan 16 at 18:22
  • @nickler incorrect. The geometric addition rule holds for all elliptic curves and that is the basis for the negation rule described in the several answers existing before your comment was written. – Chan-Ho Suh Feb 7 at 5:13
  • The negation of a point (x, y) on a twisted Edwards curve is (-x, y) and not (x, -y) as the answers given here would indicate. – nickler Feb 10 at 14:39
  • @nickler there's confusion here between elliptic curve representation and the elliptic curve itself. When not specified, it's standard to assume the form is Weisterstrass; you are referring to a particular non-standard form. The answers given apply to any elliptic curve in Weierstrass form. To state that they only apply to secp256k1 is wrong. – Chan-Ho Suh Feb 14 at 14:07
  • I didn't state it would only apply to secp256k1. My comment was intended to address confusion about the different forms of elliptic curves because we can't expect readers to be aware of what some people consider standard and how the curves relate to each other. – nickler Feb 17 at 12:15
4

You can negate a point (x, y) by simply changing it to (x, −y).

The document that defines ECDSA reminds us of this fact:

https://www.secg.org/sec1-v2.pdf

Here's a screenshot:

Definition of point negation

So once you have negated one of your points, just add it to the other one, and you have achieved subtraction.

| improve this answer | |
1

As other's have said, the essential point is the algebraic definition for additive inverses in elliptic arithemetic.

 -(x,y)=(x,-y)

But if it helps, there are also some nice geometric illustrations like this one from Vitalik Buterin's Exploring Elliptic Curve Pairings:

Elliptic arithmetic

Suppose R = (x,y). Since the elliptic curve is symmetric with respect to the x-axis, we can guarantee that the inverse -R = -(x,y) = (x,-y) will also be a point on the curve. And since R and -R have the same x-coordinate, the line that connects them is vertical representing their sum as the identity O or "the point at infinity". So we have R + (-R) = O as required.

| improve this answer | |
0

Here is the sample of code for subtraction of two points.

# -*- coding: utf-8 -*-

def OnCurve(x,y): # Check if the point is on the curve
    A = (y*y)%P
    B = (x*x*x)%P
    C = False
    if A == (B + 7):
        C = True
    return C

def ECadd(xp,yp,xq,yq): # EC point addition
    m = ((yq-yp) * modinv(xq-xp,P))%P
    xr = (m*m-xp-xq)%P
    yr = (m*(xp-xr)-yp)%P
    return (xr,yr)

def legendre_symbol(a,p):
    ls = pow(a, (p - 1) / 2, p)
    return -1 if ls == p - 1 else ls

def modsqrt(a,p):
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return p
    elif p % 4 == 3:
        return pow(a, (p + 1) / 4, p)
    s = p - 1
    e = 0
    while s % 2 == 0:
        s /= 2
        e += 1
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1
    x = pow(a, (s + 1) / 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e
    while True:
        t = b
        m = 0
        for m in xrange(r):
            if t == 1:
                break
            t = pow(t, 2, p)
        if m == 0:
            return x
        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m

def modinv(a,n): # Extended Euclidean Algorithm in elliptic curves
    lm, hm = 1,0
    low, high = a%n,n
    while low > 1:
        ratio = high/low
        nm = hm - lm * ratio
        new = high - low * ratio
        hm = lm
        high = low
        lm = nm
        low = new
    return lm % n

def ECadd(xp,yp,xq,yq): # EC point addition
    m = ((yq-yp) * modinv(xq-xp,P))%P
    xr = (m*m-xp-xq)%P
    yr = (m*(xp-xr)-yp)%P
    return (xr,yr)

def ECsub(xp,yp,xq,yq): # EC point subtraction
    X = (((yp+yq)*modinv(xq-xp,P))**2-xp-xq)%P
    A = (xp + X + xq)%P
    B = modsqrt(A,P)
    B1 = P - B
    Y = yq - (xq - X) * B
    X = X % P
    Y = Y % P
    if not OnCurve(X,Y):
        Y = yq - (xq - X) * B1
    Y = Y % P
    return X,Y

P = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1

Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424

print Gx,Gy

Ax,Ay = ECadd(Gx,Gy,Gx,Gy)
print Ax,Ay

Bx,By = ECsub(Ax,Ay,Gx,Gy)
print Bx,By

This code is from here.

It works perfect in Python 2.7.13.

In the earlier version of Python there is OverflowError: (34, 'Result too large').

| improve this answer | |
  • Please explain in this code what point values do the subtraction? – Izi Tors Feb 5 at 5:47
  • @IziTors i'am sorry but I can not understand your question – Denis Leonov Feb 5 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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