libsecp256k1比特币密码算法开源库（十一）

admin • 2021-11-29 20:55 • 区块链

2021SC@SDUSC

secp256k1的结构——公钥

公钥解析的格式
公钥PublicKey总述
- 公钥生成函数
- 反序列化

本文将介绍secp256k1定义的公钥结构，主要介绍公钥的三种格式以及公钥相应的函数实现。

公钥解析的格式

公钥的格式下面例举了三种，分别是Compressed、Full和Raw：

pub enum PublicKeyFormat {
    /// Compressed public key, 33 bytes.
    Compressed,
    /// Full length public key, 65 bytes.
    Full,
    /// Raw public key, 64 bytes.
    Raw,
}

下面分别介绍这个东西代表什么意思。
Compressed public key即为压缩公钥；
Full length public key即为未压缩公钥；
Raw public key即为原始公钥。
虽然上面是这么个顺序，但是介绍的话需要反过来介绍。

Raw public key原始公钥

先说Raw public key原始公钥，这其实就是最先认识的那个公钥，它用64字节即512比特表示，由于公钥点坐标的横纵坐标都是256位比特32字节，这个64字节的公钥其实就是把横纵坐标直接拼起来。

这样表示公钥的话省时省力，公钥是什么样就表示成为什么样。但是有一个用于序列化ECDSA的公钥标准，称之为Standard for Efficient Cryptography（SEC高效加密标准），那么既然他说高效了，直接原样存储公钥肯定不是最高效的，于是就有了未压缩公钥和压缩公钥。

Full length public key未压缩公钥

未压缩公钥有65个字节，比原始公钥还要多一个字节，这其实是为了区分未压缩公钥和压缩公钥，给他们分别加一个一字节的前缀。未压缩公钥的一字节前缀用16进制表示为0x04，由于是16进制表示，04代表两个16进制数，共8比特，即一字节。

Compressed public key压缩公钥

压缩公钥有33字节，和未压缩公钥一样，在压缩公约前面加了一个字节的前缀来表示是压缩后的公钥，剩下的32字节就只有公钥的x坐标，y坐标不再保留，要得到公钥的y坐标需要把x坐标代入到椭圆曲线方程中得到。
但是这里就会有一个问题，有限域椭圆曲线方程关于y=p/2对称，如果只给一个x坐标会得到两个y坐标值，且这两个y坐标值的和为p。这样就需要对具体是哪个y来标记，由于两个y坐标值的和为p，那么必定有一个y是奇数，另一个是偶数。规定一字节前缀如果为0x02则表示y为偶数，0x03表示y为奇数，这样就可以使用1字节前缀+32字节x坐标来表示压缩后的33字节公钥了。

公钥PublicKey总述

结构体PublicKey表示公钥，公钥就是一个仿射坐标点：

pub struct PublicKey(Affine);

公钥实现的函数如下图所示，相比Message而言多了很多，下文将会具体分析，这里先把细节抹掉，关注整体实现：

impl PublicKey {
    //公钥生成：
pub fn from_secret_key_with_context(seckey: &SecretKey, 
context: &ECMultGenContext,) -> PublicKey {
    ...
    }
#[cfg(any(feature = "static-context", feature = "lazy-static-context"))]
pub fn from_secret_key(seckey: &SecretKey) -> PublicKey {
       ...
    }

pub fn parse_slice(p: &[u8], format: Option<PublicKeyFormat>) -> Result<PublicKey, Error> {
...
    }

pub fn parse(p: &[u8; util::FULL_PUBLIC_KEY_SIZE]) -> Result<PublicKey, Error> {...
    }

pub fn parse_compressed(
        p: &[u8; util::COMPRESSED_PUBLIC_KEY_SIZE],
    ) -> Result<PublicKey, Error> {
        ...
    }

pub fn serialize(&self) -> [u8; util::FULL_PUBLIC_KEY_SIZE] {
    ...
    }

pub fn serialize_compressed(&self) -> [u8; util::COMPRESSED_PUBLIC_KEY_SIZE] {
...
    }

pub fn tweak_add_assign_with_context(
        &mut self,
        tweak: &SecretKey,
        context: &ECMultContext,
    ) -> Result<(), Error> {
        ...
    }
#[cfg(any(feature = "static-context", feature = "lazy-static-context"))]
pub fn tweak_add_assign(&mut self, tweak: &SecretKey) -> Result<(), Error> {
       ...
    }

pub fn tweak_mul_assign_with_context(
        &mut self,
        tweak: &SecretKey,
        context: &ECMultContext,
    ) -> Result<(), Error> {
    ...
    }
#[cfg(any(feature = "static-context", feature = "lazy-static-context"))]
pub fn tweak_mul_assign(&mut self, tweak: &SecretKey) -> Result<(), Error> {
       ...
    }

pub fn combine(keys: &[PublicKey]) -> Result<Self, Error> {
       ...
}

下面开始讲述具体的函数实现：

公钥生成函数

公钥生成过程很简单，就是根据椭圆曲线群的生成元G，与私钥进行标量乘法运算，得到的坐标点就是公钥，这里就是公钥生成函数，实现上述过程。

这个函数表示根据context上下文生成公钥，这里的context上下文其实就是ECMultGenContext，即专门计算

$a G$ 类型运算的那个impl，ecmult_gen函数应该看到比较熟悉，在libsecp256k1比特币密码算法开源库（九）的ECMultGenContext部分介绍过这个函数，就是根据传入的Jacobian类型的坐标点pj和Scalar类型的标量seckey进行标量乘法运算，得到结果点坐标。由于最后结果点坐标还是Jacobian类型，需要得到的公钥是一个仿射坐标点，需要用set_gej函数将Jacobian坐标点转化为Affine仿射坐标点。

pub fn from_secret_key_with_context(
        seckey: &SecretKey,
        context: &ECMultGenContext,
    ) -> PublicKey {
        let mut pj = Jacobian::default();
        context.ecmult_gen(&mut pj, &seckey.0);
        let mut p = Affine::default();
        p.set_gej(&pj);
        PublicKey(p)
    }

set_gej函数实现如下代码所示，实现的功能就是根据传入的Jacobian类型坐标点转化为Affine仿射坐标点，之前博客中提到过，Jacobian类型坐标点转化为Affine仿射坐标点的对应关系为：Jacobian射影坐标点

(

)

(x,y,z)

$(x, y, z)$ 对应仿射坐标中的点

(

)

(frac {x}{z^2},frac {y}{z^3})

$(\frac{x}{z ^{2}}, \frac{y}{z ^{3}})$ ，按照这个对应关系很容易看懂下面的代码，在相应位置我给出了注释。

pub fn set_gej(&mut self, a: &Jacobian) {
        self.infinity = a.infinity;
        let mut a = *a;
        a.z = a.z.inv();//对z求逆，相当于1/z
        let z2 = a.z.sqr();//对z逆求平方
        let z3 = a.z * z2;//对z逆求三次方
        a.x *= z2;//a.x即为x/z^2，即为仿射坐标横坐标点
        a.y *= z3;//a.y即为y/z^3，即为Jacobian射影坐标纵坐标点
        a.z.set_int(1);
        self.x = a.x;
        self.y = a.y;
    }

这个函数没啥好说的，就是把上面那个函数给封装了一下，直接调用上面的那个函数from_secret_key_with_context：

pub fn from_secret_key(seckey: &SecretKey) -> PublicKey {
        Self::from_secret_key_with_context(seckey, &ECMULT_GEN_CONTEXT)
    }

反序列化

这个函数运行实现的就是把一个序列化的公钥给反序列化，并加入了错误处理机制。具体的反序列化函数prase（处理未压缩公钥）和parse_compressed（处理压缩公钥）的实现在这段代码的后面给出了解释。
在本文最开始的部分介绍了原始公钥、压缩公钥和未压缩公钥，这段代码的在反序列化操作前先识别传入的公钥p是哪种类型，对原始公钥做得很绝，直接返回错误了，但是在后面又把原始公钥给转化成了未压缩公钥；对于压缩公钥和未压缩公钥都是直接反序列化为PublicKey，不报错。

pub fn parse_slice(p: &[u8], format: Option<PublicKeyFormat>) -> Result<PublicKey, Error> {
//识别公钥类型
        let format = match (p.len(), format) {
            (util::FULL_PUBLIC_KEY_SIZE, None)
            | (util::FULL_PUBLIC_KEY_SIZE, Some(PublicKeyFormat::Full)) => PublicKeyFormat::Full,
            (util::COMPRESSED_PUBLIC_KEY_SIZE, None)
            | (util::COMPRESSED_PUBLIC_KEY_SIZE, Some(PublicKeyFormat::Compressed)) => {
                PublicKeyFormat::Compressed
            }
            (util::RAW_PUBLIC_KEY_SIZE, None)
            | (util::RAW_PUBLIC_KEY_SIZE, Some(PublicKeyFormat::Raw)) => PublicKeyFormat::Raw,
            _ => return Err(Error::InvalidInputLength),//原始公钥返回异常
        };
//反序列化公钥
        match format {
        //未压缩公钥使用反序列化函数prase反序列化
            PublicKeyFormat::Full => {
                let mut a = [0; util::FULL_PUBLIC_KEY_SIZE];
                a.copy_from_slice(p);
                Self::parse(&a)
            }
            //将原始公钥转化为未压缩公钥并反序列化
            PublicKeyFormat::Raw => {
                use util::TAG_PUBKEY_FULL;

                let mut a = [0; util::FULL_PUBLIC_KEY_SIZE];
                a[0] = TAG_PUBKEY_FULL;
                a[1..].copy_from_slice(p);
                Self::parse(&a)
            }
             //压缩公钥使用反序列化函数parse_compressed反序列化
            PublicKeyFormat::Compressed => {
                let mut a = [0; util::COMPRESSED_PUBLIC_KEY_SIZE];
                a.copy_from_slice(p);
                Self::parse_compressed(&a)
            }
        }
    }

下面是专门针对未压缩公钥的反序列化函数prase实现过程，主要思路就是调用set_b32函数分别将x和y进行反序列化处理，其中在代码段
if !x.set_b32(array_ref!(p, 1, 32))
中，(p, 1, 32)表示在数组p中截取下标index为1-32的部分，其中1表示index下标，32表示偏移量offset，共32个数组元素，刚好表示x坐标；同样地在代码段
if !y.set_b32(array_ref!(p, 33, 32))
中，33表示index下标，32表示偏移量offset，即截取数组下标33-64的数组元素，刚好表示y坐标。

截取好对应部分后分别传入set_b32函数进行反序列化处理得到反序列化的x坐标和y坐标。

最后创建一个Affine类型的变量，调用set_xy函数接收x坐标和y坐标，实现将序列化数组p转化为了一个Affine类型的变量elem，实现了反序列化的过程。

pub fn parse(p: &[u8; util::FULL_PUBLIC_KEY_SIZE]) -> Result<PublicKey, Error> {
        use util::{TAG_PUBKEY_FULL, TAG_PUBKEY_HYBRID_EVEN, TAG_PUBKEY_HYBRID_ODD};

        if !(p[0] == TAG_PUBKEY_FULL
            || p[0] == TAG_PUBKEY_HYBRID_EVEN
            || p[0] == TAG_PUBKEY_HYBRID_ODD)
        {
            return Err(Error::InvalidPublicKey);
        }
        let mut x = Field::default();
        let mut y = Field::default();
        //反序列化处理x坐标和y坐标
        if !x.set_b32(array_ref!(p, 1, 32)) {
            return Err(Error::InvalidPublicKey);
        }
        //将处理结束后的坐标转换为Affine类型的变量
        if !y.set_b32(array_ref!(p, 33, 32)) {
            return Err(Error::InvalidPublicKey);
        }
        let mut elem = Affine::default();
        elem.set_xy(&x, &y);
        if (p[0] == TAG_PUBKEY_HYBRID_EVEN || p[0] == TAG_PUBKEY_HYBRID_ODD)
            && (y.is_odd() != (p[0] == TAG_PUBKEY_HYBRID_ODD))
        {
            return Err(Error::InvalidPublicKey);
        }
        if elem.is_infinity() {
            return Err(Error::InvalidPublicKey);
        }
        if elem.is_valid_var() {
            Ok(PublicKey(elem))
        } else {
            Err(Error::InvalidPublicKey)
        }
    }

set_xy函数实现如下所示，即创建一个与给定x和y坐标对应的椭圆曲线群元素，且坐标为仿射坐标。

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

下面是专门针对压缩公钥的反序列化函数parse_compressed实现过程，压缩的公钥没有y坐标只有x坐标，因此只对x坐标使用set_b32函数处理即可，得到反序列化的x坐标。

最后创建一个Affine类型的变量，调用set_xo_var函数接收x坐标，实现将序列化数组p转化为了一个Affine类型的变量elem，实现了反序列化的过程。

pub fn parse_compressed(
        p: &[u8; util::COMPRESSED_PUBLIC_KEY_SIZE],
    ) -> Result<PublicKey, Error> {
        use util::{TAG_PUBKEY_EVEN, TAG_PUBKEY_ODD};

        if !(p[0] == TAG_PUBKEY_EVEN || p[0] == TAG_PUBKEY_ODD) {
            return Err(Error::InvalidPublicKey);
        }
        let mut x = Field::default();
        //反序列化处理x坐标
        if !x.set_b32(array_ref!(p, 1, 32)) {
            return Err(Error::InvalidPublicKey);
        }
        //将处理结束后的坐标转换为Affine类型的变量
        let mut elem = Affine::default();
        elem.set_xo_var(&x, p[0] == TAG_PUBKEY_ODD);
        if elem.is_infinity() {
            return Err(Error::InvalidPublicKey);
        }
        if elem.is_valid_var() {
            Ok(PublicKey(elem))
        } else {
            Err(Error::InvalidPublicKey)
        }
    }

在传入set_xo_var时就设置p[0] == TAG_PUBKEY_ODD，即公钥y坐标为奇数。
在set_xo_var函数中实现设置一个仿射坐标表示的群元素，这个群元素的x坐标与给定x坐标一致。

在set_xo_var函数中调用函数set_xquad，实现群元素坐标x和y的设置，设置之外还是为了验证给定的x坐标是不是有效，即将x代入到椭圆曲线方程中能否找到一个对应的y点。

    pub fn set_xo_var(&mut self, x: &Field, odd: bool) -> bool {
        if !self.set_xquad(x) {
            return false;
        }
        //将在set_xquad中得到的y坐标正常化
        self.y.normalize_var();
        //判断在set_xquad中得到的y坐标是否为奇数，
        //如果不是奇数使用neg函数得到对应奇数坐标
        if self.y.is_odd() != odd {
            self.y = self.y.neg(1);
        }
        true
    }

函数set_xquad实现设置一个仿射坐标表示的群元素，这个群元素的x坐标等于给定x坐标，并求出这个x坐标对应椭圆曲线方程的纵坐标y。如果存在一个给定x坐标的椭圆曲线群下的坐标，则返回值为真。

    pub fn set_xquad(&mut self, x: &Field) -> bool {
        self.x = *x;
        let x2 = x.sqr();
        let x3 = *x * x2;//求x的三次方
        self.infinity = false;
        let mut c = Field::default();
        c.set_int(CURVE_B);
        c += x3;//求 x的三次方 加 b
        let (v, ret) = c.sqrt();//求平方剩余，即求一个数v，v的平方模p结果为c
        self.y = v;//求得的v即为纵坐标y
        ret
    }

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

rust 算法

二维码

10采用区块链智能合约管理智能城市房地产交易的概念框架

< <上一篇

本地链使用web3js发送签名交易

下一篇>>

搜索内容