Digital Signature 数字签名
什么是数字签名
考虑这样的一个场景:
Alice 想给 Bob 发送一个信息。
- Alice把信息放在一个信封里
- Alice用自己的印章封住了信封
所有人都可以通过检查封印知道:
这封信来自于Alice,因为印章是Alice的。
同时可以通过查看封印是否完好得知信息有无被修改。
Digital Signature就是想实现同样的功能。
更贴近现实生活的一个例子是支票。
公钥和私钥对
在编码学中我们用公钥(Public Key)和私钥(Private Key)对来实现数字签名协议
- Priate key 用于签名(发送者才有, 不可以公开)
- Public key 用于验证(所有人都可以验证,是公开的)
- 每一个文件都有独特的签名(签名是跟着文件才生效的,就像日常中你不能把一个地方的签名减下来贴到另一个地方)
数字签名的工作流程
- Create Keys
- Alice生成一定大小的私钥
- Alice用私钥生成公钥
- Create Signature
- Alice用私钥给meesage签名
- Alice将签名, message和Public Key发送给Bob
- Verify
- Bob用签名, message和public key验证Alice一定拥有对应的私钥。
- 因此Alice是一个友善的发出者
[图片来源: https://www.cryptocompare.com/wallets/guides/how-do-digital-signatures-in-bitcoin-work/]
ECDSA (Elliptic Curve Digital Signature Algorithm 椭圆曲线算法)
- What ECDSA does is to provide a method for computing a public key from the private key in a non-invertible fashion (也就是说,我们可以通过ECDSA算法计算出一个私钥对应的公钥,但是不能通过已知公钥算出对应的私钥-要找也只能Brute Force)
- Private key is a 256 bit long number chosen by Alice
Elliptic curves
An elliptic curve is represented algebraically as an equation of the form:
$$y^2 = x^3 + ax + b$$
For a = 0 and b = 7 (the version used by bitcoin), it looks like this:
$$y^2 = x^3 + 7$$
Elliptic curves有一些有用的特性
- 曲线上两个非切点的非垂直于坐标轴的连线必定与曲线相交于另一点
- 曲线上一点的不与坐标轴垂直切线一定与曲线相较于另一点。
由此两个特性,可以定义如下运算。
Point addition, Point doubling and Scalar multiplication
1.Point addition
$$P+Q=R$$
P和Q连线与曲线交点关于x轴的对称点
2.Point doubling
$$P+P=R$$
P的切线与曲线交点关于x轴的对称点
3.Scalar multiplication
计算$$R=7P$$并不需要7次加法。
$$R=7P=P+2(P+2P)$$
总共其实只需要4次运算。
Finite fields (有限域)
曲线是无限的,但是我们期望所得到的点是落在有限的区域里,最简单的方法就是模运算。
如图则是将x, y mod 67的结果。这样所有点都落在66*66的空间里(还是关于某个与原x轴平行的线对称的)
那么上述的加法操作要怎么进行呢?
采取的方法是保证两点连线的斜率不发生变化,水平和上下移动直到碰到一个点。
再取该点的对称点。如下图所示
签名步骤
- Base point G= 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
- public key = private key * base point
- Alice hashes the message. The hash is z.
签名过程
- Choose some random (or deterministic) integer k between 1 and n - 1. (n is called order - FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141)
- Calculate the point (x, y) = k * G, using ECDSA multiplication.
- Find r = x mod n. If r = 0, return to step 1.
- Find s = (z + r * d) / k mod n. If s = 0, return to step 1.
- The signature is the pair (r, s)
验证
Q是public key, 其他字符和上面代表的一样
- Verify that r and s are between 1 and n - 1.
- Calculate w = s-1 mod n
- Calculate u = z * w mod n
- Calculate v = r * w mod n
- Calculate the point (x, y) = uG + vQ
- Verify that r = x mod n. The signature is invalid if it is not.
####参考资料