DSA
上面所描述的ElGamal签名算法在实际中并不常用，更常用的是其变体DSA。
基本原理
密钥生成
选择一个合适的哈希函数，目前一般选择SHA1，当前也可以选择强度更高的哈希函数H。
选择密钥的长度L和N，这两个值决定了签名的安全程度。在最初的DSS（Digital Signature Standard ）中建议L必须为64的倍数，并且$512 \leq L \leq 1024$ ，当然，也可以更大。N必须大小必须不大于哈希函数H输出的长度。FIPS 186-3给出了一些建议的L和N的取值例子：(1024, 160)， (2048, 224)， (2048, 256)，以及 (3,072, 256)。
选择N比特的素数q。
选择L比特的素数p，使得p-1是q的倍数。
选择满足$g^k \equiv 1 \bmod p$ 的最小正整数k为q的g，即在模p的背景下，ord(g)=q的g。即g在模p的意义下，其指数次幂可以生成具有q个元素的子群。这里，我们可以通过计算$g=h^{\frac{p-1}{q}} \bmod p$ 来得到g，其中$1< h < p-1$ 。
选择私钥x，$0<x<q$ ，计算$y \equiv g^x \bmod p$ 。
公钥为(p,q,g,y)，私钥为(x)。
签名
签名步骤如下
选择随机整数数k作为临时密钥，$0<k<q$ 。
计算$r\equiv (g^k \bmod p) \bmod q$
计算$s\equiv (H(m)+xr)k^{-1} \bmod q$
签名结果为(r,s)。需要注意的是，这里与Elgamal很重要的不同是这里使用了哈希函数对消息进行了哈希处理。
验证
验证过程如下
计算辅助值，$w=s^{-1} \bmod q$
计算辅助值，$u_1=H(m)w \bmod q$
计算辅助值，$u_2=rw \bmod q$
计算$v=(g^{u_1}y^{u_2} \bmod p) \bmod q$
如果v与r相等，则校验成功。
正确性推导
首先，g 满足 $g^k \equiv 1 \bmod p$ 的最小正整数k为q。所以 $g^q \equiv 1 \bmod p$ 。所以 $g^x \equiv g^{x \bmod q} \bmod p$ 。进而
$v=(g^{u_1}y^{u_2} \bmod p) \bmod q=g^{u_1}g^{xu_2} \equiv g^{H(m)w}g^{xrw} \equiv g^{H(m)w+xrw}$
又$s\equiv (H(m)+xr)k^{-1} \bmod q$ 且$w=s^{-1} \bmod q$ 所以
$k \equiv s^{-1}(H(m)+xr) \equiv H(m)w+xrw \bmod q$
所以$v \equiv g^k$ 。正确性得证。
安全性
已知k
原理
如果知道了随机密钥k，那么我们就可以根据$s\equiv (H(m)+xr)k^{-1} \bmod q$ 计算私钥d，几乎攻破了DSA。
这里一般情况下，消息的hash值都会给出。
$x \equiv r^{-1}(ks-H(m)) \bmod q$
k共享
原理
如果在两次签名的过程中共享了k，我们就可以进行攻击。
假设签名的消息为m1,m2，显然，两者的r的值一样，此外
$s_1\equiv (H(m_1)+xr)k^{-1} \bmod q$
$s_2\equiv (H(m_2)+xr)k^{-1} \bmod q$
这里我们除了x和k不知道剩下的均知道，那么
$s_1k \equiv H(m_1)+xr$
$s_2k \equiv H(m_2)+xr$
两式相减
$k(s_1-s_2) \equiv H(m_1)-H(m_2) \bmod q$
此时 即可解出k，进一步我们可以解出x。
例子
这里我们以湖湘杯的DSA为例，但是不能直接去做，，，因为发现在验证message4的时候签名不通过。源题目我没有了，。，，这里我以Jarvis OJ中经过修改的题目DSA为例
可以看出四则消息全部校验通过。这里之所以会联想到共享k是因为题目中提示了PS3的破解曾用到这个方法，从网上搜索可知该攻击。
下面，我们看一下签名后的值，这里使用的命令如下
其中，获取的第一个值是r，第二个值是s。可以看到第4个packet和第3个packet共享了k，因为他们的r一致。
这里我们可以使用openssl看下公钥
下面，我们直接利用上面的原理编写程序即可，程序如下
我发现pip安装的pycrypto竟然没有DSA的importKey函数。。。只好从github上下载安装了pycrypto。。。
结果如下
Last updated