椭圆曲线数字签名算法（ECDSA）详解

椭圆曲线数字签名算法（ECDSA）详解

引用

CSDN

1.

https://blog.csdn.net/qq_64585761/article/details/138250846

椭圆曲线数字签名算法（ECDSA）是区块链技术中的核心密码学算法之一，主要用于数据签名和验证。本文将详细介绍ECDSA的工作原理、椭圆曲线密钥生成过程以及具体的数字签名实现方法，并附有Go语言的代码示例。

1. ECDSA算法简介

ECDSA（Elliptic Curve Digital Signature Algorithm）主要用于对数据（比如一个文件）创建数字签名，以便于在不破坏数据安全性的情况下验证其真实性。ECDSA与AES（高级加密标准）不同，它不会对数据进行加密或阻止他人访问数据，而是确保数据没有被篡改。

ECDSA的基本原理如下：首先在椭圆曲线上选择一个点作为原点G，然后生成一个随机数k作为私钥。接着使用这个随机数k和原点G通过复杂的数学运算得到椭圆曲线上的另一个点，这个点就是公钥P。当需要对一个文件进行签名时，签名由两部分组成，即r和s。通过私钥k和文件的哈希值组成一个数学方程，得到签名的s部分。取公钥P的x轴坐标作为签名的r部分。为了验证签名的正确性，需要使用公钥P和签名s、r组成一个数学方程，如果计算得到的坐标点的x轴坐标与签名中的r相等，则认为签名有效。

2. 椭圆曲线密钥生成

椭圆曲线的一般方程为y² = x³ + ax + b，画出来通常是一个椭圆曲线。如下图所示：

在椭圆曲线上，如果画一条直线与曲线产生三个交点P、Q、-R，我们称P + Q = R，其中R是-R关于x轴的对称点。需要注意的是这里的加法运算实际上是指第三个交点的x轴对称点。

如果以椭圆曲线的某一切点G做一直线，则直线与椭圆曲线的另一交点即为-2G，其关于x轴对称点即为2G点。若2G点与G点连接即可得到3G点，以此类推，即可得到kG点。

引入G点的好处是可以实现快速寻找，我们以G点做切线即可得到2G点，以2G点为切线即可得到4G点，以此类推，这样的寻找过程大大减少了寻找次数。

椭圆曲线还有一个特性：从G点开始经过k次寻找后得到kG点这一顺序计算过程比较简单，但如果我们已知G点要得到kG点是经过多少次寻找得到的则比较困难，我们只能对k一个一个尝试，当k比较大时，k的寻找过程极其困难，因此，这一过程是ECDSA算法背后安全性的基础，也被称为单向陷门函数。

比特币使用的椭圆曲线函数为y² = x³ + 7，其中a = 0, b = 7。起始节点Generator(G)的坐标为：

Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

私钥k通常选择一个较大的随机数，通过起始节点G与私钥k可以得到公钥节点P。

3. 椭圆曲线数字签名实现

假设Alice要给Bob发送消息M，Alice根据起始点G与选择的随机数（私钥）k可得到公钥P，然后用私钥k与要发送的消息M的哈希值HASH(M)相乘得到s，然后将要发送的信息M与s一同发送给Bob。Bob得到信息后，通过Alice的公钥P与Hash(M)相乘得到Y，然后将s与G相乘得到X，如果X=Y则该签名即为有效，具体过程如下：

X = Hash(M) * P = Hash(M) * k * G = s * G = Y

虽然以上过程实现了数字签名，但是存在一个漏洞：Bob得到的数据包括Alice的公钥P、s以及起始坐标G，虽然根据G与P推断不出私钥k，但是k可以通过s计算得到k = s / Hash(M)。因此，科学家又改进了签名过程：

签名过程：

1. 随机产生一个随机数e，通过计算得到eG = Q
2. 随机产生一个随机数k作为私钥，计算得到kG = P，P即为公钥，记录下P的x坐标记为r
3. 利用SHA1计算要传递信息M的哈希值z
4. 利用方程s = (z + e * r) / k计算得到s
5. 要传递的数据即为原始数据M、M的Hash值z、r与s

验证过程：
计算z * G / s + r * Q / s = P，若左右相等，则即为有效签名。

验证过程：
验证以上公式有效性：
z * G / s + r * Q / s = z * G + r * Q / s = z * G + r * e * G / s = (z + r * e) * G / s = (z + r * e) * G * k / (z + r * e) = kG = P

由于两侧求得的都为坐标，比较x轴即可。可以看到在新的签名中不存在通过s求出密钥k的漏洞，因为s = (z + e * r) / k，其中有两个未知参数e与k，所以此签名过程比上面的更加完备了。由于计算过程中所得数据要在规定的字节范围内，所以在实际代码中要进行取模运算。

4. 代码实现

以下是使用Go语言实现的ECDSA算法的签名与认证：

签名：

func (ecc *MyECC) Sign(msg []byte, secKey *big.Int) (*Signature, error) {
    // 随机产生随机数k作为私钥
    k, error := newRand()
    if error != nil {
        return nil, error
    }
    
    // 对要传递的消息msg进行hash运算得到z
    z_bytes := crypto.Keccak256(msg)
    z := new(big.Int).SetBytes(z_bytes)
    z.Mod(z, N)
    
    //计算得到私钥k的公钥P，并求出其x坐标作为r
    P := Multi(G, k)
    r := new(big.Int).Mod(P.X, N)
    
    // 计算要传递的参数s
    s := new(big.Int).Mul(r, secKey)
    s.Add(s, z)  
    s.Mul(s, Inv(k, N))  
    s.Mod(s, N)  
    // 传递s与r
    s_r := &Signature{s, r}
    return s_r, nil
}

验证：

func (ecc *MyECC) VerifySignature(msg []byte, signature *Signature, pubkey *Point) bool {
    // 获得s与r
    s, r := signature.s, signature.r
    
    // 获得传递信息msg的hash值z
    z_bytes := crypto.Keccak256(msg)
    z := new(big.Int).SetBytes(z_bytes)
    z.Mod(z, N)
    
    // 使用费马小定理求得1/s
    s_inv := Inv(s, N)
    
    // 取u = z/s
    u := new(big.Int).Mul(z, s_inv)
    u.Mod(u, N)
    
    // 取v = r/s
    v := new(big.Int).Mul(r, s_inv)
    v.Mod(v, N)
    
    // 计算u*G与v*Q
    uG := Multi(G, u)
    vQ := Multi(pubkey, v)
    // 计算u*G+v*Q得到R，并取出其x轴
    R := Add(uG, vP)
    Rx := new(big.Int).Mod(R.X, N)
    
    // 比较判断是否相同
    if Rx.Cmp(r) == 0 {
        return true
    } else {
        return false
    }
}

本文详细介绍了ECDSA算法的工作原理及其在区块链中的应用，包括椭圆曲线密钥生成、数字签名实现以及具体的代码实现过程。希望对读者理解区块链中的密码学技术有所帮助。