写在前面
上一节讲了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原始论文是这么写的。
这种做法本质上是一样的。但是这种做法需要逆元运算，且不太符合多数人实现习惯，所以更多具体实现和博客文章选择和本文描述的过程一致， 大家可以自己体会。
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
