In elliptic curve we have a base point (\(G\)), and then take a scalar value of \(n\) to produce \(n.G\). Normally \(n\) is the private key value, and \(n.G\) is the public key point. In Ed25519 we only need one of the co-ordinate point values. In this case we will determine the y-axis point for the Ed25519 curve, and then compute the x-axis point. The generalised form of a twisted Edwards curve is \(x^2 = (y^2 - 1) / (d y^2 + 1) \pmod p \) and where \(p=2^{255}-19\).
Sodium: NaCl - Finding Points on Ed25519 |
Theory
The generalize form of the curve is:
\(x^2 = (y^2 - 1) / (d y^2 + 1) \pmod p \)
and is specificially defined as:
\(−x^2+y^2=1−(121665/121666)x^2y^2 \pmod p\)
with a prime number (\(p\)) of \(2^{255}-19\) and the order (\(L\)) of \(2^{252}+27742317777372353535851937790883648493\). The base point is \(y=4/5\), and which is:
>>> p=2**255-19 >>> y=4*pow(5,-1,p) >>> print (y) 46316835694926478169428394003475163141307993866256225615783033603165251855960
When we convert this to hex we get:
>>> hex(46316835694926478169428394003475163141307993866256225615783033603165251855960) '0x6666666666666666666666666666666666666666666666666666666666666658'
And we can then work out the x co-ordinate with:
\(x=(u/v)^{(p+3)/8}\)
and where \(u = y^2 - 1\) and \(v = d y^2 + 1\). A Python program to recover the base point is:
p = 2**255 - 19 def inv(x): return pow(x, p-2, p) d = -121665 * inv(121666) I = pow(2,(p-1)//4,p) def findx(y): xx = (y*y-1) * inv(d*y*y+1) x = pow(xx,(p+3)//8,p) if (x*x - xx) % p != 0: x = (x*I) % p if x % 2 != 0: x = p-x return x y = 4 * inv(5) x = findx(y) print (x,y)
and which gives:
15112221349535400772501151409588531511454012693041857206046113283949847762202 46316835694926478169428394003475163141307993866256225615783033603165251855960
Coding
The code is:
import nacl.bindings as b import binascii import sys p = 2**255 - 19 def inv(x): return pow(x, p-2, p) d = -121665 * inv(121666) I = pow(2,(p-1)//4,p) def findx(y): xx = (y*y-1) * inv(d*y*y+1) x = pow(xx,(p+3)//8,p) if (x*x - xx) % p != 0: x = (x*I) % p if x % 2 != 0: x = p-x return x def convert_to_little_int(val): little_hex = bytearray.fromhex(val) little_hex.reverse() little = ''.join(format(x, '02x') for x in little_hex) return little i=1 n = binascii.a2b_hex("0100000000000000000000000000000000000000000000000000000000000000") if (len(sys.argv)>1): i=int(sys.argv[1]) n= i.to_bytes(32, 'little') x= b.crypto_scalarmult_ed25519_base_noclamp(n) print ("Base point, X value: ",binascii.b2a_hex(x)) print (f"\nn={i} [{binascii.b2a_hex(n).decode()}]") point= b.crypto_scalarmult_ed25519_base_noclamp(n) point_hex= binascii.b2a_hex(x).decode() point_int = int(convert_to_little_int(point_hex),16) print (f"{i}G, Point (y): {point_hex} ({point_int})") print () print (f"x point: {findx(point_int)}") print (f"y point: {point_int}")
With this we compute just the y-axis point (as we can then compute the x-axis point, if required). A sample run is:
y co-ordinate value: b'5866666666666666666666666666666666666666666666666666666666666666' n=1 [0100000000000000000000000000000000000000000000000000000000000000] 1G -> Point (y): 5866666666666666666666666666666666666666666666666666666666666666 (46316835694926478169428394003475163141307993866256225615783033603165251855960) x point: 15112221349535400772501151409588531511454012693041857206046113283949847762202 y point: 46316835694926478169428394003475163141307993866256225615783033603165251855960
and for \(2.G\):
y co-ordinate value: b'c9a3f86aae465f0e56513864510f3997561fa2c9e85ea21dc2292309f3cd6022' n=2 [0200000000000000000000000000000000000000000000000000000000000000] 2G -> Point (y): c9a3f86aae465f0e56513864510f3997561fa2c9e85ea21dc2292309f3cd6022 (15549675580280190176352668710449542251549572066445060580507079593062643049417) x point: 24727413235106541002554574571675588834622768167397638456726423682521233608206 y point: 15549675580280190176352668710449542251549572066445060580507079593062643049417