本节主要讲了Schnorr基于离散对数签名和Schnorr 群生成&用法。有了schnorr签名的基础,就可以继续学习相关的门限签名,零知识证明等对基础要求较高的内容。
上一节讲了PKCS与RSA相关填充标准,可以看到实用的RSA实现在原理算法基础上,增加了很多额外的处理,包括安全和计算方面。 之前有一文章介绍了Schnorr与椭圆曲线结合的签名, 本节继续讲Schnorr基于离散对数签名。
q为选取有限群的阶,随机选择一个秘密私钥x(0<x<q), 得到公钥$y = y^x mod\ q$
假定待签名消息是M,
随机选择随机数k, k < q
令$r = g^k mod\ p,e=H(r|M)$
计算s = k - xe mod q
则签名结果为(s,e)
收到上述签名结果后,验证者执行如下过程:
令$r_v = g^sy^e mod\ p$
计算$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原始论文是这么写的。
这种做法本质上是一样的。但是这种做法需要逆元运算,且不太符合多数人实现习惯,所以更多具体实现和博客文章选择和本文描述的过程一致, 大家可以自己体会。
上述计算过程要求在一个有限群上进行,这个群的阶是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
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!