Some advanced cryptographic protocols require a "curve cycle", which is a pair of elliptic curves Ep
and Eq
over prime fields GF(p)
and GF(q)
such that #Ep = q
and #Eq = p
, i.e. the scalar field of each curve exactly equals to the base field of the other curve.
Unfortunately, Curve25519 has a composite order (divisible by 8), so it cannot be part of a curve cycle (both p
and q
need to be primes).
However, if we could find a curve cycle with p = 2^255 - 19
, points on Curve25519 could enter the cycle via curve Eq
, which has an order of p
. We call this arrangement a "tower-cycle":
-- Ep --
/ \
| ^
v |
\ /
-- Eq --
^
|
Curve25519
To find a curve of exact order p = 2^255 - 19
, we will use an algorithm described in the 2007 paper "Constructing elliptic curves of prime order" [1].
The algorithm roughly consists of the following steps:
- Searching for CM field discriminant
D
values that produce a tracet
such thatq = p + 1 ± t
is a prime number. - Finding a root
j0
of the Hilbert class polynomial overGF(q)
. - Calculating
a = 27*j0/(4*(1728 - j0))
- Finally, we have
Eq: y^2 = x^3 + a*x - a
or its quadratic twist (one of them will have orderp
).
The Hilbert class polynomial has more than one root, so there will be multiple curves for each prime.
Due to the symmetry of the algorithm between p
and q
, we can use the same process to find Ep
(except we can skip the first step because we already know the value of p
).
For performance and security reasons, we place additional conditions on q
, Eq
and Ep
:
- We want
q < 2^255
so we can encode compressed points ofEq
in 256 bits. This means we will only useq = p + 1 - t
in step 1 above. - We want
q = 3 mod 4
for efficient square root calculation modq
[2]. - Let
c = 2^256 - 2*q
. Crandall's modular reduction algorithm [3] requires multiplications byc
. We wantc < 2^128
, soc
can fit into two machine words on 64-bit CPUs, making modular reductions faster. - We want both
Ep
andEq
to have the form ofy^2 = x^3 - 3*x + b
for some constantb
, which allows for more efficient group law formulae [4]. - We want the curve constant
b
to be a non-square number. This prevents the pointx = 0
from being on the curve, which protects from some power analysis attacks [5].
The attached script tower_cycle_25519.sage
implements the search. The first discriminant value that produces a prime q
that matches our conditions (1), (2) and (3) is D = -7857907
and the prime is:
q = 0x7fffffffffffffffffffffffffffffffbf7f782cb7656b586eb6d2727927c79f
The resulting curve cycle consists of two curves Ep
and Eq
, which we will call "Helios" and "Selene". They are the first curves that match our conditions (4) and (5).
Helios: y^2 = x^3 - 3*x + 15789920373731020205926570676277057129217619222203920395806844808978996083412 over GF(p)
Selene: y^2 = x^3 - 3*x + 50691664119640283727448954162351551669994268339720539671652090628799494505816 over GF(q)
Helios corresponds to the 11th root of the Hilbert class polynomial over GF(p)
and Selene corresponds to the 5th root of the Hilbert class polynomial over GF(q)
.
We define the base point of each curve as the point with the smallest x-coordinate:
Helios: G = [3, 37760095087190773158272406437720879471285821656958791565335581949097084993268]
Selene: G = [1, 55227837453588766352929163364143300868577356225733378474337919561890377498066]
Both Helios and Selene meet some of the SafeCurves criteria [6].
Both p
and q
are primes.
For both Helios and Selene, b != ±2
, so the curves are not singular.
For both curves, the base point G
lies on the curve. For Helios, q*G == O
and for Selene, p*G == O
.
Both curves provide 127.3 bits of ECDLP security, which is more than Curve25519.
Since p != q
, both curves are safe from additive transfers. The embedding degree of Helios is (q-1)/2
and the embedding degree of Selene is (p-1)/2
, so both are also safe from multiplicative transfers.
Due to the way they were constructed, both curves have a CM field discriminant value of -7857907
.
The curve generation process is completely explained.
Both curves have a cofactor of 1, so they don't support the Montgomery ladder.
Both Helios and Selene lack twist security, so they should not be used in single-coordinate ladders.
The curves don't support complete formulas that meet the SafeCurves requirements.
Both curves support indistinguishability using Elligator Squared [7].
[1] Constructing elliptic curves of prime order: https://arxiv.org/abs/0712.2022
[2] A simple algorithm for finding square root modulo p: https://arxiv.org/pdf/2008.11814.pdf
[3] Crandall's modular reduction: https://patents.google.com/patent/US5159632A/en
[4] Jacobian coordinates with a=-3 for short Weierstrass curves: https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html
[5] A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems https://www.iacr.org/archive/pkc2003/25670199/25670199.pdf
[6] SafeCurves: choosing safe curves for elliptic-curve cryptography https://safecurves.cr.yp.to/index.html
[7] Elligator Squared: Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings https://eprint.iacr.org/2014/043.pdf
https://github.com/kayabaNerve/fcmp-plus-plus/tree/develop/crypto/helioselene is a Rust implementation of these two curves using constant time, yet generic, arithmetic. It uses the complete Weierstrass addition formulas (and I have yet to implement dedicated doubling). It's presumed not performant enough for production before tailored arithmetic is implemented.