DER签名（下）

在上一篇中介绍了DER签名的编码格式为：
$0 x 30 [t o t a l ? l e n g t h] 0 x 02 [R ? l e n g t h] [R] 0 x 02 [S ? l e n g t h] [S] [s i g h a s h]$
其中还介绍了如果r或s的一个字节大于等于0x80，则在r或s前置0x00，这是因为如果最高位为1在DER编码看来这就应该是个负值，本来应该作为无符号数的r或s就会被当做有符号数，因此在前面需要加一个0x00。

在本篇代码分析中有部分涉及到“Low S values in signatures”规则，就是对上面的前置0x00的进一步讨论。现在规定，第一位设置0x00的r或s值称为高，第一位未设置0x00的r或s值称为低。

r 和s值是随机的。当两个值都为高时（都设置了第一个位），它们就都需要一个前置的 0x00字节。使用两个额外字节0x00，编码的r值和s值导致签名总长度为72个字节（不算[sighash]）。在同一签名中两个值都很高的概率是 25%。直到 2014 年初，在区块链上可以观察到大约25%的72字节、50%的71字节和大约25%的70字节签名的分布。在71字节签名中，两个值之一为高，另一个为低。在70字节的签名中，两个值都必须是低。

2014年3月，Bitcoin Core v0.9.0版本开始减少高s值签名的份额。此版本包含对BitcoinCore钱包的更改，仅创建低s签名。随着2015年10月BitcoinCore v0.10.3和v0.11.1的发布，高s签名变得非标准，以完全消除延展性向量。这禁止具有高s值的交易被中继或用于挖矿。从 2015年12月开始，区块链上的几乎所有交易的签名中都只有低值。

既然现在比特币里面都开始用低s了，那么怎么把高s转换为低s呢？

方法很简单，用n值（有限域的秩n）减去s值就行了，n的值在libsecp256k1比特币密码算法开源库（五）里面给出过：
在这里插入图片描述
下面只需要
$n ? s$
就可以了，也就是：
0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 - S

数字签名Signature

下面的Signature定义的函数中parse_overflowing、parse_standard、parse_standard_slice和parse_der在上一篇中已经介绍过了，本篇主要介绍后面的normalize_s、serialize和serialize_der。

impl Signature {
    //允许签名溢出的反序列化
    pub fn parse_overflowing(p: &[u8; util::SIGNATURE_SIZE]) -> Signature {
        let mut r = Scalar::default();
        let mut s = Scalar::default();

        let _ = r.set_b32(array_ref!(p, 0, 32));
        let _ = s.set_b32(array_ref!(p, 32, 32));

        Signature { r, s }
    }

    //未溢出的签名的反序列化
    pub fn parse_standard(p: &[u8; util::SIGNATURE_SIZE]) -> Result<Signature, Error> {
        let mut r = Scalar::default();
        let mut s = Scalar::default();

        let overflowed_r = r.set_b32(array_ref!(p, 0, 32));
        let overflowed_s = s.set_b32(array_ref!(p, 32, 32));

        if bool::from(overflowed_r | overflowed_s) {
            return Err(Error::InvalidSignature);
        }

        Ok(Signature { r, s })
    }


    //复制未溢出的反序列化签名
    pub fn parse_standard_slice(p: &[u8]) -> Result<Signature, Error> {
        if p.len() != util::SIGNATURE_SIZE {
            return Err(Error::InvalidInputLength);
        }

        let mut a = [0; util::SIGNATURE_SIZE];
        a.copy_from_slice(p);
        Ok(Self::parse_standard(&a)?)
    }

    //将DER格式的签名反序列化
    pub fn parse_der(p: &[u8]) -> Result<Signature, Error> {
        let mut decoder = Decoder::new(p);

        decoder.read_constructed_sequence()?;
        let rlen = decoder.read_len()?;

        if rlen != decoder.remaining_len() {
            return Err(Error::InvalidSignature);
        }

        let r = decoder.read_integer()?;
        let s = decoder.read_integer()?;

        if decoder.remaining_len() != 0 {
            return Err(Error::InvalidSignature);
        }

        Ok(Signature { r, s })
    }
   //将s规范化为低s
    pub fn normalize_s(&mut self) {
        if self.s.is_high() {
            self.s = -self.s;
        }
    }

    //将签名序列化为未溢出的格式，也就是上面的函数`parse_standard`的逆过程
    pub fn serialize(&self) -> [u8; util::SIGNATURE_SIZE] {
        let mut ret = [0u8; 64];
        self.r.fill_b32(array_mut_ref!(ret, 0, 32));
        self.s.fill_b32(array_mut_ref!(ret, 32, 32));
        ret
    }

    //将签名序列化为DER编码格式，也就是函数`parse_der`的逆过程
    pub fn serialize_der(&self) -> SignatureArray {
        fn fill_scalar_with_leading_zero(scalar: &Scalar) -> [u8; 33] {
            let mut ret = [0u8; 33];
            scalar.fill_b32(array_mut_ref!(ret, 1, 32));
            ret
        }

        let r_full = fill_scalar_with_leading_zero(&self.r);
        let s_full = fill_scalar_with_leading_zero(&self.s);

        fn integer_slice(full: &[u8; 33]) -> &[u8] {
            let mut len = 33;
            while len > 1 && full[full.len() - len] == 0 && full[full.len() - len + 1] < 0x80 {
                len -= 1;
            }
            &full[(full.len() - len)..]
        }

        let r = integer_slice(&r_full);
        let s = integer_slice(&s_full);

        let mut ret = SignatureArray::new(6 + r.len() + s.len());
        {
            let l = ret.as_mut();
            l[0] = 0x30;
            l[1] = 4 + r.len() as u8 + s.len() as u8;
            l[2] = 0x02;
            l[3] = r.len() as u8;
            l[4..(4 + r.len())].copy_from_slice(r);
            l[4 + r.len()] = 0x02;
            l[5 + r.len()] = s.len() as u8;
            l[(6 + r.len())..(6 + r.len() + s.len())].copy_from_slice(s);
        }

        ret
    }
}

数字签名s值的规范化

本函数实现将高s转换为低s，即将大于n的s转化为n-s：

pub fn normalize_s(&mut self) {
        if self.s.is_high() {
            self.s = -self.s;
        }
    }

判断s是否为高s通过调用is_high函数来实现：

/// Check whether a scalar is higher than the group order divided by 2.
    pub fn is_high(&self) -> bool {
        let mut yes: Choice = 0.into();
        let mut no: Choice = 0.into();
        no |= Choice::from((self.0[7] < SECP256K1_N_H_7) as u8);
        yes |= Choice::from((self.0[7] > SECP256K1_N_H_7) as u8) & !no;
        no |= Choice::from((self.0[6] < SECP256K1_N_H_6) as u8) & !yes; /* No need for a > check. */
        no |= Choice::from((self.0[5] < SECP256K1_N_H_5) as u8) & !yes; /* No need for a > check. */
        no |= Choice::from((self.0[4] < SECP256K1_N_H_4) as u8) & !yes; /* No need for a > check. */
        no |= Choice::from((self.0[3] < SECP256K1_N_H_3) as u8) & !yes;
        yes |= Choice::from((self.0[3] > SECP256K1_N_H_3) as u8) & !no;
        no |= Choice::from((self.0[2] < SECP256K1_N_H_2) as u8) & !yes;
        yes |= Choice::from((self.0[2] > SECP256K1_N_H_2) as u8) & !no;
        no |= Choice::from((self.0[1] < SECP256K1_N_H_1) as u8) & !yes;
        yes |= Choice::from((self.0[1] > SECP256K1_N_H_1) as u8) & !no;
        yes |= Choice::from((self.0[0] >= SECP256K1_N_H_0) as u8) & !no;
        yes.into()
    }

下面是上面函数使用的一些定义常量的取值:

const SECP256K1_N: [u32; 8] = [
    0xD0364141, 0xBFD25E8C, 0xAF48A03B, 0xBAAEDCE6, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
];

const SECP256K1_N_H_0: u32 = 0x681B20A0;
const SECP256K1_N_H_1: u32 = 0xDFE92F46;
const SECP256K1_N_H_2: u32 = 0x57A4501D;
const SECP256K1_N_H_3: u32 = 0x5D576E73;
const SECP256K1_N_H_4: u32 = 0xFFFFFFFF;
const SECP256K1_N_H_5: u32 = 0xFFFFFFFF;
const SECP256K1_N_H_6: u32 = 0xFFFFFFFF;
const SECP256K1_N_H_7: u32 = 0x7FFFFFFF;

数字签名的序列化

本函数实现将数字签名的r部分和s部分分别序列化。首先创建一个64字节的ret数组（64个数组元素，每个数组元素一字节），并初始化数组元素全为0。然后调用fill_b32函数实现将反序列化的r和s转化为序列化的r和s。

pub fn serialize(&self) -> [u8; util::SIGNATURE_SIZE] {
        let mut ret = [0u8; 64];
        self.r.fill_b32(array_mut_ref!(ret, 0, 32));
        self.s.fill_b32(array_mut_ref!(ret, 32, 32));
        ret
    }

函数fill_b32实现过程如下所示。r和s在序列化前共32字节，为Scalar类型，用8个数组元素，数组元素为u32类型；现在转化为32个数组元素，数组元素为u8类型。

    pub fn fill_b32(&self, bin: &mut [u8; 32]) {
        bin[0] = (self.0[7] >> 24) as u8;
        bin[1] = (self.0[7] >> 16) as u8;
        bin[2] = (self.0[7] >> 8) as u8;
        bin[3] = (self.0[7]) as u8;
        bin[4] = (self.0[6] >> 24) as u8;
        bin[5] = (self.0[6] >> 16) as u8;
        bin[6] = (self.0[6] >> 8) as u8;
        bin[7] = (self.0[6]) as u8;
        bin[8] = (self.0[5] >> 24) as u8;
        bin[9] = (self.0[5] >> 16) as u8;
        bin[10] = (self.0[5] >> 8) as u8;
        bin[11] = (self.0[5]) as u8;
        bin[12] = (self.0[4] >> 24) as u8;
        bin[13] = (self.0[4] >> 16) as u8;
        bin[14] = (self.0[4] >> 8) as u8;
        bin[15] = (self.0[4]) as u8;
        bin[16] = (self.0[3] >> 24) as u8;
        bin[17] = (self.0[3] >> 16) as u8;
        bin[18] = (self.0[3] >> 8) as u8;
        bin[19] = (self.0[3]) as u8;
        bin[20] = (self.0[2] >> 24) as u8;
        bin[21] = (self.0[2] >> 16) as u8;
        bin[22] = (self.0[2] >> 8) as u8;
        bin[23] = (self.0[2]) as u8;
        bin[24] = (self.0[1] >> 24) as u8;
        bin[25] = (self.0[1] >> 16) as u8;
        bin[26] = (self.0[1] >> 8) as u8;
        bin[27] = (self.0[1]) as u8;
        bin[28] = (self.0[0] >> 24) as u8;
        bin[29] = (self.0[0] >> 16) as u8;
        bin[30] = (self.0[0] >> 8) as u8;
        bin[31] = (self.0[0]) as u8;
    }

序列化数字签名转化为DER格式

首先在这里摆上DER序列化的格式:
$0 x 30 [t o t a l ? l e n g t h] 0 x 02 [R ? l e n g t h] [R] 0 x 02 [S ? l e n g t h] [S]$
本函数实现将已经序列化的数字签名的r和s转化为DER序列化格式。

在下面的代码中，首先变量r_full和s_full调用了函数fill_scalar_with_leading_zero，生成了一个包含33个u8类型的0的数组元素，也就是
$_{full}= \overbrace{ [0]\cdot\cdot\cdot[0] }^{33\text{个}}\\s _{full}= \overbrace{ [0]\cdot\cdot\cdot[0] }^{33\text{个}}$
之所以是33个，是因为r和s本来32位，但考虑可能出现高r高s需要再加一个0x00，需要再添一个字节。

然后变量r和s调用了函数integer_slice，实现将序列化的r和s最小化，也就是将高位的0字节抹去，如果抹去了该0字节使得最高位字节大于0x80，则不抹去，这个函数会使得r和s最小。

然后在 let mut ret = SignatureArray::new(6 + r.len() + s.len());中实现DER的生成。
l[0] = 0x30;表示DER格式的第一个字段；
l[1] = 4 + r.len() as u8 + s.len() as u8;表示计算[total-length]；
l[2] = 0x02;表示DER格式的0x02字段，也就是r的开始字段；
l[3] = r.len() as u8;表示计算[R-length]，调用len函数实现；
l[4..(4 + r.len())].copy_from_slice(r);将integer_slice生成的r直接复制到[R]中
l[4 + r.len()] = 0x02;表示DER格式的0x02字段，也就是s的开始字段；
l[5 + r.len()] = s.len() as u8;表示计算[S-length]，调用len函数实现；
l[(6 + r.len())..(6 + r.len() + s.len())].copy_from_slice(s);将integer_slice生成的s直接复制到[S]中。
DER生成结束。

 pub fn serialize_der(&self) -> SignatureArray {
 //r和s初始化
        fn fill_scalar_with_leading_zero(scalar: &Scalar) -> [u8; 33] {
            let mut ret = [0u8; 33];
            scalar.fill_b32(array_mut_ref!(ret, 1, 32));
            ret
        }

        let r_full = fill_scalar_with_leading_zero(&self.r);
        let s_full = fill_scalar_with_leading_zero(&self.s);
//r和s最小化
        fn integer_slice(full: &[u8; 33]) -> &[u8] {
            let mut len = 33;
            while len > 1 && full[full.len() - len] == 0 && 
            full[full.len() - len + 1] < 0x80 {
                len -= 1;
            }
            &full[(full.len() - len)..]
        }

        let r = integer_slice(&r_full);
        let s = integer_slice(&s_full);
//生成DER
        let mut ret = SignatureArray::new(6 + r.len() + s.len());
        {
            let l = ret.as_mut();
            l[0] = 0x30;
            l[1] = 4 + r.len() as u8 + s.len() as u8;
            l[2] = 0x02;
            l[3] = r.len() as u8;
            l[4..(4 + r.len())].copy_from_slice(r);
            l[4 + r.len()] = 0x02;
            l[5 + r.len()] = s.len() as u8;
            l[(6 + r.len())..(6 + r.len() + s.len())].copy_from_slice(s);
        }

        ret
    }
}

上面函数中使用了SignatureArray结构体：

pub struct SignatureArray([u8; 6 + 33 + 33], usize);

SignatureArray结构体定义了如下函数，包括初始化一个DER序列、计算长度和判断长度是否为0。

impl SignatureArray {
    pub fn new(size: usize) -> Self {
        SignatureArray([0u8; 6 + 33 + 33], size)
    }

    pub fn len(&self) -> usize {
        self.1
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}