In ECC, If We Add Two Points on the Curve, We Always Get Another Point on the Curve

In ECC, If We Add Two Points on the Curve, We Always Get Another Point on the Curve

Elliptic Curve Cryptography (ECC) protects your online identity and your privacy like few other things. With ECC, we take our equation of y²=x³ +7 (mod 37), and where we have valid points of: (3, 16) (4, 16) (5, 13) (6, 1) (8, 1) (9, 12) (12, 12) (13, 13) (16, 12) (17, 6) (18, 17) (19, 13) (22, 6) (23, 1) (24, 17) (30, 16) (32, 17) (35, 6) [here]. For example if x=3, we get 3³+7=34, and where 16² (mod 37) = 34. The graph is here.

With ECC, if we have a point on the curve, and then add another point, we will always get another point on the curve. It is this property that allows ECC to implement cryptography.

So, let’s try one point, and calculate the addition to it with all the other points. If (x1,y1) is not equal to (x2,y2), to two points (x1,y1) and (x2,y2), we use:

Let s=(y1−y2)/(x1−x2)

Then:

x2=s²−x1−x2

y2=s(x1−x2)−y1

If they are the same point (x1,y1), we use:

s=((3*x1²)+a) /(2*y1,p)

x2=(s²–2*x1)

y2=((s(x1-x2))-y1)

Here is a program to implement this [here]:

import sys

a=0
b=7
p=37

x1=6
x2=8

if (len(sys.argv)>1):
    x1=int(sys.argv[1])
if (len(sys.argv)>2):
    p=int(sys.argv[2])
if (len(sys.argv)>3):
    a=int(sys.argv[3])
if (len(sys.argv)>4):
    b=int(sys.argv[4])
if (len(sys.argv)>5):
    n=int(sys.argv[5])

def modular_sqrt(a, p):
    """ Find a quadratic residue (mod p) of 'a'. p
        must be an odd prime.

        Solve the congruence of the form:
            x^2 = a (mod p)
        And returns x. Note that p - x is also a root.

        0 is returned is no square root exists for
        these a and p.

        The Tonelli-Shanks algorithm is used (except
        for some simple cases in which the solution
        is known from an identity). This algorithm
        runs in polynomial time (unless the
        generalized Riemann hypothesis is false).
    """
    # Simple cases
    #
    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)

    # Partition p-1 to s * 2^e for an odd s (i.e.
    # reduce all the powers of 2 from p-1)
    #
    s = p - 1
    e = 0
    while s % 2 == 0:
        s /= 2
        e += 1

    # Find some 'n' with a legendre symbol n|p = -1.
    # Shouldn't take long.
    #
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1

    # Here be dragons!
    # Read the paper "Square roots from 1; 24, 51,
    # 10 to Dan Shanks" by Ezra Brown for more
    # information
    #

    # x is a guess of the square root that gets better
    # with each iteration.
    # b is the "fudge factor" - by how much we're off
    # with the guess. The invariant x^2 = ab (mod p)
    # is maintained throughout the loop.
    # g is used for successive powers of n to update
    # both a and b
    # r is the exponent - decreases with each update
    #
    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 legendre_symbol(a, p):
    """ Compute the Legendre symbol a|p using
        Euler's criterion. p is a prime, a is
        relatively prime to p (if p divides
        a, then a|p = 0)

        Returns 1 if a has a square root modulo
        p, -1 otherwise.
    """
    ls = pow(a, (p - 1) / 2, p)
    return -1 if ls == p - 1 else ls

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    a=a%p
    g, x, y = egcd(a, m) 
    if g != 1:
        print "x-point is not on the curve. Please select another point. No solution for %d (mod %d)" % (a,m)
    sys.exit()
    else: 
       return x % m

print "a=",a
print "b=",b
print "p=",p

print "x-point=",x1

z=(x1**3 + a*x1 +b) % p
y1=modular_sqrt(z, p)
if (y1==0):         
    print "No solution for y1 on curve. Please select another x-point."
    sys.exit()

for x2 in range(2,p-1):
    z=(x2**3 + a*x2 +b) % p
    y2=modular_sqrt(z, p)
    
    if (y2!=0 and x1!=x2):         
        print "P1=(%d,%d)" % (x1,y1),
        print "\tP2=(%d,%d)" % (x2,y2),

        s=(y2-y1)* modinv(x2-x1,p) 

        x3=(s**2-x2-x1) % p

        y3=((s*(x2-x3)-y2)) % p

        print "\tP1+P2=(%d,%d)" % (x3,y3)
        if (x2>100): sys.exit()

And a sample run for a point (6,1) [here] is:

a= 0
b= 7
p= 37
x-point= 6
P1=(6,1)  P2=(3,16)  P1+P2=(16,12)
P1=(6,1)  P2=(4,16)  P1+P2=(0,28)
P1=(6,1)  P2=(5,13)  P1+P2=(22,6)
P1=(6,1)  P2=(6,1)  P1+P2=(18,17)
P1=(6,1)  P2=(8,1)  P1+P2=(23,36)
P1=(6,1)  P2=(9,12)  P1+P2=(19,13)
P1=(6,1)  P2=(12,12)  P1+P2=(9,12)
P1=(6,1)  P2=(13,13)  P1+P2=(30,16)
P1=(6,1)  P2=(16,12)  P1+P2=(4,16)
P1=(6,1)  P2=(17,6)  P1+P2=(35,6)
P1=(6,1)  P2=(18,17)  P1+P2=(23,1)
P1=(6,1)  P2=(19,13)  P1+P2=(3,16)
P1=(6,1)  P2=(22,6)  P1+P2=(13,13)
P1=(6,1)  P2=(23,1)  P1+P2=(8,36)
P1=(6,1)  P2=(24,17)  P1+P2=(32,17)
P1=(6,1)  P2=(30,16)  P1+P2=(17,6)
P1=(6,1)  P2=(32,17)  P1+P2=(32,20)
P1=(6,1)  P2=(35,6)  P1+P2=(12,12)

In this case we see the 2P is (18,17). We can also see that a point is generated for each addition, so that if we add two points on the elliptic curve we always get a point on the curve.

Conclusions

There we go. Take a point on the curve, and add it to itself, and you get another point on the curve. Take two points, too, and add them, and you get another point on the curve. Magic!