Expand description
Internal curve representations which are not part of the public API.
§Curve representations
Internally, we use several different models for the curve. Here
is a sketch of the relationship between the models, following a
post
by Ben Smith on the moderncrypto mailing list. This is also briefly
discussed in section 2.5 of Montgomery curves and their
arithmetic by Costello and Smith.
Begin with the affine equation for the curve,
$$
-x^2 + y^2 = 1 + dx^2y^2.
$$
Next, pass to the projective closure \(\mathbb P^1 \times \mathbb
P^1 \) by setting \(x=X/Z\), \(y=Y/T.\) Clearing denominators
gives the model
$$
-X^2T^2 + Y^2Z^2 = Z^2T^2 + dX^2Y^2.
$$
In curve25519-dalek, this is represented as the CompletedPoint
struct.
To map from \(\mathbb P^1 \times \mathbb P^1 \), a product of
two lines, to \(\mathbb P^3\), we use the Segre
embedding
$$
\sigma : ((X:Z),(Y:T)) \mapsto (XY:XT:ZY:ZT).
$$
Using coordinates \( (W_0:W_1:W_2:W_3) \) for \(\mathbb P^3\),
the image \(\sigma (\mathbb P^1 \times \mathbb P^1) \) is the
surface defined by \( W_0 W_3 = W_1 W_2 \), and under \(
\sigma\), the equation above becomes
$$
-W_1^2 + W_2^2 = W_3^2 + dW_0^2,
$$
so that the curve is given by the pair of equations
$$
\begin{aligned}
-W_1^2 + W_2^2 &= W_3^2 + dW_0^2, \\ W_0 W_3 &= W_1 W_2.
\end{aligned}
$$
Up to variable naming, this is exactly the “extended” curve model
introduced in Twisted Edwards Curves
Revisited by Hisil, Wong, Carter,
and Dawson. In curve25519-dalek, it is represented as the
EdwardsPoint struct. We can map from \(\mathbb P^3 \) to
\(\mathbb P^2 \) by sending \( (W_0:W_1:W_2:W_3) \) to \(
(W_1:W_2:W_3) \). Notice that
$$
\frac {W_1} {W_3} = \frac {XT} {ZT} = \frac X Z = x,
$$
and
$$
\frac {W_2} {W_3} = \frac {YZ} {ZT} = \frac Y T = y,
$$
so this is the same as if we had started with the affine model
and passed to \( \mathbb P^2 \) by setting \( x = W_1 / W_3
\), \(y = W_2 / W_3 \).
Up to variable naming, this is the projective representation
introduced in in Twisted Edwards
Curves by Bernstein,
Birkner, Joye, Lange, and Peters. In curve25519-dalek, it is
represented by the ProjectivePoint struct.
§Passing between curve models
Although the \( \mathbb P^3 \) model provides faster addition formulas, the \( \mathbb P^2 \) model provides faster doubling formulas. Hisil, Wong, Carter, and Dawson therefore suggest mixing coordinate systems for scalar multiplication, attributing the idea to a 1998 paper of Cohen, Miyagi, and Ono.
Their suggestion is to vary the formulas used by context, using a \( \mathbb P^2 \rightarrow \mathbb P^2 \) doubling formula when a doubling is followed by another doubling, a \( \mathbb P^2 \rightarrow \mathbb P^3 \) doubling formula when a doubling is followed by an addition, and computing point additions using a \( \mathbb P^3 \times \mathbb P^3 \rightarrow \mathbb P^2 \) formula.
The ref10 reference implementation of Ed25519, by
Bernstein, Duif, Lange, Schwabe, and Yang, tweaks
this strategy, factoring the addition formulas through the
completion \( \mathbb P^1 \times \mathbb P^1 \), so that the
output of an addition or doubling always lies in \( \mathbb P^1 \times
\mathbb P^1\), and the choice of which formula to use is replaced
by a choice of whether to convert the result to \( \mathbb P^2 \)
or \(\mathbb P^3 \). However, this tweak is not described in
their paper, only in their software.
Our naming for the CompletedPoint (\(\mathbb P^1 \times \mathbb
P^1 \)), ProjectivePoint (\(\mathbb P^2 \)), and
EdwardsPoint (\(\mathbb P^3 \)) structs follows the naming in
Adam Langley’s Golang ed25519 implementation, which
curve25519-dalek was originally derived from.
Finally, to accelerate readditions, we use two cached point formats in “Niels coordinates”, named for Niels Duif, one for the affine model and one for the \( \mathbb P^3 \) model:
AffineNielsPoint: \( (y+x, y-x, 2dxy) \)ProjectiveNielsPoint: \( (Y+X, Y-X, Z, 2dXY) \)
Structs§
- A pre-computed point in the affine model for the curve, represented as \((y+x, y-x, 2dxy)\) in “Niels coordinates”.
- A
CompletedPointis a point \(((X:Z), (Y:T))\) on the \(\mathbb P^1 \times \mathbb P^1 \) model of the curve. A point (x,y) in the affine model corresponds to \( ((x:1),(y:1)) \). - A pre-computed point on the \( \mathbb P^3 \) model for the curve, represented as \((Y+X, Y-X, Z, 2dXY)\) in “Niels coordinates”.
- A
ProjectivePointis a point \((X:Y:Z)\) on the \(\mathbb P^2\) model of the curve. A point \((x,y)\) in the affine model corresponds to \((x:y:1)\).