Module curve25519_dalek::curve
[−]
[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 𝗣1 x 𝗣1 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 𝗣1 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 σ(𝗣1 x 𝗣1) 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 𝗣3 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 𝗣2 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 𝗣1 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 𝗣3 model:
- PreComputedPoint:
(y+x, y-x, 2dxy) - CachedPoint:
(Y+X, Y-X, Z, 2dXY)
Structs
| CachedPoint |
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. |
| 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)). |
| CompressedPoint |
An affine point |
| ExtendedPoint |
An |
| PreComputedPoint |
A pre-computed point in the affine model for the curve, represented as (y+x, y-x, 2dxy). These precomputations accelerate addition and subtraction. |
| ProjectivePoint |
A |
Traits
| CTAssignable |
Trait for items which can be conditionally assigned in constant time. |
| Identity |
Trait for curve point types that have an identity constructor. |
Functions
| double_scalar_mult_vartime |
Given a point |