Curve 25519Curve 25519 is one of the most widely used ECC methods. It uses a curve of \(y^2 = x^3 + 486662 x^2 + x\) [plot], and which is a Montgomery curve. The prime number used is \(2^{255}-19\). This page implements ECDH, and which is the method used in Tor to exchange the key. In this case we will use Python to implement X25519 (and which uses Curve 25519), but only uses the x-axis point for the sharing of values. The base point \(G\) on Curve 25519 is (9,1478161944 ... 7755586237401) [here]. Curve Points
Curve Adding/Multiplication
ECDH
|
Ed25519
Ed25518 provides a signature (EdDSA) using Curve 25519. This is a Montgomery Curve and has the generalized form of:
\(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
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
X25519
Curve 25519 is one of the most widely used ECC methods. It uses a curve of \(y^2 = x^3 + 486662 x^2 + x\) [plot], and which is a Montgomery curve. The prime number used is \(2^{255}-19\). This page implements ECDH, and which is the method used in Tor to exchange the key. In this case we will use Python to implement X25519 (and which uses Curve 25519), but only uses the x-axis point for the sharing of values. The base point \(G\) on Curve 25519 is (9,1478161944 ... 7755586237401)[here] and the paramaters based by on RFC 7748 [here].
Clamping
The order of Curve25519 has cofactor 8. This means that we can points with two independent values. One will have an order q, the second of order 8. If we multiply a point by a multiple of 8 results in the value of zero in the cofactor component (8k * n = 0 mod 8) and thus avoids leaking the value of the scalar modulo 8.
Presentations