本文共 3944 字,大约阅读时间需要 13 分钟。
接前一博客。
Twisted Edwards curves的affine坐标系表示为:
ε a , d : = { ( x , y ) ∈ P 2 ( F ) : a ∗ x 2 + y 2 = 1 + d ∗ x 2 ∗ y 2 } \varepsilon_{a,d}:=\{(x,y)\in P^2(F):a*x^2+y^2=1+d*x^2*y^2\} εa,d:={ (x,y)∈P2(F):a∗x2+y2=1+d∗x2∗y2}
对应的Extended坐标系表示为:
ε a , d : = { ( X : Y : Z : T ) ∈ P 3 ( F ) : X Y = Z T a n d a ∗ X 2 + Y 2 = Z 2 + d ∗ T 2 } \varepsilon_{a,d}:=\{(X:Y:Z:T)\in P^3(F):XY=ZT\ and\ a*X^2+Y^2=Z^2+d*T^2\} εa,d:={ (X:Y:Z:T)∈P3(F):XY=ZT and a∗X2+Y2=Z2+d∗T2}
Edwards curve的identity point表示为 ( 0 , 1 ) = ( 0 : 1 : 1 : 0 ) (0,1)=(0:1:1:0) (0,1)=(0:1:1:0)。
affine坐标系与extended坐标系之间的映射关系为:
x = X / Z , y = Y / Z , X Y = Z T , x y = T / Z x=X/Z,y=Y/Z,XY=ZT,xy=T/Z x=X/Z,y=Y/Z,XY=ZT,xy=T/Z
s = − a 2 1 − y 1 + y = − a 2 1 − Y / Z 1 + Y / Z = − a 2 Z − Y Z 2 − Y 2 s=\sqrt{-a_2\frac{1-y}{1+y}}=\sqrt{-a_2\frac{1-Y/Z}{1+Y/Z}}=\sqrt{-a_2}{\frac{Z-Y}{\sqrt{Z^2-Y^2}}} s=−a21+y1−y=−a21+Y/Z1−Y/Z=−a2Z2−Y2Z−Y
由此可知,需要计算 1 / Z 2 − Y 2 1/\sqrt{Z^2-Y^2} 1/Z2−Y2。
根据前一博客第1.3节描述,对于带压缩点 P ( x 0 , y 0 ) P(x_0,y_0) P(x0,y0)需与2-torsion point ( 0 , − 1 ) 或 ( 0 , 1 ) (0,-1)或(0,1) (0,−1)或(0,1)求和,然后根据 x y ? > 0 xy?>0 xy?>0,来决定是否需要再需要与点 Q 4 Q_4 Q4【当 a = 1 a=1 a=1时, Q 4 = ( 1 , 0 ) Q_4=(1,0) Q4=(1,0);当 a = − 1 a=-1 a=−1时, Q 4 = ( i , 0 ) , i 2 = − 1 Q_4=(i,0),i^2=-1 Q4=(i,0),i2=−1。因 a 2 = 1 a^2=1 a2=1,可统一描述为 Q 4 = ( 1 / a , 0 ) Q_4=(1/\sqrt{a},0) Q4=(1/a,0)】求和。
P ( x 0 , y 0 ) ↦ ( x , y ) P(x_0,y_0)\mapsto(x,y) P(x0,y0)↦(x,y) affine坐标系下的压缩算法的第一二步内容可梳理为:
P ( X 0 : Y 0 : Z 0 : T 0 ) ↦ ( X : Y : Z : T ) P(X_0:Y_0:Z_0:T_0)\mapsto(X:Y:Z:T) P(X0:Y0:Z0:T0)↦(X:Y:Z:T)衍生到extended坐标系下压缩算法的第一二步内容可梳理为:
( X : Y : Z : T ) = { ( X 0 : Y 0 : Z 0 : T 0 ) ( Y 0 / a : − a X 0 : Z 0 : − T 0 ) (X:Y:Z:T)=\left\{\begin{matrix} (X_0:Y_0:Z_0:T_0)\\ (Y_0/\sqrt{a}:-\sqrt{a}X_0:Z_0:-T_0) \end{matrix}\right. (X:Y:Z:T)={ (X0:Y0:Z0:T0)(Y0/a:−aX0:Z0:−T0)
⇒ 1 / Z 2 − Y 2 = { 1 / Z 0 2 − Y 0 2 1 / Z 0 2 − a X 0 2 \Rightarrow 1/\sqrt{Z^2-Y^2}=\left\{\begin{matrix} 1/\sqrt{Z_0^2-Y_0^2}\\ 1/\sqrt{Z_0^2-aX_0^2} \end{matrix}\right. ⇒1/Z2−Y2={ 1/Z02−Y021/Z02−aX02
同时:
ε a , d : = { ( X : Y : Z : T ) ∈ P 3 ( F ) : X Y = Z T a n d a ∗ X 2 + Y 2 = Z 2 + d ∗ T 2 } \varepsilon_{a,d}:=\{(X:Y:Z:T)\in P^3(F):XY=ZT\ and\ a*X^2+Y^2=Z^2+d*T^2\} εa,d:={ (X:Y:Z:T)∈P3(F):XY=ZT and a∗X2+Y2=Z2+d∗T2}
⇒ − d X 2 Y 2 = Z 4 − a X 2 Z 2 − Y 2 Z 2 \Rightarrow -dX^2Y^2=Z^4-aX^2Z^2-Y^2Z^2 ⇒−dX2Y2=Z4−aX2Z2−Y2Z2
⇒ ( a − d ) X 2 Y 2 = Z 4 − a X 2 Z 2 − Y 2 Z 2 + a X 2 Y 2 = ( Z 2 − Y 2 ) ( Z 2 − a X 2 ) \Rightarrow (a-d)X^2Y^2=Z^4-aX^2Z^2-Y^2Z^2+aX^2Y^2=(Z^2-Y^2)(Z^2-aX^2) ⇒(a−d)X2Y2=Z4−aX2Z2−Y2Z2+aX2Y2=(Z2−Y2)(Z2−aX2)
⇒ 1 Z 2 − a X 2 = 1 a − d Z 2 − Y 2 X 2 Y 2 \Rightarrow \frac{1}{Z^2-aX^2}=\frac{1}{a-d}\frac{Z^2-Y^2}{X^2Y^2} ⇒Z2−aX21=a−d1X2Y2Z2−Y2
⇒ 1 Z 2 − a X 2 = 1 a − d Z 2 − Y 2 X 2 Y 2 \Rightarrow \frac{1}{\sqrt{Z^2-aX^2}}=\frac{1}{\sqrt{a-d}}\sqrt{\frac{Z^2-Y^2}{X^2Y^2}} ⇒Z2−aX21=a−d1X2Y2Z2−Y2
所以,extended坐标系下总的压缩公式计算如下:【其中下图第9步是因为 P + ε a , d [ 2 ] = { ( x , y ) , ( − x , − y ) } P+\varepsilon_{a,d}[2]=\{(x,y),(-x,-y)\} P+εa,d[2]={ (x,y),(−x,−y)},即经过上图第一和第二步,所有的点都扭转到了 ε ε [ 2 ] \frac{\varepsilon}{\varepsilon[2]} ε[2]ε。】
affine坐标系下,解压缩算法为根据 s s s值,求相应的 ( x , y ) (x,y) (x,y)。
extended坐标系下,解压缩算法为根据 s s s值,求相应的 ( x , y , 1 , t ) (x,y,1,t) (x,y,1,t)。
根据前一博客第3节描述有:
⇒ y = 1 + a 2 s 2 1 − a 2 s 2 \Rightarrow y=\frac{1+a_2s^2}{1-a_2s^2} ⇒y=1−a2s21+a2s2
⇒ x = + 4 s 2 a 2 d 2 ( 1 + a 2 s 2 ) 2 − ( 1 − a 2 s 2 ) 2 \Rightarrow x=+\sqrt{\frac{4s^2}{a_2d_2(1+a_2s^2)^2-(1-a_2s^2)^2}} ⇒x=+a2d2(1+a2s2)2−(1−a2s2)24s2
extended坐标系下,额外有:
⇒ t = x y \Rightarrow t=xy ⇒t=xy
所以,总的解压缩公式为:
参考资料:
[1] https://ristretto.group/details/encoding_in_extended.html
转载地址:http://ebqx.baihongyu.com/