edwards25519 point压缩及解压缩算法

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 ⇒ x 2 = ( y 2 − 1 ) / ( d y 2 + 1 )   ( m o d   q ) \Rightarrow x^2=(y^2-1)/(dy^2+1)\ (mod\ q) ⇒x2=(y2−1)/(dy2+1) (mod q)

0. 为何edwards curve point可以压缩

根据论文《Twisted Edwards Curves Revisited》有： 可知 ( − x , y ) + ( x , y ) = ( 0 , 1 ) = ∞ (-x,y)+(x,y)=(0,1)=\infty (−x,y)+(x,y)=(0,1)=∞ 所以， ( 0 , 1 ) (0,1) (0,1)不在 F p F_p Fp​ subgroup中（其中，对于Curve25519， p = 8 q , q = 2 252 + 27742317777372353535851937790883648493 p=8q,q=2^{252} + 27742317777372353535851937790883648493 p=8q,q=2252+27742317777372353535851937790883648493）。 因此： ( − x , y ) 和 ( x , y ) (-x,y)和(x,y) (−x,y)和(x,y)不可以同时在同一个subgroup中，于是可以直接取 y y y坐标和 x x x坐标的符号位来表示唯一点。

以上内容参考https://ethresear.ch/t/some-snarky-tricks-from-ethboston-zeropool-under-the-hood/6115：（dalek-Curve25519中的压缩算法采用是 ( − x , y ) 和 ( x , y ) (-x,y)和(x,y) (−x,y)和(x,y)，github.com/snjax/circomlib中采用的压缩算法是 ( x , y ) 和 ( x , − y ) (x,y)和(x,-y) (x,y)和(x,−y)）。

1. compression压缩算法

将edwards25519的point ( x , y ) (x,y) (x,y)，其中每个 x , y x,y x,y均可以little-endian数组[u8;32]表示，表示一个point 需要2个[u8;32]数组。 通过压缩算法，可用一个[u8;32]数组来表示point ( x , y ) (x,y) (x,y)。具体的压缩算法为： E n c ( x , y ) = ( y ∣ x < < 255 ) Enc(x,y)=(y|x<<255) Enc(x,y)=(y∣x