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

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

写在前面

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

签名过程

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

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-05-02 14:10
  • 阅读 ( 156 )
  • 学分 ( 0 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

53 篇文章, 954 学分