密码学基础--ECDSA算法入门
目录
1.ECDSA签名长度的疑惑
2.ECDSA原理
2.1 生成签名
2.2 验签过程
2.3 签名编码问题
3.小结
1.ECDSA签名长度的疑惑
我们来看看ECDSA签名长什么样子，使用MuscleV02自动生成密钥对，并对message"0x11223344”进行签名，结果如下：
仔细看，这个签名的长度竟然来到了568bit，可是我们用的是SECP256R1，这个长度既不是256，也不是256的倍数，这里面到底有什么玄机？
今天我们就来了解一下：1）ECDSA原理；2）签名值的编码格式。
2.ECDSA原理
首先回顾下签名原理：
- Bob 使用 Hash 函数对"Hello Alice"计算出摘要；
- Bob 为了证明消息是自己发的，用自己的私钥对摘要进行加密，也即签名；并把消息和签名同时发送给 Alice；
- Alice 拿到数据后，首先对"Hello Alice”使用同样 Hash 函数进行摘要计算，得到消息原始 Hash值；使用 Bob 对外公开的公钥，对签名进行解密得到待校验的 Hash 值；
- 将上述 Hash 进行比对，如果值一致，则证明是 Bob 发送的消息。
- 如果用其他的密钥进行签名会出现什么情况呢？
- 如果 Bob 使用自己的公钥签名，那只有自己私钥才能验，Alice 不知道是谁发的；
- 如果 Bob 用 Alice 的公钥签名，虽然只有 Alice 能验证，但是由于只要是获得了 Alice 公钥的人都可以签名，不能证明是 Bob 发的。
ECDSA(Elliptic Curve Digital Signature Algorithm)就是基于椭圆曲线密码学的一种签名机制。
以SECP256R1(对应NIST P-256曲线)为例，它满足方程形如：
该方程我们用函数 T = (p,a,b,G,n,h)进行表示，其中 p 为素数，a、b 为椭圆曲线参数，G为基点，n为G的阶(即多少个点)，h是辅助计算因子。
根据SEC2标准定义，该曲线推荐参数如下：
在实际代码中，我们也可以看到上述参数均作为常数：
有了上述基础，我们接着看算法细节。
2.1 生成签名
ECDSA的签名总体流程一句话概括：对消息做Hash计算得到H，对H进行计算得到整数对(r，s)，（r，s）根据不同编码格式输出S，作为最终签名。
我们主要讨论对H如何进行计算，具体如下：
- 首先我们先基于曲线生成对应的公私钥对，如下：
原理也很简单，就是在上述推荐参数n中随机选择一个数d作为私钥(即上图P)，然后利用基点G计算出公钥Q = d * G(xG,yG) ，故密钥对为（Q，dU）。
- 然后继续在随机选择一个整数k(k<n)，生成一个临时密钥对(Q1, k)，Qt坐标为（x1，y1）；
- 令 r = x1 mod n，注意这个n不是模数，而是上述提到的固定参数n(阶)，
- 判断r是否为0，如果为0，就需要重新再次生成，
从mbedtls的示例中也可以看出这个判断过程；
- 从上述消息摘要H中派生出整数e，来源于H的二进制表现形式下高log2n个bit，代码如下：
- 然后套用公式
最终得到了签名(r,s)，函数实现如下：
2.2 验签过程
接收者受到明文M、签名(r，s)，
- 计算M哈希值H，并根据生成过程派生出整数e；
- 根据公式u1 = e / s mod n, u2 = r / s mod n，分别计算出u1，u2；
- 使用发送方公钥Q，计算R = (xR,yR)= u1*G+u2*Q，如果R不是该曲线上的点，则认为签名无效；
- 计算v = xR mod ;
- 判断v 是否等于r，如果相等，则签名有效。
2.3 签名编码问题
从上面签名生成过程，其实我们可以发现，不管是r还是s，它的长度都不会超过模数p，因此P-256签名(r，s)的长度最大理应为256*2 = 512bit.
但实际我们从第一节知道，该签名有568bit，总共多了56bit（7个字节）。
直觉告诉我这必然与编码格式有关。
我印象里就只记得ASN.1，所以就去翻了翻了文档，最终在DER(Distinguished Encoding Rules)里找到了答案。
DER叫做可辨别编码规则，采用TLV三元组格式进行编码，具体如下：
Tag表示真实数据结构，Length表示具体字节长度，Value则是真实数据；
它的构造可以如下图：
而我们开头看到的0x30， 刚好对应Sequence：
根据这个规则，我把刚才的签名做了如下分解：
为什么r会有前导字节00，这是因为(r，s)都是整数，r第一个字节99最高位为1，为了避免混淆，故需要添加前导字节。
为了验证正确性，我继续做了几次签名试验，分别如下：
可以初步判断，这个python库 ECDSA签名采用ASN,1 DER编码规则。
3.小结
这篇文章把ECDSA的原理讲述清楚，原理简单，难点主要是在这些计算公式的理解上；同时我们把针对数字签名的DER编码格式理了一遍。
就酱，中秋快乐！