python实现私钥，公钥，签名，验签原理

I have yet to meet a person who understands blockchain but don't believe in it. ——by CZ

本文将简单，直白，明了的介绍椭圆曲线公钥、私钥、签名，验证签名的原理，并使用python实现相关代码。
相关源码PYchain/wallet.py

椭圆曲线介绍

椭圆曲线一般方程形如

比特币椭圆曲线中采用的参数如下，16进制表示，a=0，b= 7。

_a = 0x0000000000000000000000000000000000000000000000000000000000000000
_b = 0x0000000000000000000000000000000000000000000000000000000000000007

私钥与公钥

G为比特币椭圆曲线上固定已知的一点，坐标如下：

_Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
_Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G_point = (_Gx, _Gy)

k就是私钥(sk)，私钥就是一个数字，公钥就是k乘G后得到的点的坐标。

# 随机生成sk = random.randint(1, _r)或自己设置
sk = 123456

下图中，G点为已知固定的一点，若私钥k=8，则8G点的坐标为相对应的公钥K，如果私钥k=3，那么相对应的K计算方式为2G点+G点后的坐标，注意，此处加法和乘法是定义在椭圆曲线上的运算，与我们熟知的加法乘法完全不同，下边有详细说明。

image

为了避免公钥取小数，两边对_p取模(mod是求模运算)，这是真正的比特币椭圆曲线方程。（求模之后椭圆曲线转变为离散的点图，为方便讨论，后续仍采用曲线图形方式）：

_r是一个和_p有关的参数，私钥不能大于_r

_p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
_r = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

定义模除法

定义椭圆曲线加法和乘法前，首先介绍分数取模，模运算中，要将模除法转化为模乘形式。
如求 1/17 (mod 2668)，问题转化为（1*（17mod2668的逆元））mod 2668 ，求得逆元为157 ，结果为157

定义求逆元函数Md_inv，例子中输入a等于上式17，n等于2668（比特币中为_p）输出为逆元157（算法来源于扩展欧几里得方法）

def Mod_inv(a, n=_p):
    lm, hm = 1, 0
    low, high = a % n, n
    while low > 1:
        ratio = high // low
        nm, new = hm - lm * ratio, high - low * ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % n

定义加法

P+Q等于P、Q连线与椭圆曲线相交点关于X轴对称的点R，R点坐标可由P，Q两点坐标求出，如下：

定义函数E_add，输入p为P点坐标，横坐标P[0]，纵坐标P[1]，q类似，输出为R点坐标(rx为横坐标、ry纵坐标)。（求lam用到了模除法）

def E_add(p, q):
    lam = ((q[1] - p[1]) * Mod_inv(q[0] - p[0], _p)) % _p
    rx = (lam * lam - p[0] - q[0]) % _p
    ry = (lam * (p[0] - rx) - p[1]) % _p
    return rx, ry

定义乘法

2P等于过P点做椭圆曲线切线交椭圆的点关于X轴对称的点R，其中

定义E_double函数，输入为P点横坐标，纵坐标，输出为R横坐标，纵坐标

def E_double(p):
    lam = ((3 * p[0] * p[0] + _a) * Mod_inv((2 * p[1]), _p)) % _p
    rx = (lam * lam - 2 * p[0]) % _p
    ry = (lam * (p[0] - rx) - p[1]) % _p
    return rx, ry

公钥计算

有了加法和乘法，我们就可以来计算公钥了。
如计算8G，通过乘法迭代计算2G，4G，8G最终得到结果
9G等于8G+G。现有一种更快捷算法(来源)
如计算9G，我们首先将9转化为二进制是'1001'，跳过第一位，从第二位开始，先直接对g倍乘，当该位为1时再进行一次加G，经过循环，最后得到9G。
定义Emultiply函数，输入为G点，和私钥(sk)，输出为公钥(kG点的坐标)

def Emultiply(point, secret_key):
    if secret_key == 0 or secret_key >= _r:
        raise Exception("生成私钥不符合要求")
    secret_key = str(bin(secret_key))[2:]
    g = point
    for i in range(1, len(secret_key)):
        g = E_double(g)
        if secret_key[i] == '1':
            g = E_add(g, point)
    return g

测试

已知椭圆曲线一点x坐标可由曲线方程推出y，只需多两位来标记y的奇偶，偶加‘02’，奇加‘03’，奇或偶前缀加x坐标称为压缩公钥。

下图第一个为私钥，第二个是压缩公钥(来源)

运行函数结果，sa和上述压缩公钥完全一样。

hashlib.sha256()

在介绍签名之前，介绍下hashlib.sha256()函数。
hashlib.sha256()，将任意长度的字符串哈希成为64位16进制字符串(256位二进制字符串)，不同字符串的hash值完全不同，当前技术无法通过破解hash值来得到原字符串内容，这是比特币安全的基石。

签名和验签

你用私钥k对一条消息进行运算产生一个签名，我根据你的公钥K和签名以及同样的消息进行计算，可以确认你是否拥有公钥对应的私钥。这个过程关键之处在于你不需要给我传输你的私钥，我就可以确定你拥有公钥相对应的私钥。

理论过程如下：

私钥签名：

Alice产生零时私钥r(RandNum)，计算对应点rG的横坐标为xrand。
Alice根据零时私钥r(RandNum)、消息h、私钥k，计算s = (h + kxrand)/r。（同时r = (h + kxrand)/s）
Alice将消息h、和签名{xrand, s}，公钥K发给接收方。

公钥验证签名：

Bob收到消息h、以及签名{xrand, s},Alice的公钥K。
计算（h/s)G + (xrand/s)K ，其中 K = kG
推导结果如下：（h/s)G + (xrand/s)K = （h/s)G + (kxrand /s)G = [(h+ k xrand)/s]*G = rG
通过判断计算结果rG的横坐标和收到的xrand是否相等，相等则该消息h经过该公钥K对应的私钥k加密,签名有效。

算法实现

h为信息，可以是任意长度的字符串

h = 'dhsjdhsjdh'

定义函数sign

sign 函数输入为消息h为字符串，以及私钥k(privkey)，输出为签名，形式为[r, s]
字符串h转化为数字msg参与计算。
注意运算中当有对点使用加法或乘法时，需采用椭圆曲线定义的法则，否则就使用普通的运算法则。所有计算均需对_r求模操作。

def sign(h, privkey):
    msg = int(hashlib.sha256(json.dumps(h).encode()).hexdigest(), 16)
    RandNum = random.randint(1, _r)
    xRand, yRand = Emultiply(G_point, RandNum)
    r = xRand % _r
    s = ((msg + r * privkey) * (Mod_inv(RandNum, _r))) % _r
    return [r, s]

定义函数verify_sign

函数输入为消息h，公钥K(pubkey)，以及签名rs，输出为True或False ，判断签名是否正确，公钥拥有者是否有对应的私钥。

def verify_sign(h, pubkey, rs):
    msg = int(hashlib.sha256(json.dumps(h).encode()).hexdigest(), 16)
    w = Mod_inv(rs[1], _r)
    xu1, yu1 = Emultiply(G_point, (msg * w) % _r)
    xu2, yu2 = Emultiply(pubkey, (rs[0] * w) % _r)
    x, y = E_add((xu1, yu1), (xu2, yu2))
    return x == rs[0]

签名和验证测试

成功验证签名，当修改签名后，验签为False，不通过。

意义

比特币实质就是一个账本，上边记录了大量的交易信息。你拥有1个比特币，意味着账本上已经存在这样一条交易消息“aaa给我的公钥转了1比特币”，且这条消息的签名是正确的，那么现在你就能够用你自己的私钥k提交一条交易信息‘我的公钥给bbb公钥转账1比特币’,并对其签名，当这条消息被账本记录了，你的1比特币就花出去了，而所有的比特币最初来源都是挖矿所得，挖矿那条系统信息是'给xxx矿工的公钥转50比特币’，这种交易不需要签名。

参考资料

https://www.youtube.com/watch?v=iB3HcPgm_FI
https://www.youtube.com/watch?v=U2bw_N6kQL8
https://blog.csdn.net/gao131360144/article/details/79978516
https://www.jianshu.com/p/eece4117cb63

欢迎转载分享,请注明出处。