Curve 25519 is one of the most widely used ECC methods. It uses a curve of \(y^2 = x^3 + 486662 x^2 + x\) [plot], and which is a Montgomery curve. The prime number used is \(2^{255}-19\). In this case we will use Python to implement X25519 (and which uses Curve 25519), but only uses the x-axis point for the sharing of values. The base point \(G\) on Curve 25519 is (9,1478161944 ... 7755586237401). With X25519 we typically discard the y co-ordinate value, and only use the x-co-ordinate [secp256k1 barebones][P256 barebones][P521 barebones][Curve 25519 barebones]:
Barebones Curve 25519: Scalar Multiply on the curve (Python)TheoryCurve 25519 is one of the most widely used ECC methods. It uses a curve of: \(y^2 = x^3 + 486662 x^2 + x\) This is a Montgomery curve. The prime number used is \(2^{255}-19\). In this case we will use Python to implement X25519 (and which uses Curve 25519), but only uses the x-axis point for the sharing of values. The base point \(G\) on Curve 25519 is (9,1478161944 ... 7755586237401) The simplest operations we have is to take a base point (\(G\)) and then perform point addition and where \(2G\) is equal to \(G+G\) and where we get a new point on the elliptic curve. For \(3G\) we can have \(G+2G\), and so on. We can also perform a scalar multiplication, such as taking a scalar of \(3\) and finding \(3G\). In the following code we have three scalar values of 1, 2 and 3, and then use point addition and scalar multiplication to find \(2G\) and \(3G\). import sys import curve25519 import random import ecc1 def getPoint(n,x): x2 = curve25519.X25519(n, x) z2= (x2**3+a*(x2**2)+x2) % p y2=ecc1.modular_sqrt(z2, p) return(x2,y2) type='Curve25519_Montgomery' p = pow(2,255)-19 a =486662 b=1 x=9 # Base point order = 57896044618658097711785492504343953926856930875039260848015607506283634007912 val=1 # Compute valG if (len(sys.argv)>1): val=int(sys.argv[1]) print ("Curve 25519 (Montgomery)") n=1 G = getPoint(n,x) print (f"Point {n}G: {G}") n=2 G2 = getPoint(n,x) print (f"Point {n}G: {G2}") n=3 G3 = getPoint(n,x) print (f"Point {n}G: {G3}") Gv = getPoint(val,x) print (f"\nPoint {val}G: {Gv}") (xval,y) = Gv xval=xval.to_bytes(32, byteorder='little').hex() print (f"\n Hex: {xval}") val=random.randint(0,order) Gv = getPoint(val,x) print (f"\nPoint {val}G: {Gv}") (xval,y) = Gv xval=xval.to_bytes(32, byteorder='little').hex() print (f"\n Hex: {xval}") And Curve 25519 code: import os import binascii P = 2 ** 255 - 19 A24 = 121665 def cswap(swap, x_2, x_3): dummy = swap * ((x_2 - x_3) % P) x_2 = x_2 - dummy x_2 %= P x_3 = x_3 + dummy x_3 %= P return (x_2, x_3) # Based on https://tools.ietf.org/html/rfc7748 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 def decodeScalar25519(k): k_list = [(b) for b in k] k_list[0] &= 248 k_list[31] &= 127 k_list[31] |= 64 return decodeLittleEndian(k_list) def decodeLittleEndian(b): return sum([b[i] << 8*i for i in range( 32 )]) def unpack2(s): if len(s) != 32: raise ValueError('Invalid Curve25519 scalar (len=%d)' % len(s)) t = sum((ord(s[i]) ) << (8 * i) for i in range(31)) t += (((ord(s[31]) ) & 0x7f) << 248) return t def pack(n): return ''.join([chr((n >> (8 * i)) & 255) for i in range(32)]) def clamp(n): n &= ~7 n &= ~(128 << 8 * 31) n |= 64 << 8 * 31 return n # Return nP def multscalar(n, p): n = clamp(decodeScalar25519(n)) p = unpack2(p) return pack(X25519(n, p)) # Start at x=9. Find point n times x-point def base_point_mult(n): n = clamp(decodeScalar25519(n)) return pack(X25519(n, 9)) A sample run shows that \(2G\) is equal to \(G+G\), and \(3G\) is equal to \(G+2G\): Curve 25519 (Montgomery) Point 1G: (9, 14781619447589544791020593568409986887264606134616475288964881837755586237401) Point 2G: (14847277145635483483963372537557091634710985132825781088887140890597596352251, 48981431527428949880507557032295310859754924433568441600873610210018059225738) Point 3G: (12697861248284385512127539163427099897745340918349830473877503196793995869202, 18782504731206017997790968374142055202547214238579664877619644464800823583275) Point 2G: (14847277145635483483963372537557091634710985132825781088887140890597596352251, 48981431527428949880507557032295310859754924433568441600873610210018059225738) Hex: fb4e68dd9c46ae5c5c0b351eed5c3f8f1471157d680c75d9b7f17318d542d320 Point 35328789825008225085423720304553163911213545686500336875485410840708834922917G: (36398665667544205244634731527062357032440495857132569185918282653838713250635, 7341733635090260818431183457302662788058419874597118533119166883295593161347) Hex: 4b631f0efcec99ce636b20d954b84a01cf7c6a46620af1dc23646db529ea7850 |