One recent cipher option in openSSH is ed25519. This is an Elliptic curve
and is used in many public key cryptographic schemes. These curves are
polynomials in two variables — (x,y), and of the second degree in y,
and of the third degree in x.
One can consider the curve 25519 over a finite field F of 2^255-19.
One can see that this is a field because this is prime.
(%i1) factor(2^255-19);
(%o1)
57896044618658097711785492504343953926634992332820282019728792003956564819949
The points (x,y) of the elliptic curve form a group and so
one can use them as public keys.
(%i9) montgomery_curve(x,y,A,B):=B*y^2 = x+A*x^2+x^3
(%i10) curve25519(X):=polymod(montgomery_curve(X[1],X[2],486662,1),2^255-19)
For the value x = 9,
one can consider this curve as a quadratic in y, and solve for it.
(%i4) montgomery_curve(9,y,486662,1);
2
(%o4) y = 39420360
(%i11) solve(montgomery_curve(9,y,486662,1),y)
(%o11) [y = – 6 sqrt(1095010), y = 6 sqrt(1095010)]
These are solutions over the reals.
(%i12) factor(39420360)
3 2
(%o12) 2 3 5 7 15643
(%i13) zn_nth_root(39420360,2,2^255-19)
(%o13) [1478161944758954479102059356840998688726460613461647528896488183775558\
6237401,
43114425171068552920764898935933967039370386198203806730763910166200978582548]
These are the solutions for y over the finite field.
(%i14) curve25519([9,
14781619447589544791020593568409986887264606134616475288964881837755586237401])
(%o14) 39420360 = 39420360
(%i15) rhs(%)-lhs(%)
(%o15) 0
So we have shown that the point x = 9, y = 14781619447589544791020593568409986887264606134616475288964881837755586237401
is a point on curve 25519. And thus is a member of the elliptic curve group.
Maxima has an elliptic curve package that one can load with
(%i11) batch(“elliptic_curves”);
(%i16) secp112r2;
(%o16) [[4451685225093714772084598273548427,
1970543761890640310119143205433388, 1660538572255285715897238774208265],
[1534098225527667214992304222930499, 3525120595527770847583704454622871],
1112921306273428674967732714786891]
Elliptic curve cryptography is supported in openSSH and openSSL and DKIM. When I first wrote this post in 2018, support was incomplete, but now in 2021, it looks fairly good. The basic claim is that elliptic curves are more efficient, key length, and use are perhaps faster for the same level of security.
plot2d (y^2 = x+486662*x^2+x^3,[x,-1e4,1e4],[y,-2e6,2e6])$
