2021SC@SDUSC

本篇将介绍libsecp256k1中如何定义Affine坐标和Jacobian加重射影坐标，并实现其相应的函数。通过将椭圆曲线上的点坐标从仿射坐标转换到射影坐标中，就可以巧妙地避开扩展欧几里得算法求乘法逆元，大大提高算法执行计算效率，有关Affine坐标和Jacobian加重射影坐标的相关底层数学知识我在博客：椭圆曲线——从仿射坐标到雅可比坐标的转换中写的比较详细了，有需要可以去了解一下。

由于本开源库用Rust语言编写，开始前先说一下Rust提供的模块系统，自顶向下依次为：
包（package）：一个用于构建、测试并共享crate的Cargo功能。
单元包（crate）：一个用于生成library（库）或可执行文件的树形模块结构。
模块（module）、use：控制代码结构、作用域及路径的私有路径。
路径（path）：一种用于命名条目的方法，这些条目包括struct、function和module等。

package与crate
一个package由一个或多个crate组成，一个package带有一个Cargo.toml描述构筑crate的信息。crate可以被用作生成二进制程序或库。
package可以包含：最多一个库crate（lib）；package可以拥有任意多个二进制包；package内至少要有一个crate（库crate或二进制crate）。

Curve曲线结构

下面定义了曲线curve模块结构，它使用了如下的crate：

pub mod curve {
    pub use crate::{
        field::{Field, FieldStorage},
        group::{Affine, AffineStorage, Jacobian, AFFINE_G, CURVE_B},
        scalar::Scalar,
    };

    pub use crate::ecmult::{ECMultContext, ECMultGenContext};
}

其中，
Field定义secp256k1的有限域$GF(p)$元素。
FieldStorage实现紧凑的域元素存储。在libsecp256k1库中 定义了Field元素为320位，但Field可以被压缩成 FieldStorage, 也就是常见的256位，便于存储。
具体请参考libsecp256k1比特币密码算法开源库（八）

Affine，在仿射坐标中定义secp256k1曲线的一组元素。
AffineStorage实现仿射坐标群元紧凑存储。
Jacobian，在雅可比射影坐标中定义secp256k1曲线的一组元素。

AFFINE_G定义了secp256k1在仿射坐标中的生成元G点的横纵坐标，G点的横纵坐标我在libsecp256k1比特币密码算法开源库（五）中曾经给出过。可以看到每个逗号隔开8位16进制数，每个16进制数可用4位比特表示，也就是说每个逗号隔开32位比特，和一个int大小一样。

pub static AFFINE_G: Affine = Affine::new(
//开头的0x表示使用16进制表示
    Field::new(
        0x79BE667E, 0xF9DCBBAC, 0x55A06295, 0xCE870B07, 0x029BFCDB, 0x2DCE28D9, 0x59F2815B, 0x16F81798,
    ),//G点的横坐标
    Field::new(
        0x483ADA77, 0x26A3C465, 0x5DA4FBFC, 0x0E1108A8, 0xFD17B448, 0xA6855419, 0x9C47D08F, 0xFB10D4B8,
    ),//G点的纵坐标
);

CURVE_B定义了secp256k1方程参数b（b为常量=7）。

pub const CURVE_B: u32 = 7;
//u32即为32比特（可以看做int）
//在Rust语言中，声明变量默认是不可修改的
//如果是可修改的变量要在变量名前加关键字mut

Scalar为256位标量值。secp256k1中多处用到标量scalar，其中私钥和数字签名中使用的随机数k都是标量。
ECMultContext 对形如$aP+bG$的运算使用ecmult函数实现高效运算。
ECMultGenContext 对形如$aG$的运算使用ecmult_gen函数实现高效运算。
具体请参考libsecp256k1比特币密码算法开源库（九）

由于内容比较多，本篇主要介绍Affine和Jacobian结构定义和相关实现。为了让数学公式结合代码更加清晰，我在代码片段中写了详尽的注释，如有需要可留意。

Affine 仿射坐标

定义仿射坐标下点的结构体，其中x和y值都是Field型变量，还有一个bool型变量infinty表示无穷远点。

pub struct Affine {
    pub x: Field,
    pub y: Field,
    pub infinity: bool,
}

相关函数实现：
1.创建一个仿射坐标中的点。Self代表的是Affine类型的点，对于类型名字很长的时候或者频繁变更的时候，这样可以很省事。

  pub const fn new(x: Field, y: Field) -> Self {
        Self {
            x,
            y,
            infinity: false,
        }
    }

2.对给定的仿射坐标的x和y值，找到一个在椭圆曲线群中的点：

 pub fn set_xy(&mut self, x: &Field, y: &Field) {
        self.infinity = false;
        self.x = *x;
        self.y = *y;
    }

3.检查椭圆曲线群中的点是否满足椭圆曲线方程：

pub fn is_valid_var(&self) -> bool {
        if self.is_infinity() {
            return false;
        }
        let y2 = self.y.sqr();//令y2为对y求平方
        let mut x3 = self.x.sqr();
        x3 *= &self.x;//x3为对x求立方
        let mut c = Field::default();
        c.set_int(CURVE_B);//c取secp256k1参数b取值，其中b=7
        x3 += &c;//结果x3即为x^3+7,椭圆曲线方程右端
        x3.normalize_weak();
        y2.eq_var(&x3)//判断y2与x3是否相等
    }

4.对给定的Jacobian坐标下的点坐标，找到其在仿射坐标中的对应点：

pub fn set_gej(&mut self, a: &Jacobian) {
        self.infinity = a.infinity;
        let mut a = *a;
        a.z = a.z.inv();
        let z2 = a.z.sqr();
        let z3 = a.z * z2;
        a.x *= z2;
        a.y *= z3;
        a.z.set_int(1);
        self.x = a.x;
        self.y = a.y;
    }

5.清除敏感数据。这里的清除敏感数据体现Rust这个编程语言在设计密码库的一大优势，即Rust对底层的控制能力很好，Rust可以提供对底层内存的直接控制，比如在使用完私钥等机密信息之后可以及时从内存空间完全释放掉。

 pub fn clear(&mut self) {
        self.infinity = false;
        self.x.clear();
        self.y.clear();
    }

Jacobian加重射影坐标

定义Jacobian坐标下点的结构体，其中x、y和z值都是Field型变量，还有一个bool型变量infinty表示无穷远点（前面说过，在Jacobian坐标中该点即为z=0的点）。

pub struct Jacobian {
    pub x: Field,
    pub y: Field,
    pub z: Field,
    pub infinity: bool,
}

1.创建一个Jacobian坐标中的点。z=1的原因即为仿射坐标中的点$(x,y)$对应Jacobian加重射影坐标中的点$(x,y,1)$

pub const fn new(x: Field, y: Field) -> Self {
        Self {
            x,
            y,
            infinity: false,//不为无穷远点
            z: Field::new(0, 0, 0, 0, 0, 0, 0, 1),
        }
    }

2.设置一个等于无穷远点的用Jacobian坐标表示的群元素：

    pub fn set_infinity(&mut self) {
        self.infinity = true;
        self.x.clear();
        self.y.clear();
        self.z.clear();
    }

3.对给定的仿射坐标点，找到对应的Jacobian坐标下的点：

 pub fn set_ge(&mut self, a: &Affine) {
        self.infinity = a.infinity;
        self.x = a.x;
        self.y = a.y;
        self.z.set_int(1);//z值必定为1
    }

4.比较Jacobian坐标下群元素的X坐标：

    pub fn eq_x_var(&self, x: &Field) -> bool {
        debug_assert!(!self.is_infinity());
        //这里 debug_assert! 宏是只在未开启优化的编译包中才有效
        let mut r = self.z.sqr();
        r *= x;
        let mut r2 = self.x;
        r2.normalize_weak();
        r.eq_var(&r2)
    }

5.求a的逆。由于a是一个点，在椭圆曲线构成的群中定义单位元为无穷远点，运算为几何加法运算，则a的逆元实际上就是点a关于坐标轴的对称点。

    pub fn neg_in_place(&mut self, a: &Jacobian) {
        self.infinity = a.infinity;
        self.x = a.x;
        self.y = a.y;
        self.z = a.z;
        self.y.normalize_weak();
        self.y = self.y.neg(1);//neg为相反数指令
    }

6.检查群元素是否为无穷远处的点。

    pub fn is_infinity(&self) -> bool {
        self.infinity
    }

7.检查群元素的y坐标是否为二次剩余。

    pub fn has_quad_y_var(&self) -> bool {
        if self.infinity {
            return false;
        }

        let yz = self.y * self.z;
        yz.is_quad_var()
    }

8.在Jacobian坐标下求2a，即a+a（这里的a是Jacobian坐标下的一个点）。在上一篇中介绍，a=0时，Jacobian加重射影坐标运算过程如下：
$$\begin{gathered} {\lambda }_1=3x_1^2 \\ {\lambda }_2=4x_1{y}_1^2 \\ {\lambda }_3=8y_1^4 \\ {x}_3={\lambda }_1^2-2{\lambda }_2 \\ {y}_3={\lambda }_1({\lambda }_2-x_3)-{\lambda }_3 \\ {z}_3=2y_1{z}_1 \end{gathered}$$下面的代码将会实现上面的运算过程，由于代码实现和数学公式的表达有点不同，而且很多变量取名也会不一致，所以代码和数学公式的详细对应关系我在相应位置给出了注释，代码中 self.x， self.y， self.z的运算结果即为对应的$x_3,y_3,z_3$。

 pub fn double_var_in_place(&mut self, a: &Jacobian, rzr: Option<&mut Field>) {
        self.infinity = a.infinity;
        if self.infinity {
            if let Some(rzr) = rzr {
                rzr.set_int(1);
            }
            return;
        }

        if let Some(rzr) = rzr {
            *rzr = a.y;
            rzr.normalize_weak();
            rzr.mul_int(2);
        }

        self.z = a.z * a.y;
        self.z.mul_int(2);
        //求得self.z为2yz，即a+a得到的点的z坐标，即self.z对应上面公式中的z3
        let mut t1 = a.x.sqr();
        t1.mul_int(3);//t1为3x^2，即t1对应上面公式中的λ1
        let mut t2 = t1.sqr();//t2为λ1的平方
        let mut t3 = a.y.sqr();
        t3.mul_int(2);//t3为2倍的y^2
        let mut t4 = t3.sqr();//此时t4为4倍的y^4
        t4.mul_int(2);//t4为8倍的y^4，则t4对应上面公式中的λ3
        t3 *= &a.x;//此时t3为2y^2乘以x
        self.x = t3;//令self.x等于2y^2乘以x
        self.x.mul_int(4);//此时self.x等于8y^2乘以x，即2倍的λ2
        self.x = self.x.neg(4);//此时self.x等于8y^2乘以x的相反数，即-2倍的λ2
        self.x += &t2;
        //此时self.x等于t2加上-2倍的λ2，由t2为λ1的平方，则self.x对应上面公式中的x3
        t2 = t2.neg(1);//对t2求相反数，即为负的λ1的平方
        t3.mul_int(6);//此时t3为12倍y^2乘以x
        t3 += &t2;//此时t3为12倍y^2乘以x，再减λ1的平方
        self.y = t1 * t3;//此时self.y对应上面公式中的λ1(λ2 −x3)
        t2 = t4.neg(2);//此时t2为−λ3
        self.y += t2;
        //此时self.y为λ1(λ2 −x3)加上t2,得到的结果即为上面公式中的y3
    }

调用上面的函数，计算2a。

pub fn double_var(&self, rzr: Option<&mut Field>) -> Jacobian {
        let mut ret = Jacobian::default();
        ret.double_var_in_place(&self, rzr);
        ret
    }

9.在Jacobian坐标下求a+b（这里的a和b是Jacobian坐标下的一个点）。Jacobian加重射影坐标下的几何加法运算过程如下：$$\begin{gathered} {\lambda }_1=x_1{z}_2^2 \\ {\lambda }_2=x_2{z}_1^2 \\ {\lambda }_3={\lambda }_1-{\lambda }_2 \\ {\lambda }_4=y_1{z}_2^3 \\ {\lambda }_5=y_2{z}_1^3 \\ {\lambda }_6={\lambda }_4-{\lambda }_5 \\ {\lambda }_7={\lambda }_1+{\lambda }_2 \\ {\lambda }_8={\lambda }_4+{\lambda }_5 \\ {x}_3={\lambda }_6^2-{\lambda }_7{\lambda }_3^2 \\ {\lambda }_9={\lambda }_7{\lambda }_3^2-2x_3 \\ {y}_3=({\lambda }_9{\lambda }_6-{\lambda }_8{\lambda }_3^3)/2 \\ {z}_3=z_1{z}_2{\lambda }_3 \end{gathered}$$下面的代码将会实现上面的运算过程，代码和数学公式的对应关系我在相应位置给出了注释，代码中 self.x， self.y， self.z的运算结果即为对应的$x_3,y_3,z_3$。

pub fn add_var_in_place(&mut self, a: &Jacobian, b: &Jacobian, rzr: Option<&mut Field>) {
        if a.is_infinity() {
            debug_assert!(rzr.is_none());
            *self = *b;
            return;
        }
        if b.is_infinity() {
            if let Some(rzr) = rzr {
                rzr.set_int(1);
            }
            *self = *a;
            return;
        }

        self.infinity = false;
        let z22 = b.z.sqr();
        let z12 = a.z.sqr();
        let u1 = a.x * z22;//u1计算结果即为上面数学公式中的λ1
        let u2 = b.x * z12;//u2计算结果即为上面数学公式中的λ2
        let mut s1 = a.y * z22;
        s1 *= b.z;//s1计算结果即为上面数学公式中的λ4
        let mut s2 = b.y * z12;
        s2 *= a.z;//s2计算结果即为上面数学公式中的λ5
        let mut h = u1.neg(1);
        h += u2;//h计算结果即为上面数学公式中的λ3
        let mut i = s1.neg(1);
        i += s2;//i计算结果即为上面数学公式中的λ6
        if h.normalizes_to_zero_var() {
            if i.normalizes_to_zero_var() {
                self.double_var_in_place(a, rzr);
            } else {
                if let Some(rzr) = rzr {
                    rzr.set_int(0);
                }
                self.infinity = true;
            }
            return;
        }
        let i2 = i.sqr();//i2计算结果即为上面数学公式中的λ6的平方
        let h2 = h.sqr();//h2计算结果即为上面数学公式中的λ3的平方
        let mut h3 = h * h2;//h3计算结果即为上面数学公式中的λ3的立方
        h *= b.z;//h计算结果即为上面数学公式中的z2*λ3
        if let Some(rzr) = rzr {
            *rzr = h;
        }
        self.z = a.z * h;
        //self.z计算结果即为上面数学公式中的z1*z2*λ3，即为z3
        let t = u1 * h2;//t计算结果即为上面数学公式中的λ1*λ3的平方
        self.x = t;
        self.x.mul_int(2);//这里self.x计算结果即为2 λ1*(λ3)^2
        self.x += h3;//这里self.x计算结果即为2 λ1*(λ3)^2 + (λ3)^3
        self.x = self.x.neg(3);
        self.x += i2;
        //self.x计算结果即x3
        self.y = self.x.neg(5);
        self.y += t;
        self.y *= i;
        h3 *= s1;
        h3 = h3.neg(1);
        self.y += h3;
        //self.y计算结果即y3
    }

调用上面的函数，计算a+b。

pub fn add_var(&self, b: &Jacobian, rzr: Option<&mut Field>) -> Jacobian {
        let mut ret = Jacobian::default();
        ret.add_var_in_place(self, b, rzr);
        ret
    }

10.清除敏感数据，防止敏感信息泄露。

    pub fn clear(&mut self) {
        self.infinity = false;
        self.x.clear();
        self.y.clear();
        self.z.clear();
    }