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\)). This is defined as a Weierstrass curve. For Curve 25519 the form is \(y^2 = x^3+a x^2+x \pmod p\), and is known as the Montgomery form. 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\)). In this case we will use the parameters for \(a\), \(b\) and \(p\) for some real curves [Simple]:
Finding 2P when we have P for EC (for real curves) |
secp256k1:
\(y^2 = x^3+0x+7 \pmod p\)
\(p = 2^{256} - 2^{32} - 977\). This is represented as \(\mathbb{F}_{2^{256}-2^{32}-997}\).
Curve 25519:
\(y^2 = x^3+486662 x^2+x \pmod p\)
\(p = 2^{255} - 19\). This is represented as \(\mathbb{F}_{2^{255}-1}\).
NIST P256:
\(y^2 = x^3-3x+41058363725152142129326129780047268409114441015993725554835256314039467401291 \pmod p\)
\(p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\). This is represented as \(\mathbb{F}_{2^{256} - 2^{224} + 2^{192} + 2^{96} - 1}\).
Coding
In this case we calculate \(x^3+ax+b \pmod p\). For point addition of \(P\) (\(x,y\)) we calculate the point addition for a given point (\(P+P\)) and represent it by (\(2P\)). For this we have:
\(2P = (x_2, y_2)\)
Let \(s = (3x^2 + a)/(2y)\)
Then:
\(x_2 = s^2 - 2x\)
\(y_2 = s(x - x_2) - y\)
For Curve 25519, for point addition, we use the method defined in RFC 7748 [here].
Coding
import sys import libnum import ecc import curve25519 a=0 b=7 t=2 # t=1 SECP256k1, t=2 25519, t=3 P256, t=4 SECP160k1 x=9 y=0 if (len(sys.argv)>1): x=int(sys.argv[1]) if (len(sys.argv)>2): t=int(sys.argv[2]) if (t==1): type='SECP256k1' p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f a=0 b=7 if (t==2): type='Curve25519_Montgomery' p = pow(2,255)-19 a =486662 b=1 if (t==3): type='NIST P256' a = -3 b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 if (t==4): type='SECP160k1' a = 0 b = 7 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73 print("Type: ",type) z=(x**3 + a*x +b) % p if (t==2): z=(x**3 + a*(x**2) +x) % p # if (libnum.has_sqrtmod(z,{p:1} )): # y=next(libnum.sqrtmod(z,{p:1})) y=ecc.modular_sqrt(z, p) if (y==0): print ("x-point is not on the curve. Please select another point. No solution for %d (mod %d)" % (z,p)) sys.exit() if (t!=2): s=((3*(x**2))+a) * libnum.invmod(2*y,p) # s=((3*x**2)+a) * ecc.modinv(2*y,p) x2=(s**2-2*x) % p y2=((s*(x-x2))-y) % p else: x2 = curve25519.X25519(2, x) z2= (x2**3+a*(x2**2)+x2) y2=ecc.modular_sqrt(z2, p) s=0 print("a=",a) print("b=",b) print("p=",p) print("s=",s) print("\nP=(",x,",",y,")") print("2P=(",x2,",",y2,")") print("\n=== Just checking for (x2, y2).") print("These have to be the same, to prove that 2P is on the elliptic curve:") if (t!=2): print ("\nx^3+ax+b (mod p)=",(x2**3+a*x2+b) % p) else: print ("\nx^3+ax^2+x (mod p)=",(x2**3+a*(x2**2)+x2) % p) print ("y^2 (mod p)=", (y2**2)% p)
And a sample run:
And a sample run: Type: SECP256k1 a= 0 b= 7 p= 115792089237316195423570985008687907853269984665640564039457584007908834671663 x-point= 1 s= 309559869782811709114791466953038768572873897589664974937917787940921749681528 P=( 1 , 29896722852569046015560700294576055776214335159245303116488692907525646231534 ) 2P=( 90462569716653277674664832038037428010367175520031690655826237506178777087235 , 30122570767565969031174451675354718271714177419582540229636601003470726681395 ) === Just checking for (x2, y2). These have to be the same, to prove that 2P is on the elliptic curve: x^3+ax+b (mod p)= 64938697018864737649504516342305227130723343145766499186801514322306538536414 y^2 (mod p)= 64938697018864737649504516342305227130723343145766499186801514322306538536414
and for Curve 25519:
Type: Curve25519_Montgomery a= 486662 b= 1 p= 57896044618658097711785492504343953926634992332820282019728792003956564819949 x-point= 9 Z= 39420360 Y= 14781619447589544791020593568409986887264606134616475288964881837755586237401 s= 0 P=( 9 , 14781619447589544791020593568409986887264606134616475288964881837755586237401 ) 2P=( 14847277145635483483963372537557091634710985132825781088887140890597596352251 , 48981431527428949880507557032295310859754924433568441600873610210018059225738 ) === Just checking for (x2, y2). These have to be the same, to prove that 2P is on the elliptic curve: x^3+ax^2+x (mod p)= 33907837233136750156209621146237833792591564891953031467287095746800606444521 y^2 (mod p)= 33907837233136750156209621146237833792591564891953031467287095746800606444521
Presentation
The following is a presentation: