写在前面
上一节我们介绍了离散域上的椭圆曲线加密和解密过程，本节继续介绍离散域上椭圆曲线进行签名和验证过程，并加以实例说明。
签名过程
首先做如下符号约定：
发起签名的用户的密钥对:
（d, Q）；(d为私钥，Q为公钥)，上一节说过d是一个秘密的大整数，D是椭圆曲线上一个点。
G:生成元[基元]
待签名的信息：M；
选择椭圆曲线点群的阶：n
签名结果：Signature(M) = ( r, s)
接下来看签名过程：
1、随机选择一个整数k, 且0 < k < n
2 计算R = k * G=（$x_r,y_r$）
注：1，2步骤也可以描述为：随机生成一个密钥对(k, R), R=（$x_r,y_r$）
3、令 r = $x_r$ mod n，如果r = 0，则返回步骤1
4、计算 H = Hash(M)
5、s = $k^{-1}$ (H + rd) mod n，若s = 0, 则返回步骤1
6、输出的S =(r,s)即为签名。r是R的横坐标，有的文章说签名结果S =(R,s) 用R作为第一部分，也是可以的，本质上一样，只要在验证时候取出r.
验证过程
使用上面一样的符号规则，收到Signature(M) = ( r, s) 的签名结果， 验证过程如下：
1、计算 H = Hash(M)
2、计算 u1 = $Hs^{-1}$ mod n, u2 = $rs^{-1}$ mod n
3、计算 R = ($x_r,y_r$) = u1G + u2Q, 如果R = 零点，则验证该签名无效
4、令 v = $x_r$ mod n
5、若 v == r，则签名有效，否则, 则签名无效。
可以看到，验证过程用到了<r,s>,签名者的公钥Q，及消息M等公开信息。
为什么可以这样验证呢？下面推导一下：
R=u1G + u2Q=( $Hs^{-1}$ mod n)G + ($rs^{-1}$ mod n)*Q= ($Hs^{-1}$ mod n)G + ($rs^{-1}$ mod n) dG=$s^{-1}$G((H + rd) mod n)=$s^{-1}$Gks=kG=R
r是R的横坐标模n,到此验证结束。
实例演练
椭圆曲线方程中的参数选定为：𝑎=0, 𝑏=−4,𝑝=199,𝐺=(2,2)，该椭圆曲线方程为：
$y^2\ mod\ 199=(x^3−4)\ mod\ 199$
【注意：如果写成 −4 属于耍流氓的写法 】
此时n=217, 假设B选定的私钥为d=13，其公钥:
Q=13𝐺=(165,33)
消息假设消息M经过摘要后H=58。签名过程：
随机选择k=23,
计算R = k G=23(2,2)=(15,171)
令 r =$x_r$ mod n= 15 mod 217=15
计算：
s =$k^{-1}$ (H + rd) mod n=(58+15*13)/23 mod 217 = 11
得到签名结果：Signature(M) = ( r, s)=（15，11）
验证过程：使用上面一样的符号规则，收到Signature(M) = ( r, s)=（15，11） 的签名结果， 验证过程如下：
1、计算 H = 58 （假设内容）
2、计算 u1 = $Hs^{-1}$ mod n=58*79 mod 217=25, （1/s 模逆：79）
u2 =$rs^{-1}$ mod n = 1579 mod 217=100
3、计算 R = ($x_r,y_r $) = u1G + u2Q= 25*(2,2) + 100*(165,33)=(160,175)+ (5,11)=(15,171)
4、令 v =$x_r$ mod n = 15 mod 217 =15=r
验证该签名为有效。
正如上一节所说一样， 实用的椭圆曲线算法选择是非常大的整数作为各个参数，但原理是一样的。
下一节讲迪菲赫尔曼密钥交换过程。
欢迎关注公众号：blocksight
