区块链中的数学-Schnorr 离散对数签名及素数阶群构造(Schnorr 群)

  • blocksight
  • 更新于 2020-07-21 17:45
  • 阅读 5942

本节主要讲了Schnorr基于离散对数签名和Schnorr 群生成&用法。有了schnorr签名的基础,就可以继续学习相关的门限签名,零知识证明等对基础要求较高的内容。

写在前面

上一节讲了PKCS与RSA相关填充标准,可以看到实用的RSA实现在原理算法基础上,增加了很多额外的处理,包括安全和计算方面。 之前有一文章介绍了Schnorr与椭圆曲线结合的签名, 本节继续讲Schnorr基于离散对数签名。

签名及验证

q为选取有限群的阶,随机选择一个秘密私钥x(0<x<q), 得到公钥$y = y^x mod\ q$

签名过程

假定待签名消息是M,

  1. 随机选择随机数k, k < q

  2. 令$r = g^k mod\ p,e=H(r|M)$

  3. 计算s = k - xe mod q

    则签名结果为(s,e)

签名验证

收到上述签名结果后,验证者执行如下过程:

  1. 令$r_v = g^sy^e mod\ p$

  2. 计算$e_v=H(r_v|M)$

如果$e_v == e$则验证通过,否则失败。

为何这样验证是正确的?下面推导下:

$r_v=g^sy^e=g^sy^{xe}=g^{s+xe}=g^k=r$

所以:

$e_v=H(r_v|M)=H(r|M)=e$

得证。

到这里签名和验证都说完了,这里要说明一下,有的实现在签名过程中步骤3 写成 s = k + xe mod q 【是“+”不是“-”】,这种写法的前提是生成公钥时候$y =g^{-x} mod\ q$,注意指数是-x, Schnorr原始论文是这么写的。

这种做法本质上是一样的。但是这种做法需要逆元运算,且不太符合多数人实现习惯,所以更多具体实现和博客文章选择和本文描述的过程一致, 大家可以自己体会。

Schnorr群

上述计算过程要求在一个有限群上进行,这个群的阶是q, q 如何得来?这就是Schnorr群的算法。

Schnorr群跟Schnorr签名一样,是 Claus P. Schnorr首先提出的。构造Schnorr群首先选择两个大的素数,p,q 满足:

p = q * r + 1

r是大于1的正整数,显然q整除 p - 1 , 然后在[1,p]之前找到一个h, 使得:

$h^r\not= 1\ mod\ p$

那么,$g = h^r\not= 1\ mod\ p $是q阶子群的生成元。

为什么以g为生成元的群会有q的阶呢?看下式:

$g^q \equiv h^{rq } \equiv h^{p-1} \equiv 1\ mod\ p$

这里利用了费马小定理。这表明了g的阶要么是q,要么是q的一个因数,但同时因为$h^r\not= 1\ mod\ p$,并且q是素数不存在因数,因此g的阶必为q。

这样生成的群称为Schnorr群。Schnorr群有什么特点?

q素数阶,该群没有非平凡子群,可以避免小子群攻击(Small subgroup confinement attack)

同时,素数阶群必为循环群,这个性质很重要,尤其是在密码学中,我们总是引入素数阶的群,这个性质保证了引入的群具有循环群的一切特征,包括交换性、具有生成元等。

Diffie-Hellman密钥交换算法一文中,我们只讲了运算过程。其实不完整,还有一部分就是协议约定的有限群,即前置条件。 密钥交换算法所依赖的群的阶需要是一个素数,原因刚才说过,即素数阶群的特点。而通常的余数群,其中p为大于2的素数,那么群阶ord = p-1 则必是偶数。因此,直接用作为Diffie-Hellman的群是不安全的。

为解决这个问题,其中的思路是在p内找到一个Schnorr Group的子群,该子群满足存在素数q。用我们前面的方法,就可以找到Schnorr生成元g。

小结

本节主要讲了Schnorr基于离散对数签名和Schnorr 群生成&用法。有了schnorr签名的基础,就可以继续学习相关的门限签名,零知识证明等对基础要求较高的内容。 本文提到到小子群攻击,以后有机会再说吧。

之前介绍了椭圆曲线加密算法的一些基本概念和运算,后续讲一些具体的应用相关的内容。

好了,下一篇回到椭圆曲线,继续讲下椭圆曲线的公钥恢复相关内容。

欢迎关注公众号:blocksight

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

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。