Module curve25519_dalek::edwards [−] [src]

Group operations for Curve25519, in the form of the twisted Edwards curve -x²+y²=1+dx²y² modulo p=2²⁵⁵-19 with parameter d=-121665/121666.

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.

Begin with the affine equation for the curve,

-x² + y² = 1 + dx²y². (1)

Next, pass to the projective closure 𝗣¹ x 𝗣¹ by setting x=X/Z, y=Y/T. Clearing denominators gives the model

-X²T² + Y²Z² = Z²T² + dX²Y². (2)

To map from 𝗣¹ x 𝗣^1, a product of two lines, to 𝗣^3, we use the Segre embedding,

σ : ((X:Z),(Y:T)) ↦ (XY:XT:ZY:ZT). (3)

Using coordinates (W₀:W₁:W₂:W₃) for 𝗣^3, the image of σ(𝗣¹ x 𝗣¹⁾ is the surface defined by W₀W₃=W₁W₂, and under σ, equation (2) becomes

-W₁² + W₂² = W₃² + dW₀². (4)

Up to variable naming, this is exactly the curve model introduced in "Twisted Edwards Curves Revisited" by Hisil, Wong, Carter, and Dawson. We can map from 𝗣³ to 𝗣² by sending (W₀:W₁:W₂:W₃) to (W₁:W₂:W₃). Notice that

W₁/W₃ = XT/ZT = X/Z = x (5)

W₂/W₃ = ZY/ZT = Y/T = y, (6)

so this is the same as if we had started with the affine model (1) and passed to 𝗣² by setting x = W₁/W₃, y = W₂/W₃. Up to variable naming, this is the projective representation introduced in "Twisted Edwards Curves".

Following the implementation strategy in the ref10 reference implementation for Ed25519, we use several different models for curve points:

CompletedPoint: points in 𝗣¹ x 𝗣^1;
ExtendedPoint: points in 𝗣^3;
ProjectivePoint: points in 𝗣^2.

Finally, to accelerate additions, we use two cached point formats, one for the affine model and one for the 𝗣³ model:

AffineNielsPoint: (y+x, y-x, 2dxy)
ProjectiveNielsPoint: (Y+X, Y-X, Z, 2dXY)

Modules

vartime

Variable-time operations on curve points, useful for non-secret data.

Structs

AffineNielsPoint	A pre-computed point in the affine model for the curve, represented as (y+x, y-x, 2dxy). These precomputations accelerate addition and subtraction, and were introduced by Niels Duif in the ed25519 paper "High-Speed High-Security Signatures".
CompletedPoint	A `CompletedPoint` is a point ((X:Z), (Y:T)) in 𝗣¹(𝔽ₚ)×𝗣¹(𝔽ₚ). A point (x,y) in the affine model corresponds to ((x:1),(y:1)).
CompressedEdwardsY	In "Edwards y" format, the point `(x,y)` on the curve is determined by the `y`-coordinate and the sign of `x`, marshalled into a 32-byte array.
EdwardsBasepointTable	Precomputation
ExtendedPoint	An `ExtendedPoint` is a point on the curve in 𝗣³(𝔽ₚ). A point (x,y) in the affine model corresponds to (x:y:1:xy).
ProjectiveNielsPoint	A pre-computed point in the P³(𝔽ₚ) model for the curve, represented as (Y+X, Y-X, Z, 2dXY). These precomputations accelerate addition and subtraction, and were introduced by Niels Duif in the ed25519 paper "High-Speed High-Security Signatures".
ProjectivePoint	A `ProjectivePoint` is a point on the curve in 𝗣²(𝔽ₚ). A point (x,y) in the affine model corresponds to (x:y:1).

Traits

Identity	Trait for curve point types which have an identity constructor.
IsIdentity	Trait for testing if a curve point is equivalent to the identity point.
ValidityCheck	Trait for checking whether a point is on the curve

Functions

multiscalar_mult

Given a vector of (possibly secret) scalars and a vector of (possibly secret) points, compute c_1 P_1 + ... + c_n P_n.