Eccfrog512ck2: An Enhanced 512-bit Weierstrass Elliptic Curve
This article outlines the research work that Víctor Duarte Melo and I have recently been doing.
Introduction
My route into cryptography … I first fell for the power of the Diffie-Hellman method and then was amazed by the simplicity and power of the RSA method. But it was with Elliptic Curve Cryptography that I discovered the sheer beauty of cryptography. For me, how could such a simple and elegant lead to such power?
While our first steps into the world of the Diffie-Hellman method were with discrete logarithms (g^x mod p), it was the power of elliptic curves which made it so much more simple, and where now virtually all of our connections to the Internet are secured by ECDH (Elliptic Curve Diffie Hellman). For digital signatures, elliptic curves have also significantly reduced the processing requirements, and where we now often use ECDSA and EdDSA over RSA.
Bitcoin and Ethereum
The rapid rise of elliptic curves perhaps happened when Satoshi Nakamoto selected the secp256k1 curve for Bitcoin. This uses the equation of:
y² = x³ + 7 (mod p)
and where p=2²⁵⁶-2³²-977, and is defined as a Weierstrass curve. Overall, we end up with a number of integer points (x,y) for which the first 20 points for secp256k1 are [here]:
Elliptic curve is: secp256k1
Finding elliptic point closest to: 1
Prime number: 115792089237316195423570985008687907853269984665640564039457584007908834671663
a,b 0 7
(1, 29896722852569046015560700294576055776214335159245303116488692907525646231534L)
(2, 69211104694897500952317515077652022726490027694212560352756646854116994689233L)
(3, 94471189679404635060807731153122836805497974241028285133722790318709222555876L)
(4, 40508090799132825824753983223610497876805216745196355809233758402754120847507L)
(6, 19112057249303445409876026535760519114630369653212530612662492210011362204224L)
(8, 91736135629086734185706894124002126994554994840140056297753929940646699135966L)
(12, 84723224514829953401809146057688111907524826729556536824205543511930558249867L)
(13, 20267456347483554069520440766283645831919514026818877192810320909941447705364L)
(14, 44647516152956573151520437476900496747965187933683819148138195218441524686495L)
(16, 6086653149631013477190265492692874244435390487330439650246572165529255539543L)
(20, 95115947350322555212584100192293494006877237570979160767752142956238074546829L)While secp256k1 is used in many blockchain systems, we often use secp256r1 (NIST P256) for TLS communications.
With secp256k1, we have 128-bit security, and which gives us a good margin over the currently recommended 112-bit security level. But, in some applications, we need a better security level and have to use larger prime numbers for the elliptic curve. For NIST, the most secure curve is NIST P521, and which uses a prime number of 2⁵²¹−1. It takes the form of [here]:
y²=x³−3x+b=1093849…5984,
and a finite field of:
p=2⁵²¹−1=6864797….51
Overall, we have a base point on the curve (G), and then can compute 2G (G+G) and 3G (G+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)Eccfrog512ck2: An Enhanced 512-bit Weierstrass Elliptic Curve
With Víctor Duarte Melo, we have developed an enhanced elliptic curve which improves performance over P521 and is named eccfrog512ck2. It has been published in the IACR [here]:
The basic specifications for the curve are:
We can see it is resistant to the twist and MOV attacks. The parameters selected are:
and where n is the order of the curve — and which defines the number of possible (x,y) points. When it comes to performance, in our evaluation, we achieved significant improvements of the basic elliptic curve operations, such as for point generation, scalar multiplication (k.G), point validation (whether a point is on the curve) and ECDH key exchange time:
Conclusions
Here is the paper:
