Module curve25519_dalek::backend::serial::curve_models

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

• AffineNielsPoint
  A pre-computed point in the affine model for the curve, represented as \((y+x, y-x, 2dxy)\) in “Niels coordinates”.
• CompletedPoint
  A CompletedPoint is 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)) \).
• ProjectiveNielsPoint
  A pre-computed point on the \( \mathbb P^3 \) model for the curve, represented as \((Y+X, Y-X, Z, 2dXY)\) in “Niels coordinates”.
• ProjectivePoint
  A ProjectivePoint is 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)\).