数字签名算法之ECDSA

椭圆曲线密码学，简称ECC。是一种建立公开加密的算法，也就是非对称加密。和RSA类似。被公认在给定密钥长度下最安全的加密算法。应用范围很广，主要的三个技术TLS、PGP、SSH都在使用它，特别是以BTC为代表的数字货币。

基于ECC的签名算法就是ECDSA。

椭圆曲线

一般情况下，椭圆曲线可用下列方程式来表示，其中a,b,c,d为系数。

E:y2=ax3+ bx2+cx+d

简化这个问题

一条椭圆曲线就是一组被 定义的且满足 的点集。

不同的椭圆曲线对应不同的形状（b=1，a从2到-3）

可以发现，椭圆曲线始终是关于x轴对称的。

再定义一个无穷远的点，记为0，那么包含无穷远点的整个椭圆曲线点集为：

群（Group）

群是离散数学数学中定义的一个二元运算。如：“加法”用符号“+”表示，但此处的加法可以是任意的一个二元运算。

群G的定义需要满足以下四个条件：

  1. 封闭性（closure）：如果a和b被包含于群G，那么a+b 也一定是群G的元素。
  2. 结合律(associativity)。
  3. 存在一个单位元（identity element）0，使得 a+0 = 0+a = a;[单位元：与任意元素运算不改变其值的元素]
  4. 每个数都存在一个相反数(inverse)。

如果我们再加上第五个条件：

  1. 交换律(commutativity): a+b = b+a.

这个群就叫做交换群，也叫做阿贝尔群(abelian group)。

我们费劲证明这个集合是一个群的最终目的就是为了使用群的定理。

如：一个群中有且只有一个单位元，对应的相反数也是独一无二的。

椭圆曲线上的群论

为了简化问题，我们记

其中p为质数，a,b为小于p的非负整数，且满足：

我们可以在椭圆曲线上定义一个群：

  1. 群中的元素就是椭圆曲线上的点。

  2. 单位元就是无穷处的点0.

  3. 加法规则定义如下：

    （代数理解）取一条直线上的三点（这条直线和椭圆曲线相交的三点），P, Q, R（皆非零），他们的总和等于0，P+Q+R=0。

    （几何理解）以曲线上两点P,Q连线而成的直线交曲线于第三点C，C关于X轴对称的点即为R。即 P + Q = R

    img

  4. 二倍运算（当P，Q为同一点时）：

    取P点的切线交曲线于点C，C关于X轴对称的点即为R。即 2P = R

  5. 相反数-P，是P关于X轴对称的点。(有限域中的负元)

    （X，-Y mod P） = (X , P - Y)

ECC曲线加密核心原理

从加法运算推导到二倍运算以后，我们可以拓展到K倍运算。即从P的坐标得到KP的坐标

不同于RSA加密的本质是，RSA基于的是大整数难分解问题，即已知一个大整数，难以将其分解为两个质数相乘。

ECC加密的本质是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。

即在有限域FP定义公式：Q = KG，已知大数K和曲线上基点G的情况下，很容易求出Q。但是在已知点G，Q的情况下很难求出K。

这就是经典的离散对数问题。

ECC算法正是利用该特点进行加密，点Q为公钥，大数K为私钥，点G为基点。

椭圆曲线加密算法原理

  1. 选定一条椭圆曲线 Ep(a,b) 并取椭圆曲线上一点，作为基点G。

  2. 选择一个大数K作为私钥，并生成公钥 Q=KG。

  3. 将 Ep(a,b) 和点Q、P传给用户。

  4. 用户接到信息后 ，将待传输的明文编码到Ep(a,b)上的一点M，并产生一个随机整数r。

  5. 公钥加密（密文C是一个点对）：C={rG, M+rQ}

  6. 私钥解密（M + rQ - k(rG) ，解密结果就是点M），公式如下：

  7. 对点M进行解码就可以得到明文。

椭圆曲线签名算法（ECDSA）

有了椭圆曲线加密的基础，可以很自然的推导出ECDSA。

依然假设私钥、公钥分别为K，Q。其中 Q = KG，G为基点。

  1. 选定一条椭圆曲线 Ep(a,b) 并取椭圆曲线上一点，作为基点G。
  2. 选择一个大数K作为私钥，并生成公钥 Q=KG。
  3. 选择随机数r，计算点rG(x, y)。
  4. 根据随机数r、消息M的哈希h、私钥K，对M进行签名 s = (h + Kx)/r。
  5. 将消息M、和签名{rG, s}发给接收方。（椭圆信息 Ep(a,b) 和点Q、P也发）
  6. 用户接到信息后，根据消息M计算哈希h。
  7. 使用发送方公钥K计算：hG/s + xQ/s，并与rG比较，如相等即验签成功。

GO使用ECDSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/rand"
	"fmt"
	"log"
)

func main() {
	privateKey, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
	if err != nil {
		log.Fatalln(err)
	}

	// 公钥是存在在私钥中的，从私钥中读取公钥
	publicKey := &privateKey.PublicKey
	message := []byte("hello,ecdsa签名")

	// 进入签名操作
	r, s, _ := ecdsa.Sign(rand.Reader, privateKey, message)
	// 进入验证
	flag := ecdsa.Verify(publicKey, message, r, s)
	if flag {
		fmt.Println("数据未被修改")
	} else {
		fmt.Println("数据被修改")
	}
	flag = ecdsa.Verify(publicKey, []byte("hello"), r, s)
	if flag {
		fmt.Println("数据未被修改")
	} else {
		fmt.Println("数据被修改")
	}
}

参考：

https://zhuanlan.zhihu.com/p/36326221

https://segmentfault.com/a/1190000019172260