The NIST P256 curve uses a form of \(y^2=x^3+ax+b\) and specifically as \(y^2 = x^3-3x+41058363725152142129326129780047268409114441015993725554835256314039467401291\) and a finite field of \(p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\). The base point (\(G\) is at and the base point is at (48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) [secp256k1 barebones][P256 barebones][P521 barebones][Curve 25519 barebones]:
Barebones P256: Adding and Scalar Multiply on the curve (Python)TheoryThe NIST P256 curve uses a form of \(y^2=x^3+ax+b\) and specifically as: \(y^2 = x^3-3x+41058363725152142129326129780047268409114441015993725554835256314039467401291\) and a finite field of: \(p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\) 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\), and where we should get the same values as \(G+G\) and \(G+2G\), respectively. Note, in NIST P256, we the point on the curve is defined with a \((x,y)\) value [secp256k1 barebones][P256 barebones][P512 barebones. import random from p256 import scalar_mult,point_add,curve import sys def toHex(val,Gv): (x,y) = Gv x=hex(x) y=hex(y) print (f"({val}G) in hex: {x},{y})\n") val=1 if (len(sys.argv)>1): val=int(sys.argv[1]) print ("P256") n=1 G = scalar_mult(n,curve.g) print (f"Point {n}G: {G}") toHex(n,G) n=2 G2 = scalar_mult(n,curve.g) print (f"Point {n}G: {G2}") toHex(n,G2) n=3 G3 = scalar_mult(n,curve.g) print (f"Point {n}G: {G3}") toHex(n,G3) G_G = point_add(G,G) print (f"\nG+G: {G_G}") G_2G = point_add(G,G2) print (f"\nG+2G: {G_2G}") Gv = scalar_mult(val,curve.g) print (f"\nPoint {val}G: {Gv}") val=random.randint(0,curve.n) Gv = scalar_mult(val,curve.g) print (f"\nPoint {val}G: {Gv}") And NIST P-256 code: import collections import random import libnum EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') p1=2**256 - 2**224 + 2**192 + 2**96 - 1 curve = EllipticCurve( 'P-256', # Field characteristic. p=p1, # Curve coefficients. a=-3, b=41058363725152142129326129780047268409114441015993725554835256314039467401291, # Base point. g=(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109), # Subgroup order. n=0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551, # Subgroup cofactor. h=1, ) # Modular arithmetic ########################################################## def inverse_mod(k, p): """Returns the inverse of k modulo p. This function returns the only integer x such that (x * k) % p == 1. k must be non-zero and p must be a prime. """ if k == 0: raise ZeroDivisionError('division by zero') if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p) # Extended Euclidean algorithm. s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = p, k while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t gcd, x, y = old_r, old_s, old_t assert gcd == 1 assert (k * x) % p == 1 return x % p # Functions that work on curve points ######################################### def is_on_curve(point): """Returns True if the given point lies on the elliptic curve.""" if point is None: # None represents the point at infinity. return True x, y = point return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0 def point_add(point1, point2): """Returns the result of point1 + point2 according to the group law.""" assert is_on_curve(point1) assert is_on_curve(point2) if point1 is None: # 0 + point2 = point2 return point2 if point2 is None: # point1 + 0 = point1 return point1 x1, y1 = point1 x2, y2 = point2 if x1 == x2 and y1 != y2: # point1 + (-point1) = 0 return None if x1 == x2: # This is the case point1 == point2. m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p) else: # This is the case point1 != point2. m = (y1 - y2) * inverse_mod(x1 - x2, curve.p) x3 = m * m - x1 - x2 y3 = y1 + m * (x3 - x1) result = (x3 % curve.p, -y3 % curve.p) assert is_on_curve(result) return result def scalar_mult(k, point): """Returns k * point computed using the double and point_add algorithm.""" assert is_on_curve(point) if k % curve.n == 0 or point is None: return None if k < 0: # k * point = -k * (-point) return scalar_mult(-k, point_neg(point)) result = None addend = point while k: if k & 1: # Add. result = point_add(result, addend) # Double. addend = point_add(addend, addend) k >>= 1 assert is_on_curve(result) return result def point_neg(point): """Returns -point.""" assert is_on_curve(point) if point is None: # -0 = 0 return None x, y = point result = (x, -y % curve.p) assert is_on_curve(result) return result A sample run shows that \(2G\) is equal to \(G+G\), and \(3G\) is equal to \(G+2G\), and that \(2G-G=G\) [test vectors]: P256 Point 1G: (48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) (1G) in hex: 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5) Point 2G: (56515219790691171413109057904011688695424810155802929973526481321309856242040, 3377031843712258259223711451491452598088675519751548567112458094635497583569) (2G) in hex: 0x7cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978, 0x7775510db8ed040293d9ac69f7430dbba7dade63ce982299e04b79d227873d1) Point 3G: (42877656971275811310262564894490210024759287182177196162425349131675946712428, 61154801112014214504178281461992570017247172004704277041681093927569603776562) (3G) in hex: 0x5ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c, 0x8734640c4998ff7e374b06ce1a64a2ecd82ab036384fb83d9a79b127a27d5032) G+G: (56515219790691171413109057904011688695424810155802929973526481321309856242040, 3377031843712258259223711451491452598088675519751548567112458094635497583569) G+2G: (42877656971275811310262564894490210024759287182177196162425349131675946712428, 61154801112014214504178281461992570017247172004704277041681093927569603776562) Point 1G: (48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) (1G) in hex: 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5) Point 50353991974934769711415159834702018307502718206665713533826828512984171521836G: (97143571766921595575715747241807552434372960995867768174905147704287709168444, 56898412949395240106136520069476913303623747810921377418178881454792023331491) The test vectors take from here are: Curve: P256 ------------- k = 1 x = 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 y = 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 k = 2 x = 7CF27B188D034F7E8A52380304B51AC3C08969E277F21B35A60B48FC47669978 y = 07775510DB8ED040293D9AC69F7430DBBA7DADE63CE982299E04B79D227873D1 k = 3 x = 5ECBE4D1A6330A44C8F7EF951D4BF165E6C6B721EFADA985FB41661BC6E7FD6C y = 8734640C4998FF7E374B06CE1A64A2ECD82AB036384FB83D9A79B127A27D5032 |