For a finite field elliptic curve we have for a curve of \(y^2 = x^3 + ax +b\) and for a defined prime number (\(p\)). This is defined as a Weierstrass curve. For Curve 25519 the form is \(y^2 = x^3+a x^2+x \pmod p\), and is known as the Montgomery form. If we have a point \(P\), we can then calculate \(2P\) (and use this to find \(nP\) - where \(n\) is the number of times we add \(P\)). In this case we will calculate 1G, 2G and nG on popular curves:
Real ECC curves for (1G, 2G and nG) |
secp256k1:
\(y^2 = x^3+0x+7 \pmod p\)
\(p = 2^{256} - 2^{32} - 977\). This is represented as \(\mathbb{F}_{2^{256}-2^{32}-997}\).
Curve 25519:
\(y^2 = x^3+486662 x^2+x \pmod p\)
\(p = 2^{255} - 19\). This is represented as \(\mathbb{F}_{2^{255}-1}\).
NIST P256:
\(y^2 = x^3-3x+41058363725152142129326129780047268409114441015993725554835256314039467401291 \pmod p\)
\(p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\). This is represented as \(\mathbb{F}_{2^{256} - 2^{224} + 2^{192} + 2^{96} - 1}\).
Coding
In this case we calculate \(x^3+ax+b \pmod p\). For point addition of \(P\) (\(x,y\)) we calculate the point addition for a given point (\(P+P\)) and represent it by (\(2P\)). For this we have:
\(2P = (x_2, y_2)\)
Let \(s = (3x^2 + a)/(2y)\)
Then:
\(x_2 = s^2 - 2x\)
\(y_2 = s(x - x_2) - y\)
For Curve 25519, for point addition, we use the method defined in RFC 7748 [here].
Coding
from libnum import ecc import sys def printPoints(name,a,b,p,G,scale): print (name) c = ecc.Curve(a,b,p,G) for n in range(1,3): res = c.power(G,n) print (n,"G=",res) x,y = res print (hex(x),hex(y)) res = c.power(G,scale) print (scale,"G=",res) x,y = res print (hex(x),hex(y)) scale=3 if (len(sys.argv)>1): scale=int(sys.argv[1]) a=0 b=7 G=(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) p=115792089237316195423570985008687907853269984665640564039457584007908834671663 printPoints("\nsecp256k1",a,b,p,G,scale) a=19298681539552699237261830834781317975544997444273427339909597334573241639236 b=55751746669818908907645289078257140818241103727901012315294400837956729358436 G=(19298681539552699237261830834781317975544997444273427339909597334652188435546, 14781619447589544791020593568409986887264606134616475288964881837755586237401) p=57896044618658097711785492504343953926634992332820282019728792003956564819949 printPoints("\nCurve 25519 - Weierstrass",a,b,p,G,scale) a=-3 b= 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984 G= (2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846, 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784) p= 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 printPoints("\np512",a,b,p,G,scale) a=-3 b=2455155546008943817740293915197451784769108058161191238065 G=(602046282375688656758213480587526111916698976636884684818, 174050332293622031404857552280219410364023488927386650641) p=6277101735386680763835789423207666416083908700390324961279 sys.exit() printPoints("\nP192",a,b,p,G,scale) a=-3 b=18958286285566608000408668544493926415504680968679321075787234672564 G=(19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) p= 26959946667150639794667015087019630673557916260026308143510066298881 printPoints("\nP224",a,b,p,G,scale) a=-3 b= 41058363725152142129326129780047268409114441015993725554835256314039467401291 G= (48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) p= 115792089210356248762697446949407573530086143415290314195533631308867097853951 printPoints("\nP256",a,b,p,G,scale) a=-3 b= 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575 G= (26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087, 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871) p= 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319 printPoints("\np384",a,b,p,G,scale) a=4451685225093714772084598273548424 b=2061118396808653202902996166388514 G=(188281465057972534892223778713752, 3419875491033170827167861896082688) p=4451685225093714772084598273548427 printPoints("\nSECP112r1",a,b,p,G,scale) a=340282366762482138434845932244680310780 b=308990863222245658030922601041482374867 G=(29408993404948928992877151431649155974, 275621562871047521857442314737465260675) p=340282366762482138434845932244680310783 printPoints("\nSECP128r1",a,b,p,G,scale) a=0 b=7 G=(338530205676502674729549372677647997389429898939, 842365456698940303598009444920994870805149798382) p=1461501637330902918203684832716283019651637554291 printPoints("\nSECP160r1",a,b,p,G,scale) a=0 b=3 G=(5377521262291226325198505011805525673063229037935769709693, 3805108391982600717572440947423858335415441070543209377693) p=6277101735386680763835789423207666416102355444459739541047 printPoints("\nSECP192r1",a,b,p,G,scale)
And a sample run:
secp256k11 G= (55066263022277343669578718895168534326250603453777594175500187360389 116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 0x483ad a7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b82 G= (89565891926547004231252920425935692360644145829622209833684329913297 188986597, 121583992996938303229678086127133986361553678870416281767988719 54788371653930) 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a 3 G= (11271166043971060605674865917392967310211497734153940854463061355520 9775888121, 25583027980570883691656905877401976406448868254816295069919888 960541586679410) 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 0x388f7 b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672 Curve 25519 - Weierstrass 1 G= (19298681539552699237261830834781317975544997444273427339909597334652 188435546, 147816194475895447910205935684099868872646061346164752889648818 37755586237401) 0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad245a 0x20ae1 9a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9 2 G= (34145958685188182721225203372338409610255982577099208428796738225249 784787788, 891461309122914783127793547204864306688006789925184041885518179 3938505594211) 0x4b7ded7fc31e9c62841fb71327c01bbf39ea0797c8dfb6070758f1478815734c 0x13b57 e011700e8ae050a00945d2ba2f377659eb28d8d391ebcd70465c72df563 3 G= (31996542787837084749389369998208417873290338362623257813787100531446 184304739, 187825047312060179977909683741420552025472142385796648776196444 64800823583275) 0x46bd66c518025690effdf83c6cc6650fa32cf9120cc6b3046ab4ae5aa61e6063 0x29868 55cbe387eaeaceea446532c338c536af570f71ef7cf75c665019c41222b p512 1 G= (26617408020502170632287687167233609607298591687569731477066713684188 02944996427808491545080627771902352094241225065558662157113545570916814161637315895999846, 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784) 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650 2 G= (901472452850866198617673658578940391618730359691416279093035377195377079020397774511960179466499271590922803070095487687963115616363390991670183687363590205, 3281327921582527507824747162491172657218985358085640380741461489720525905953211486053138004786012424348623853685340634287932228687534583594738661002099038978) 0x433c219024277e7e682fcb288148c282747403279b1ccc06352c6e5505d769be97b3b204da6ef55507aa104a3a35c5af41cf2fa364d60fd967f43e3933ba6d783d 0xf4bb8cc7f86db26700a7f3eceeeed3f0b5c6b5107c4da97740ab21a29906c42dbbb3e377de9f251f6b93937fa99a3248f4eafcbe95edc0f4f71be356d661f41b02 3 G= (5674708455687314755177411224894914551247560982429925442328503936381769479291831722549724502783064471579811889182869230569934709210549404604394803481732951421, 4271801692429350493774172787940824381696861087943454989753620357811953134117882851809933515614164977926164094992857584446095333607804956469237639174332793061) 0x1a73d352443de29195dd91d6a64b5959479b52a6e5b123d9ab9e5ad7a112d7a8dd1ad3f164a3a4832051da6bd16b59fe21baeb490862c32ea05a5919d2ede37ad7d 0x13e9b03b97dfa62ddd9979f86c6cab814f2f1557fa82a9d0317d2f8ab1fa355ceec2e2dd4cf8dc575b02d5aced1dec3c70cf105c9bc93a590425f588ca1ee86c0e5 P192 1 G= (602046282375688656758213480587526111916698976636884684818, 174050332293622031404857552280219410364023488927386650641) 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012 0x7192b95ffc8da78631011ed6b24cdd573f977a11e794811 2 G= (5369744403678710563432458361254544170966096384586764429448, 5429234379789071039750654906915254128254326554272718558123) 0xdafebf5828783f2ad35534631588a3f629a70fb16982a888 0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab 3 G= (2915109630280678890720206779706963455590627465886103135194, 2946626711558792003980654088990112021985937607003425539581) 0x76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da 0x782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd P224 1 G= (19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) 0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21 0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34 2 G= (11838696407187388799350957250141035264678915751356546206913969278886, 2966624012289393637077209076615926844583158638456025172915528198331) 0x706a46dc76dcb76798e60e6d89474788d16dc18032d268fd1a704fa6 0x1c2b76a7bc25e7702a704fa986892849fca629487acf3709d2e4e8bb 3 G= (23495795443371455911734272815198443231796705177085412225858576936196, 17267899494408073472134592504239670969838724875111952463975956982053) 0xdf1b1d66a551d0d31eff822558b9d2cc75c2180279fe0d08fd896d04 0xa3f7f03cadd0be444c0aa56830130ddf77d317344e1af3591981a925 P256 1 G= (48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5 2 G= (56515219790691171413109057904011688695424810155802929973526481321309856242040, 3377031843712258259223711451491452598088675519751548567112458094635497583569) 0x7cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978 0x7775510db8ed040293d9ac69f7430dbba7dade63ce982299e04b79d227873d1 3 G= (42877656971275811310262564894490210024759287182177196162425349131675946712428, 61154801112014214504178281461992570017247172004704277041681093927569603776562) 0x5ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c 0x8734640c4998ff7e374b06ce1a64a2ecd82ab036384fb83d9a79b127a27d5032 p384 1 G= (26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087, 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871) 0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f 2 G= (1362138308511466522361153706999924933599454966107597910086607881313301390679204654798639248640660900363360053616481, 21933325650940841369538204578070064804451893403314136885642470114978241170633179043576249504748352841115137159204480) 0x8d999057ba3d2d969260045c55b97f089025959a6f434d651d207d19fb96e9e4fe0e86ebe0e64f85b96a9c75295df61 0x8e80f1fa5b1b3cedb7bfe8dffd6dba74b275d875bc6cc43e904e505f256ab4255ffd43e94d39e22d61501e700a940e80 3 G= (1150902892488483458936980703033240421996917307006362560128741616924334451190275252566486993672663650518120360101937, 31026896179475916024120184231935979451435829475766013456640577102369059008378103381483562093497986423351518602141169) 0x77a41d4606ffa1464793c7e5fdc7d98cb9d3910202dcd06bea4f240d3566da6b408bbae5026580d02d7e5c70500c831 0xc995f7ca0b0c42837d0bbe9602a9fc998520b41c85115aa5f7684c0edc111eacc24abd6be4b5d298b65f28600a2f1df1 SECP112r1 1 G= (188281465057972534892223778713752, 3419875491033170827167861896082688) 0x9487239995a5ee76b55f9c2f098 0xa89ce5af8724c0a23e0e0ff77500 2 G= (1780995437533866901729502362261334, 1960966419089380527792400971530348) 0x57cf52a0f9318000ee0bc032d756 0x60aee03bbcff537a8d17401f006c 3 G= (4213820159228676125970083014447768, 1862707393714836977900502888758455) 0xcfc1e3447fc33e5c2a7d2bf71298 0x5bd6ac32f0a9e7aab6af722c3cb7 SECP128r1 1 G= (29408993404948928992877151431649155974, 275621562871047521857442314737465260675) 0x161ff7528b899b2d0c28607ca52c5b86 0xcf5ac8395bafeb13c02da292dded7a83 2 G= (171894248431803389772200227008324807038, 5110910329096684473053796200617836181) 0x8151a0c6b92171db199db84be753a97e 0x3d853559455caae838395a9275b7e95 3 G= (14404465037560764698468415334262000443, 163030310422358679409407543694089634847) 0xad632f542942f23aa423b628a304b3b 0x7aa67ee421c4e78851e4b4679bcdc41f SECP160r1 1 G= (338530205676502674729549372677647997389429898939, 842365456698940303598009444920994870805149798382) 0x3b4c382ce37aa192a4019e763036f4f5dd4d7ebb 0x938cf935318fdced6bc28286531733c3f03c4fee 2 G= (667872630170492720756233761457243746176356032739, 1180447395911666948299218979855295458288374173177) 0x74fc71cb95e965fc54ee5fa0227aff946533a0e3 0xcec5178957b56930ed3eb7d49f0db1dcf358cdf9 3 G= (677935970358862357903697512524689170492782677341, 1377726138650483620870431426160482164455605257519) 0x76bfb34670af0e3305c57012e49d9aea3dae0d5d 0xf153607068dcb611d14c6d9a1849db711f6bc52f SECP192r1 1 G= (5377521262291226325198505011805525673063229037935769709693, 3805108391982600717572440947423858335415441070543209377693) 0xdb4ff10ec057e9ae26b07d0280b7f4341da5d1b1eae06c7d 0x9b2f2f6d9c5628a7844163d015be86344082aa88d95e2f9d 2 G= (5898748710631235793867485368048681928976741514058866965686, 6215318586565457819081644608453878670902049430638930374357) 0xf091cf6331b1747684f5d2549cd1d4b3a8bed93b94f93cb6 0xfd7af42e1e7565a02e6268661c5e42e603da2d98a18f2ed5 3 G= (2703678267954837351785554213274685006315909454394736461187, 4819488447247427566251735083777178500867610886057901058648) 0x6e43b7dcae2fd5e0bf2a1ba7615ca3b9065487c9a67b4583 0xc48dcea47ae08e84d5fedc3d09e4c19606a290f7a19a6a58