For a finite field elliptic curve we have for a curve of \(y^2 = x^3 + ax +b\) and for a defined prime number (\(p\)). If we have a point \(P\), we can then calculate \(2P\) (and use this to find \(nP\) - where \(n\) is the number of times we add \(P\)) [Calculating nP] In this case we will take a single point (P1), and then all the other points on the curve (P2), and then calculate the resultant addition (P3=P1+P2):
ECC Point Addition Calculator (range) |
Coding
In this case we calculate \(x^3+ax+b \pmod p\). We can add two points \((x_1,y_1)\) and \((x_2,y_2)\):
Let \(s = (y_1-y_2)/(x_1-x_2)\)
Then:
\(x_2 = s^2 - x_1 - x_2\)
\(y_2 = s(x_1 - x_2) - y_1\)
If we add the point (P) to itself, we use:
\(2P = (x_2, y_2)\)
Let \(s = (3x^2 + a)/(2y)\)
Then:
\(x_2 = s^2 - 2x\)
\(y_2 = s(x - x_2) - y\)
import sys import libnum 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]) print("a=",a) print("b=",b) print("p=",p) print("x-point=",x1) z=(x1**3 + a*x1 +b) % p if (libnum.has_sqrtmod(z,{p:1} )): y1=next(libnum.sqrtmod(z,{p:1})) 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=0 if (libnum.has_sqrtmod(z,{p:1} )): y2=next(libnum.sqrtmod(z,{p:1})) if (y2!=0 and x1!=x2): print("P1=(%d,%d)" % (x1,y1), end=' ') print("\tP2=(%d,%d)" % (x2,y2), end=' ') s=(y2-y1)* libnum.invmod(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() if (y2!=0 and x1==x2): print("P1=(%d,%d)" % (x1,y1), end=' ') print("\tP2=(%d,%d)" % (x2,y2), end=' ') s=((3*x1**2)+a) * libnum.invmod(2*y1,p) x2=(s**2-2*x1) % p y2=((s*(x1-x2))-y1) % p print("\tP1+P2=(%d,%d)" % (x2,y2)) if (x2>100): sys.exit()
And a sample run with an x-point of 6:
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)
Presentation
The following is a presentation: