NIST P521 is Weierstrass curve uses a form of \(y^2=x^3+ax+b\). The prime number used is \(2^{521}-1\) [secp256k1 barebones][P256 barebones][P521 barebones][Curve 25519 barebones]:
Barebones P521: Adding and Scalar Multiply on the curve (Python)TheoryThe NIST P521 curve uses a form of \(y^2=x^3+ax+b\) and specifically as: \(y^2 = x^3-3x+b=1093849...5984,\) and a finite field of: \(p =2^{521}-1 = 6864797....51\) 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. import random from p512 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 ("P512") 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-512 code: # Code from: https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdhe.py import collections p1 = 2**521-1 EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') curve = EllipticCurve( 'P521', # Field characteristic. p=p1, # Curve coefficients. a=-3, b=1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984, # Base point. g=(2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846, 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784), # Subgroup order. n=686479766013060971498190079908139321726943530014330540939446345918554318339765539424505774633321719753296399637136332111386476861244038034037280889270700, # 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\): P512 Point 1G: (2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846, 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784) (1G) in hex: 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66,0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650) Point 2G: (901472452850866198617673658578940391618730359691416279093035377195377079020397774511960179466499271590922803070095487687963115616363390991670183687363590205, 3281327921582527507824747162491172657218985358085640380741461489720525905953211486053138004786012424348623853685340634287932228687534583594738661002099038978) (2G) in hex: 0x433c219024277e7e682fcb288148c282747403279b1ccc06352c6e5505d769be97b3b204da6ef55507aa104a3a35c5af41cf2fa364d60fd967f43e3933ba6d783d,0xf4bb8cc7f86db26700a7f3eceeeed3f0b5c6b5107c4da97740ab21a29906c42dbbb3e377de9f251f6b93937fa99a3248f4eafcbe95edc0f4f71be356d661f41b02) Point 3G: (5674708455687314755177411224894914551247560982429925442328503936381769479291831722549724502783064471579811889182869230569934709210549404604394803481732951421, 4271801692429350493774172787940824381696861087943454989753620357811953134117882851809933515614164977926164094992857584446095333607804956469237639174332793061) (3G) in hex: 0x1a73d352443de29195dd91d6a64b5959479b52a6e5b123d9ab9e5ad7a112d7a8dd1ad3f164a3a4832051da6bd16b59fe21baeb490862c32ea05a5919d2ede37ad7d,0x13e9b03b97dfa62ddd9979f86c6cab814f2f1557fa82a9d0317d2f8ab1fa355ceec2e2dd4cf8dc575b02d5aced1dec3c70cf105c9bc93a590425f588ca1ee86c0e5) G+G: (901472452850866198617673658578940391618730359691416279093035377195377079020397774511960179466499271590922803070095487687963115616363390991670183687363590205, 3281327921582527507824747162491172657218985358085640380741461489720525905953211486053138004786012424348623853685340634287932228687534583594738661002099038978) G+2G: (5674708455687314755177411224894914551247560982429925442328503936381769479291831722549724502783064471579811889182869230569934709210549404604394803481732951421, 4271801692429350493774172787940824381696861087943454989753620357811953134117882851809933515614164977926164094992857584446095333607804956469237639174332793061) Point 3G: (5674708455687314755177411224894914551247560982429925442328503936381769479291831722549724502783064471579811889182869230569934709210549404604394803481732951421, 4271801692429350493774172787940824381696861087943454989753620357811953134117882851809933515614164977926164094992857584446095333607804956469237639174332793061) (3G) in hex: 0x1a73d352443de29195dd91d6a64b5959479b52a6e5b123d9ab9e5ad7a112d7a8dd1ad3f164a3a4832051da6bd16b59fe21baeb490862c32ea05a5919d2ede37ad7d,0x13e9b03b97dfa62ddd9979f86c6cab814f2f1557fa82a9d0317d2f8ab1fa355ceec2e2dd4cf8dc575b02d5aced1dec3c70cf105c9bc93a590425f588ca1ee86c0e5) Point 101147212755025026305441865793381894836128178629589349227793568094432526283275G: (499478880715637379058036933371498808348973887857608600601954147277754992537230687610994473408851474152737468457417779883347972888843487141305715904708718946, 3227896018011269917132975217363494742837199335862354432558570356598390177460736629464091631130095734002264433421883421607659971604141992557697330671303167581) The test vectors take from here are: Curve: P521 ------------- k = 1 x = 00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66 y = 011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650 k = 2 x = 00433C219024277E7E682FCB288148C282747403279B1CCC06352C6E5505D769BE97B3B204DA6EF55507AA104A3A35C5AF41CF2FA364D60FD967F43E3933BA6D783D y = 00F4BB8CC7F86DB26700A7F3ECEEEED3F0B5C6B5107C4DA97740AB21A29906C42DBBB3E377DE9F251F6B93937FA99A3248F4EAFCBE95EDC0F4F71BE356D661F41B02 k = 3 x = 01A73D352443DE29195DD91D6A64B5959479B52A6E5B123D9AB9E5AD7A112D7A8DD1AD3F164A3A4832051DA6BD16B59FE21BAEB490862C32EA05A5919D2EDE37AD7D y = 013E9B03B97DFA62DDD9979F86C6CAB814F2F1557FA82A9D0317D2F8AB1FA355CEEC2E2DD4CF8DC575B02D5ACED1DEC3C70CF105C9BC93A590425F588CA1EE86C0E5 |