ristretto255 point压缩和解压缩算法（2）——extended坐标系下

接前一博客ristretto255 point压缩和解压缩算法（1）——affine坐标系下。

1、affine坐标系与extended坐标系之间的映射关系

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

2、extended坐标系下的压缩

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=−a2​1+y1−y​ ​=−a2​1+Y/Z1−Y/Z​ ​=−a2​ ​Z2−Y2 ​Z−Y​

由此可知，需要计算 1 / Z 2 − Y 2 1/\sqrt{Z^2-Y^2} 1/Z2−Y2 ​。

根据前一博客ristretto255 point压缩和解压缩算法（1）——affine坐标系下第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坐标系下的压缩算法的第一二步内容可梳理为:

• ( x 0 , y 0 ) + ( 0 , 1 ) = ( x 0 , y 0 ) (x_0,y_0)+(0,1)=(x_0,y_0) (x0​,y0​)+(0,1)=(x0​,y0​)
• 当 x 0 y 0 < = 0 x_0y_0<=0 x0​y0​