Curve 25519 uses a Montgomery curve of the form of \(y^2 = x^3+a x^2+x \pmod p\). If we have a point \(P\), we then find a point \(nP\) - where \(n\) is the number of times we add \(P\)). Curve 25519 takes the form of \(y^2 = x^3+486662 x^2+x \pmod p\) and a base point at \(x=9\). This gives a base point (\(G\)), and where we find the point \(nG\) for a given \(n\) value, and where \(n\) is the private key value, and \(nG\) is the public key point. Normally in Curve 25519 we only focus on the x-point, and do not need the \((x,y)\) value.
Finding nG for Curve 25519 |
Curve 25519:
\(y^2 = x^3+486662 x^2+x \pmod p\)
\(p = 2^{255} - 19\). This is represented as \(\mathbb{F}_{2^{255}-19}\) and where the generator point \(G\) is at \(x=9\).
For Curve 25519, for point addition, we use the method defined in RFC 7748 [here]. The follows takes an x-point of \(u\) and adds it \(k\) times:
def X25519(k, u): x_1 = u x_2 = 1 z_2 = 0 x_3 = u z_3 = 1 swap = 0 for t in reversed(range(255)): k_t = (k >> t) & 1 swap ^= k_t x_2, x_3 = cswap(swap, x_2, x_3) z_2, z_3 = cswap(swap, z_2, z_3) swap = k_t A = x_2 + z_2 A %= P AA = A * A AA %= P B = x_2 - z_2 B %= P BB = B * B BB %= P E = AA - BB E %= P C = x_3 + z_3 C %= P D = x_3 - z_3 D %= P DA = D * A DA %= P CB = C * B CB %= P x_3 = ((DA + CB) % P)**2 x_3 %= P z_3 = x_1 * (((DA - CB) % P)**2) % P z_3 %= P x_2 = AA * BB x_2 %= P z_2 = E * ((AA + (A24 * E) % P) % P) z_2 %= P x_2, x_3 = cswap(swap, x_2, x_3) z_2, z_3 = cswap(swap, z_2, z_3) return (x_2 * pow(z_2, P - 2, P)) % P
Coding
The following is the code:
import sys import libnum import ecc import curve25519 type='Curve25519_Montgomery' p = pow(2,255)-19 a =486662 b=1 n=2 # Compute nG y=0 if (len(sys.argv)>1): n=int(sys.argv[1]) print("Type: ",type) x=9 # Base point 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() x2 = curve25519.X25519(2, x) z2= (x2**3+a*(x2**2)+x2) y2=ecc.modular_sqrt(z2, p) print("a=",a) print("b=",b) print("p=",p) print("n=",n) print("\nG=(",x,",",y,")") print("nG=(",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:") print ("\nx^3+ax^2+x (mod p)=",(x2**3+a*(x2**2)+x2) % p) print ("y^2 (mod p)=", (y2**2)% p)
Sample run
A sample run for 1G is:
Type: Curve25519_Montgomery a= 486662 b= 1 p= 57896044618658097711785492504343953926634992332820282019728792003956564819949 n= 1 P=( 9 , 14781619447589544791020593568409986887264606134616475288964881837755586237401 ) nP=( 9 , 14781619447589544791020593568409986887264606134616475288964881837755586237401 ) === 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)= 39420360 y^2 (mod p)= 39420360
And a sample run for 10G is:
Type: Curve25519_Montgomery a= 486662 b= 1 p= 57896044618658097711785492504343953926634992332820282019728792003956564819949 n= 10 G=( 9 , 14781619447589544791020593568409986887264606134616475288964881837755586237401 ) nG=( 29820225912430724043036921744240028624897194250362921729082802159805426998395 , 27477231867808634946398188422234309688498245134990516833583512853248786744311 ) === 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)= 22295725891182109027541692427696289635999881090180249327664424935048136527970 y^2 (mod p)= 22295725891182109027541692427696289635999881090180249327664424935048136527970