V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 1800 天前的主题，其中的信息可能已经有所发展或是发生改变。

上一节谈了《 Bitcoin 公私钥是如何生成的》,并简单聊了下椭圆加密算法的标量运算，但是很多计算机实现密码学过程中的算法细节都没有谈，今天我们来谈一谈，并且用 js 的新能力 BigInt 来从零实现 ecdsa-secp256k1。

0x01 我们要用椭圆加密算法干什么？

可能很多人只知道 Bitcoin 钱包的核心是椭圆加密算法，但是椭圆加密算法能干什么却不是很清楚。

举个栗子，小明给小红开了一张一百万的支票，小红拿着支票去银行兑换，银行要验证支票是否真伪，首先要看支票是不是由该银行的发行的，第二要看支票的签名是否是本人，确定后才能给予了小红一百万。

在数字世界又该如何实现呢？

首先小明通过自己的身份去银行申请到了支票
- 这就像私钥可以通过算法生成公钥。
其次小明在支票上签名生成一个有效的支票
- 这就像利用签名算法生成了一个有效签名数据。
银行要验证支票是不是由该银行的发行和该签名是否是本人
- 这就像利用验证算法通过公钥和签名数据验证签名是否有效

而这些利用椭圆加密算法就能做到。

0x02 如何生成私钥又如何产生公钥

注意：下文提到的 p,a,b,G,N 都是常量，你可以简单的认为是某个数字

私钥可以从 1 到 N 中选择一个值作为私钥(k)，而公钥(K)的算法是 K = kG,难道是 k 乘 G ？当然不是。这里的乘是标量乘法。

那么何为`标量乘法`呢？

简单来说即是 kG 只能由另外两个点叠加而成。比如 k 等于 14，我们只知道常量 G,那么要叠加到 14G 是不是要这样(如下):

G+G = 2G
2G+G = 3G
3G+G = 4G
...
13G+G=14G

那有意思了，那如果 k 很大要怎么办呢？其实很简单，我们只要对折运算就好了。先把 14 转换成二进制即是 1110，那是不是相当于是(如下):

1110:
=>1*(2^3)G+1*(2^2)G+1*(2^1)G+0*(2^0)G
=> 1*8G + 1*4G + 1*2G + 0*G 
那么二进制只有 4 位就只要先计算 4-1 次,然后再相加不就好了
G+G = 2G
2G+2G = 4G
4G+4G = 8G
然后
2G+4G = 6G
6G+8G = 14G

对比挨个 G 相加，14 要加 13 次，而下面这种只要相加 5 次，是不是就少了很多。当然越大的数，少的次数就越多。比如 10000 要相加 9999 次，而用优化后的方法 10000 只要相加 17 次就能得到结果。这个优化是极度恐怖的。

说完标量乘法我们来看看具体 G 是如何相加的

首先 G 相加更具推导公司分两种情况，我们用武功秘籍的方法来相称吧，以下（其中 x1,y1,x2,y2,x3,y3 是坐标变量）：

相同的点相加第一式: λ≡(3x1^2+ a)/2y1(mod p)
相同的点相加第二式: x3 ≡ λ^2 − 2x1 (mod p), y3≡ λ(x1 − x3) − y1 (mod p)

不同的点相加第一式: λ≡ （ y2 − y1 ）/（ x2 − x1 ）(mod p)
不同的点相加第二式: x3 ≡ λ^2 − x1 − x2 (mod p), y3 ≡ λ(x1 − x3) − y1 (mod p)

之前说 G 是一个数字常量，那么为什么又和坐标产生关系了呢？因为 G 点就是一个坐标数字，在密码学中常常会把一个坐标根据一定的规律转换成数字。

比如 G 点的十六进制数字值是：
0x0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
而 04 表示这是一个坐标点的数字标识。
X 坐标为前 64 位：79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Y 坐标为后 64 位：483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

按照我们之前的逻辑我们就可以将 G 点代入“相同的点相加第一式”，接着求出λ后则需要代入“相同的点相加第二式”求出 2G，但是这又有一个问题，那就是在第一式中有除法，如果有除法就可能有余，而且可能会无限位，在密码学和包括天文学涉及大数运算都偏向于整数运算，同时小数无限位会存在一个计算机数据难以表示，即使能表示也很难代入下一步进行精确运算。此时保证数学公式计算值的准确性又是一个问题。

祭出“乘法逆元”解决相除导致产生小数无限位的问题

什么是“乘法逆元”？简单来说就是将除法转换成乘法的值。举个栗子，假设 a/b 其实是可以转换成 a*(b^-1),这里面的(b^-1)就是我们要求的乘法逆元。经过推导，我们在当取模数为素数时，可以转换成整数形式。而求解乘法逆元最为常见的算法就是通过“欧几里德算法”来求取。代码如下：

// 欧几里德算法求某数的乘法逆元
function inverseMulti(x,modNum) {
    let x1= 1n,x2 = 0n,x3 = modNum;
    // 取模相加保证求解数一定为正数
    let y1 = 0n,y2=1n,y3=(x%modNum+modNum)%modNum;
    let q;
    let t1,t2,t3;
    while(true){
        if(y3==0n)throw new Error('multiplicative inverse modulo is no answer!');
        if(y3==1n)return y2;
        q = x3/y3;
        t1=x1-q*y1;t2=x2-q*y2;t3=x3-q*y3;
        x1=y1;x2=y2;x3=y3;
        y1=t1;y2=t2;y3=t3;
    }
}

在完成乘法逆元的求解后，我们就可以根据公式很好的完成相同点相加和不同点相加，再通过我之前提到的对折运算来快数获取公钥结果。所以从上面可以知道公钥就是点的叠加，所以公钥的本质也就是一个点。

0x03 如何进行签名和验证

通过 0x02 节，我们知道了如何生成私钥和公钥，假设你通过私钥(d)生成了公钥(Q),那么根据椭圆加密算法的特性，通过私钥和另一对秘钥(k(私钥),R(公钥)进行运算后可以生成一个签名，再通过我们的公钥和和另一对公钥可以验证信息的签名是否正确。

根据推导我们先随机生成一对秘钥 k，R，再对 R 点的 x 坐标进行取模，如果为 0，继续取模。再通过 s = k^-1 (e + rd) mod n,其中 e 是签名信息的数字表示，比如签名信息(M)是"This a String"这样的字符串，那么 e 可以是 sha256(M)得到数字摘要。其中 d 是你的私钥值。n 是一个常量，是私钥的最大取值上限。具体实现如下：

function sign(n,pointG,p,a,d,mNum) {
    let k,R;
    let r = 0n;
    while(r==0n) {
        // 随机生成私钥
        k = getPrivteKeyNumByRand(n);
        // 根据私钥计算公钥的点
        R = getPointByNum(k,pointG,p,a);
        // 此方法即是(R.x%n+n)%n
        r = postiveMod(R.x,n);
    }
    let e = mNum;
    let s = postiveMod(((e+(r*d))*inverseMulti(k,n)),n);
    if(s==0n) {
        return sign(n,pointG,p,a,d,M,encoding);
    }
    return {r,s};
}

根据椭圆加密算法特性，我们可以推导出，当我们计算出 R = (es^-1 mod n)G + (rs^-1 mod n)Q 即是计算出签名时的随机的那个公钥值，所以我们只要通过 v = R.x mod n 计算出 v 的值，再判断 r 是否等于 v，即可判断签名是否有效。其中 G 是常量点，Q 为你的公钥。具体实现如下：

function verify(n,pointG,p,a,pointQ,S,mNum) {
    let {r,s} = S;
    if(!(r>0n && r<n && s>0n && s<n)){return false;}
    let e = mNum;
    let w = inverseMulti(s,n);
    let u1 = postiveMod((e*w),n);
    let u2 = postiveMod((r*w),n);
    let u1Point = getPointByNum(u1,pointG,p,a);
    let u2Point = getPointByNum(u2,pointQ,p,a);
    let pointR;
    if(u1Point.x==u2Point.x && u1Point.y==u2Point.y) {
        // 如果为相同点则进行叠加运算
        pointR = addSamePoint(u1Point.x,u1Point.y,p,a);
    } else {
        // 如果为不相同点则进行相加运算
        pointR = addDiffPoint(u1Point.x,u1Point.y,u2Point.x,u2Point.y,p);
    }
    if(pointR.x==0n && pointR.y==0n) {return false;}
    let v = postiveMod(pointR.x,n);
    if(v==r) {
        return true;
    }
    return false;
}