|
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位的域元素。在FIeld的每个数组元素中除了26位有效位外其余的部分都是0，下面的与或运算也使用到了这一点。域元素的高位存储在数组的高位，域元素的低位存储在数组的低位，因此对于一个大整数的实际值可以表示为：
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..9?n[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,
}
}
由于数组中存放的就是u32类型的变量，可以实现加法，那么域元素加法实现就将对应数组index相加即可。但这里很容易就会想到一个问题，那就是进位。因为要进1，会导致本来26位的有效位这么一加可能有几个数组元素的有效位就成了27位，如果把这样的结果直接压缩存储的话肯定是不行的。在Field结构体中有个boolean型变量normalized，如果normalized为true，表示域元素的所有数组元素都是26位有效位，如果为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());
}
}
前面提到需要对数组元素进行规范化处理，让每个数组元素的有效位都是26位。规范化处理的代码很长，于是我把很显然的就像排比句的部分打个省略号，重点关注算法实现部分。
pub fn normalize(&mut self) {
let mut t0 = self.n[0];
let mut t1 = self.n[1];
......
let mut t9 = self.n[9];
let mut m: u32;
let mut x = t9 >> 22;
t9 &= 0x03fffff;
t0 += x * 0x3d1;
t1 += x << 6;
t1 += t0 >> 26;
t0 &= 0x3ffffff;
t2 += t1 >> 26;
t1 &= 0x3ffffff;
t3 += t2 >> 26;
t2 &= 0x3ffffff;
m = t2;
t4 += t3 >> 26;
t3 &= 0x3ffffff;
m &= t3;
t5 += t4 >> 26;
t4 &= 0x3ffffff;
m &= t4;
t6 += t5 >> 26;
t5 &= 0x3ffffff;
m &= t5;
t7 += t6 >> 26;
t6 &= 0x3ffffff;
m &= t6;
t8 += t7 >> 26;
t7 &= 0x3ffffff;
m &= t7;
t9 += t8 >> 26;
t8 &= 0x3ffffff;
m &= t8;
debug_assert!(t9 >> 23 == 0);
x = (t9 >> 22)
| (if t9 == 0x03fffff { 1 } else { 0 }
& if m == 0x3ffffff { 1 } else { 0 }
& (if (t1 + 0x40 + ((t0 + 0x3d1) >> 26)) > 0x3ffffff {
1
} else {
0
}));
t0 += x * 0x3d1;
t1 += x << 6;
t1 += t0 >> 26;
t0 &= 0x3ffffff;
t2 += t1 >> 26;
t1 &= 0x3ffffff;
t3 += t2 >> 26;
t2 &= 0x3ffffff;
......
t9 += t8 >> 26;
t8 &= 0x3ffffff;
debug_assert!(t9 >> 22 == x);
t9 &= 0x03fffff;
self.n = [t0, t1, t2, t3, t4, t5, t6, t7, t8, t9];
self.magnitude = 1;
self.normalized = true;
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
}
}
|