libsecp256k1比特币密码算法开源库（八）
2021SC@SDUSC
secp256k1曲线Curve结构定义——域元素的运算与压缩存储
在libsecp256k1中对域元素进行了定义，其中
Field定义secp256k1的有限域
G
F
(
p
)
GF(p)
GF(p)元素,为了方便进行域下的模加法和模乘法运算，在libsecp256k1库中定义的Field元素是320位，并不是常见的256位。在进行相应的运算结束后会在
FieldStorage中实现紧凑的域元素存储，将Field中的元素压缩为256位，便于存储。
由于域元素都是长达256位的大整数，对大整数的存储采用数组来实现，在有的资料中也将这个过程称为序列化。在libsecp256k1中域元素（即椭圆曲线群元素点的横纵坐标）的序列化存储采用的都是大端序，即高位字节存入低地址，低位字节存入高地址。
在libsecp256k1中对大整数的加法乘法运算进行了定义和实现。
Field域元素
Field元素是320位，也就是说使用了10个u32构成的数组表示一个域元素大整数，但实际上每个数组元素有效的只有26位，10*26=260也足以表示256位的域元素。域元素的高位存储在数组的高位，域元素的低位存储在数组的低位，因此对于一个大整数的实际值可以表示为：
X
=
∑
i
=
0..9
n
[
i
]
∗
2
(
i
∗
26
)
m
o
d
p
X = sum_{i=0..9} n[i]*2^{(i*26)},mod,p
X=∑i=0..9n[i]∗2(i∗26)modp，在代码中数据的存储和表示都采用16进制，用0x表示十六进制的前缀，所以上面的
p
=
2
256
−
0
x
1000003
D
1
p = 2^{256} - 0x1000003D1
p=2256−0x1000003D1。
下面是定义的Field域元素结构体：
pub struct Field {
n: [u32; 10],
magnitude: u32,
normalized: bool,
}
每个Field元素320位，用10个u32数组元素表示。
impl Field {
pub const fn new_raw(
d9: u32,
d8: u32,
d7: u32,
d6: u32,
d5: u32,
d4: u32,
d3: u32,
d2: u32,
d1: u32,
d0: u32,
) -> Self {
Self {
n: [d0, d1, d2, d3, d4, d5, d6, d7, d8, d9],
magnitude: 1,
normalized: false,
}
}
域元素加法实现
impl<'a> AddAssign<&'a Field> for Field {
fn add_assign(&mut self, other: &'a Field) {
self.n[0] += other.n[0];
self.n[1] += other.n[1];
self.n[2] += other.n[2];
self.n[3] += other.n[3];
self.n[4] += other.n[4];
self.n[5] += other.n[5];
self.n[6] += other.n[6];
self.n[7] += other.n[7];
self.n[8] += other.n[8];
self.n[9] += other.n[9];
self.magnitude += other.magnitude;
self.normalized = false;
debug_assert!(self.verify());
}
}
域元素乘法实现
impl<'a> MulAssign<&'a Field> for Field {
fn mul_assign(&mut self, other: &'a Field) {
let mut ret = Field::default();
ret.mul_in_place(self, other);
*self = ret;
}
}
FieldStorage域元素紧凑存储
在libsecp256k1中对每个大数以数组的方式存储，每个数组元素为u32即32位比特，在FieldStorage中，每个Field元素为256位比特，用8个u32就可以表示。
impl FieldStorage {
pub const fn new(
d7: u32,
d6: u32,
d5: u32,
d4: u32,
d3: u32,
d2: u32,
d1: u32,
d0: u32,
) -> Self {
Self([d0, d1, d2, d3, d4, d5, d6, d7])
}
下面的代码实现了将320位的域元素压缩为256位存储的过程，首先介绍一下rust语言的语法：
|表示位或，相同位只要有一个是1则返回1，否则返回0；
左移 <<操作数中的所有位向左移动指定位数，右边的位补0；
右移 >>操作数中的所有位向右移动指定位数，左边的位补0。
有了上面的语法想要看懂压缩过程就很容易了只需把对应数组元素0-1比特串做对应运算即可。可以看到赋值号=右侧有10个数组元素，到了赋值号左侧就只有8个，实现了将320位的域元素压缩为256位的存储过程。
想要更好地理解这段代码，应该明白压缩的目的是什么，前面提到在Field中每个数组元素是u32，但只有26位是有效位，其余部分都是无效位，这就使得Field域元素表示成了320位，现在想要只用8个u32的数组元素存储这256位，也就是说不能再有无效位了，也就是说需要把无效位给压缩没，举下面代码一个例子，压缩后的0号数组元素其实就是把压缩前的0号元素的26位和压缩前的1号元素的6位给拼在一起；压缩后的1号数组元素其实就是先将压缩前的1号元素右移6位剩下的20位有效位再和压缩前的2号元素的12位给拼在一起……这也就是下面的8行实现压缩过程的代码所表示的意思。
impl Into<FieldStorage> for Field {
fn into(self) -> FieldStorage {
debug_assert!(self.normalized);
let mut r = FieldStorage::default();
r.0[0] = self.n[0] | self.n[1] << 26;
r.0[1] = self.n[1] >> 6 | self.n[2] << 20;
r.0[2] = self.n[2] >> 12 | self.n[3] << 14;
r.0[3] = self.n[3] >> 18 | self.n[4] << 8;
r.0[4] = self.n[4] >> 24 | self.n[5] << 2 | self.n[6] << 28;
r.0[5] = self.n[6] >> 4 | self.n[7] << 22;
r.0[6] = self.n[7] >> 10 | self.n[8] << 16;
r.0[7] = self.n[8] >> 16 | self.n[9] << 10;
r
}
}
既然可以将Field元素压缩存储，那么必然需要将压缩的结果恢复出来，恢复的过程如下代码所示，还是一样的0-1比特串运算，其中&符号表示位与，即相同位都是1则返回1，否则返回0，这里都是和3FFFFFF位与，即保留后26位。
解压缩就是压缩的逆过程，有了上面部分压缩的过程解释，解压缩也就非常好理解，只需每个数组元素保留26位，其余6位还是无效位即可。
impl From<FieldStorage> for Field {
fn from(a: FieldStorage) -> Field {
let mut r = Field::default();
r.n[0] = a.0[0] & 0x3FFFFFF;
r.n[1] = a.0[0] >> 26 | ((a.0[1] << 6) & 0x3FFFFFF);
r.n[2] = a.0[1] >> 20 | ((a.0[2] << 12) & 0x3FFFFFF);
r.n[3] = a.0[2] >> 14 | ((a.0[3] << 18) & 0x3FFFFFF);
r.n[4] = a.0[3] >> 8 | ((a.0[4] << 24) & 0x3FFFFFF);
r.n[5] = (a.0[4] >> 2) & 0x3FFFFFF;
r.n[6] = a.0[4] >> 28 | ((a.0[5] << 4) & 0x3FFFFFF);
r.n[7] = a.0[5] >> 22 | ((a.0[6] << 10) & 0x3FFFFFF);
r.n[8] = a.0[6] >> 16 | ((a.0[7] << 16) & 0x3FFFFFF);
r.n[9] = a.0[7] >> 10;
r.magnitude = 1;
r.normalized = true;
r
}
}