edwards25519 curve表示为：
− x 2 + y 2 = 1 + d x 2 y 2 , d = − ( 121665 / 121666 ) , q = 2 255 − 19 -x^2+y^2=1+dx^2y^2,d=-(121665/121666),q=2^{255}-19 −x2+y2=1+dx2y2,d=−(121665/121666),q=2255−19
1. edwards25519 add算法根据博客Extended twisted Edwards curve坐标系中提及：
注意，在Extended坐标系下，可提供更快的加法运算，在Projective坐标系下，可提供更快的double运算！！！实际使用时，可根据不同的计算选择不同的坐标系。
所以，add加法运算使用Extended坐标系，采用论文《Twisted Edwards Curves Revisited》中的Dedicated Addition in
ε
e
\varepsilon ^e
εe算法： 
对于edwards25519 curve，
a
=
−
1
a=-1
a=−1。 根据 https://doc-internal.dalek.rs/curve25519_dalek/backend/serial/curve_models/index.html 中定义，计算所得的
(
X
3
:
Y
3
:
T
3
:
Z
3
)
(X_3:Y_3:T_3:Z_3)
(X3:Y3:T3:Z3)为extended坐标，对应的为
(
W
1
:
W
2
:
W
0
:
W
3
)
(W_1:W_2:W_0:W_3)
(W1:W2:W0:W3)，详细的计算过程为：
A
=
(
Y
1
−
X
1
)
∗
(
Y
2
−
X
2
)
;
B
=
(
Y
1
+
X
1
)
∗
(
Y
2
+
X
2
)
;
C
=
2
d
T
1
∗
T
2
=
T
1
∗
(
2
d
T
2
)
;
D
=
2
Z
1
∗
Z
2
;
E
=
B
−
A
;
F
=
D
−
C
;
G
=
D
+
C
;
H
=
B
+
A
A=(Y_1-X_1)*(Y_2-X_2); B=(Y_1+X_1)*(Y_2+X_2); C=2dT_1*T_2=T_1*(2dT_2); D=2Z_1*Z_2; E=B-A;F=D-C;G=D+C;H=B+A
A=(Y1−X1)∗(Y2−X2);B=(Y1+X1)∗(Y2+X2);C=2dT1∗T2=T1∗(2dT2);D=2Z1∗Z2;E=B−A;F=D−C;G=D+C;H=B+A
W 1 = X 3 = E ∗ F ; W 2 = Y 3 = G ∗ H ; W 0 = T 3 = E ∗ H ; W 3 = Z 3 = F ∗ G W_1=X_3=E*F;W_2=Y_3=G*H;W_0=T_3=E*H;W_3=Z_3=F*G W1=X3=E∗F;W2=Y3=G∗H;W0=T3=E∗H;W3=Z3=F∗G
∵ W 1 W 3 = X T Z T = X Z = x = E ∗ F F ∗ G = E G \because \frac{W_1}{W_3}=\frac{XT}{ZT}=\frac{X}{Z}=x=\frac{E*F}{F*G}=\frac{E}{G} ∵W3W1=ZTXT=ZX=x=F∗GE∗F=GE ∵ W 2 W 3 = Y Z Z T = Y T = y = G ∗ H F ∗ G = H F \because \frac{W_2}{W_3}=\frac{YZ}{ZT}=\frac{Y}{T}=y=\frac{G*H}{F*G}=\frac{H}{F} ∵W3W2=ZTYZ=TY=y=F∗GG∗H=FH ∴ X = E ; Y = H ; Z = G ; T = F \therefore X=E; Y=H; Z=G; T=F ∴X=E;Y=H;Z=G;T=F
以上得到的即为 σ : ( ( X : Z ) , ( Y : T ) ) \sigma :((X:Z),(Y:T)) σ:((X:Z),(Y:T))。 相应的代码实现为：
impl Add for &'a EdwardsPoint {
type Output = EdwardsPoint;
fn add(self, other: &'b EdwardsPoint) -> EdwardsPoint {
(self + &other.to_projective_niels()).to_extended()
}
}
/// Convert to a ProjectiveNielsPoint
pub(crate) fn to_projective_niels(&self) -> ProjectiveNielsPoint {
ProjectiveNielsPoint{
Y_plus_X: &self.Y + &self.X,
Y_minus_X: &self.Y - &self.X,
Z: self.Z,
T2d: &self.T * &constants::EDWARDS_D2,
}
}
impl Add for &'a EdwardsPoint {
type Output = CompletedPoint;
fn add(self, other: &'b ProjectiveNielsPoint) -> CompletedPoint {
let Y_plus_X = &self.Y + &self.X;
let Y_minus_X = &self.Y - &self.X;
let PP = &Y_plus_X * &other.Y_plus_X;
let MM = &Y_minus_X * &other.Y_minus_X;
let TT2d = &self.T * &other.T2d;
let ZZ = &self.Z * &other.Z;
let ZZ2 = &ZZ + &ZZ;
CompletedPoint{
X: &PP - &MM,
Y: &PP + &MM,
Z: &ZZ2 + &TT2d,
T: &ZZ2 - &TT2d
}
}
}
P r o j e c t i v e N i e l s P o i n t : ( Y + X , Y − X , Z , 2 d T ) ProjectiveNielsPoint: (Y+X, Y-X, Z, 2dT) ProjectiveNielsPoint:(Y+X,Y−X,Z,2dT)。
2. edwards25519 sub算法根据Extended twisted Edwards curve坐标系， 在Extended坐标系下， ( X : Y : T : Z ) (X:Y:T:Z) (X:Y:T:Z)的负数为 ( − X : Y : − T : Z ) (-X:Y:-T:Z) (−X:Y:−T:Z)， ⇒ P 1 − P 2 = P 1 + ( − P 2 ) = ( X 1 : Y 1 : T 1 : Z 1 ) + ( − X 2 : Y 2 : − T 2 : Z 2 ) \Rightarrow P_1-P_2=P_1+(-P_2)=(X_1:Y_1:T_1:Z_1)+(-X_2:Y_2:-T_2:Z_2) ⇒P1−P2=P1+(−P2)=(X1:Y1:T1:Z1)+(−X2:Y2:−T2:Z2)。
相应的代码实现如下：
impl Sub for &'a EdwardsPoint {
type Output = EdwardsPoint;
fn sub(self, other: &'b EdwardsPoint) -> EdwardsPoint {
(self - &other.to_projective_niels()).to_extended()
}
}
impl Sub for &'a EdwardsPoint {
type Output = CompletedPoint;
fn sub(self, other: &'b ProjectiveNielsPoint) -> CompletedPoint {
let Y_plus_X = &self.Y + &self.X;
let Y_minus_X = &self.Y - &self.X;
let PM = &Y_plus_X * &other.Y_minus_X;
let MP = &Y_minus_X * &other.Y_plus_X;
let TT2d = &self.T * &other.T2d;
let ZZ = &self.Z * &other.Z;
let ZZ2 = &ZZ + &ZZ;
CompletedPoint{
X: &PM - &MP,
Y: &PM + &MP,
Z: &ZZ2 - &TT2d,
T: &ZZ2 + &TT2d
}
}
}
参考资料： [1] Extended twisted Edwards curve坐标系 [2] 论文《Twisted Edwards Curves Revisited》 [3] https://doc-internal.dalek.rs/curve25519_dalek/backend/serial/curve_models/index.html
