区块链中的数学 – 椭圆曲线进行签名和验证过程

区块链技术 3 4 月 22, 2024 0 区块链315

本节继续介绍离散域上椭圆曲线进行签名和验证过程，并加以实例说明。

## 写在前面上一节我们介绍了[离散域上的椭圆曲线加密和解密过程](https://learnblockchain.cn/article/1550)，本节继续介绍离散域上椭圆曲线进行签名和验证过程，并加以实例说明。 ## 签名过程首先做如下符号约定：发起签名的用户的密钥对: （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 验证该签名为有效。正如上一节所说一样，实用的椭圆曲线算法选择是非常大的整数作为各个参数，但原理是一样的。下一节讲[迪菲赫尔曼密钥交换过程](https://learnblockchain.cn/article/1554)。欢迎关注公众号：blocksight

写在前面

上一节我们介绍了离散域上的椭圆曲线加密和解密过程，本节继续介绍离散域上椭圆曲线进行签名和验证过程，并加以实例说明。

签名过程

首先做如下符号约定：发起签名的用户的密钥对: （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

区块链技术网。