NIST P224 curve in the form of a Weierstrass curve and uses a form of \(y^2=x^3+ax+b\) and specifically as \(y^2 = x^3-3x+18958286285566608000408668544493926415504680968679321075787234672564\) and a finite field of \(p = 2^{224} - 2^{96} + 1\). The base point (\(G\) is at and the base point is at (19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) [secp256k1 barebones][P256 barebones][P521 barebones][Curve 25519 barebones]:
Barebones P224: 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+18958286285566608000408668544493926415504680968679321075787234672564\) and a finite field of: \(p = 2^{224} - 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 P224, we the point on the curve is defined with a \((x,y)\) value [secp256k1 barebones][P256 barebones][P512 barebones]. import random from p224 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 ("P224") 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}") toHex(val,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**224 - 2**96 + 1 curve = EllipticCurve( 'P-224', # Field characteristic. p=p1, # Curve coefficients. a=-3, b=18958286285566608000408668544493926415504680968679321075787234672564, # Base point. g=(19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772), # Subgroup order. n=26959946667150639794667015087019625940457807714424391721682722368061, # 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]: P224 Point 1G: (19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) (1G) in hex: 0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21,0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34) Point 2G: (11838696407187388799350957250141035264678915751356546206913969278886, 2966624012289393637077209076615926844583158638456025172915528198331) (2G) in hex: 0x706a46dc76dcb76798e60e6d89474788d16dc18032d268fd1a704fa6,0x1c2b76a7bc25e7702a704fa986892849fca629487acf3709d2e4e8bb) Point 3G: (23495795443371455911734272815198443231796705177085412225858576936196, 17267899494408073472134592504239670969838724875111952463975956982053) (3G) in hex: 0xdf1b1d66a551d0d31eff822558b9d2cc75c2180279fe0d08fd896d04,0xa3f7f03cadd0be444c0aa56830130ddf77d317344e1af3591981a925) G+G: (11838696407187388799350957250141035264678915751356546206913969278886, 2966624012289393637077209076615926844583158638456025172915528198331) G+2G: (23495795443371455911734272815198443231796705177085412225858576936196, 17267899494408073472134592504239670969838724875111952463975956982053) Point 1G: (19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) (1G) in hex: 0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21,0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34) Point 300002184935129653211300932596162821843339027417908474523352664065G: (14793232189459690671009018614281658851434239787120013694337908677739, 16317786076124410796874980373272098403368637426257748835017313066070) The test vectors take from here are: Curve: P224 ------------- k = 1 x = B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21 y = BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34 k = 2 x = 706A46DC76DCB76798E60E6D89474788D16DC18032D268FD1A704FA6 y = 1C2B76A7BC25E7702A704FA986892849FCA629487ACF3709D2E4E8BB k = 3 x = DF1B1D66A551D0D31EFF822558B9D2CC75C2180279FE0D08FD896D04 y = A3F7F03CADD0BE444C0AA56830130DDF77D317344E1AF3591981A925 |