DSA相关知识整理

最近基本都在忙开发，很少玩CTF，湖湘杯就看了dsa这题，考虑到我之前对DSA不太熟，所以这里对知识点做个整理：

DSA可以看作是ELGamel的变种，安全性也是基于离散对数难题，且其计算速度比RSA快。

这里对DSA的相关知识点做一个整理：

密钥生成方式：

1.确定密钥长度L和N，其中L是64的倍数，且满足$512\leq L \leq 1024$，当然，随着目前对安全性要求的提高，也有标准允许更长的L，其中N的长度必须小于等于签名所使用的哈希算法的输出位长度，常见的L，N取值(1024,160),(2048,224),(2048,256)和(3072,256)

2. 取一个长度为N的质数q。

3. 取一个长度为L的质数p，且满足p-1是q的倍数。

4.取一个数$g\neq 1$满足$ g = h^\frac{p-1}{q}\;(mod\;p)$,其中$1< h<p-1$。

5.私钥x，取随机值x满足$0< x < q$。取$y = g^x \;(mod\;p)$

于是，公钥为(y,p,q,g)。

签名过程如下，假设待签名内容为m，哈希算法为H(x)：

对每个待签名的内容取随机值k满足$1<k< q$。

计算：$r = (g^k\;mod\;p)\;mod\;q$

计算：$s = k^{-1}(H(m)+xr)\;mod\;q$

如果计算结果中s = 0，则重新选择k计算

最后将(r,s)元组作为签名。

签名校验过程如下：

如果签名不满足$0< r < q$或者$0< s < q$，则该签名不合法。如果满足这两个条件：

计算：$w = s^{-1}\;mod\;q$

计算：$u_1 = H(m)\cdot w\;mod\;q$

计算：$u_2= r \cdot w\;mod\;q$

计算：$v =(g^{u_1}y^{u_2}\;mod\;p)\;mod\;q$

如果最终v与r相等，则校验成功，否则失败。

算法证明：

首先，我们在生成g时需要满足$ g = h^\frac{p-1}{q}\;(mod \;p)$，那么$g^q =  h^{p-1}\;mod\;p$，根据费马小定理，因为p是质数，所以$h^{p-1} \equiv 1\;(mod\; p)$，因此有$g^q \equiv  h^{p-1}\equiv 1 \;(mod\;p)$。

由于g>0且q是质数，所以$g^{x}\;mod\; p = g^{x\;mod\;q}\;mod\;p$

然后再看校验的过程：

$s = k^{-1}(H(m)+xr)\;mod\;q$，变化可得：

$k \equiv  s^{-1}(H(m)+xr) $

$\equiv H(m)w+xrw\; (mod\; q)$

那么

$g^k \equiv g^{H(m)w}g^{xrw}$

$\equiv g^{H(m)w}y^{rw} $

$\equiv g^{u_1}y^{u_2}\; (mod\; p)$

备注：这一步利用了：

$g^{H(m)w}\;mod\; p $

$= g^{H(m)w\;(mod\;q)}\;\;(mod\;p)$

$ =g^{u_1} \;(mod\;p)$

和

$g^{xrw}\;(mod\; p) $

$= g^{xrw\;(mod\;q)}\;mod\;p$

$=g^{xu_2} \;(mod\;p)$

$=y^{u_2}\; (mod\; p) $

所以最后有：

$r = (g^k\;mod\;p)\;mod\;q $

$= (g^{u_1}y^{u_2}\;mod\;p)\;mod\;q$

$ =v $

证毕。

最后讨论一下安全性，DSA的签名过程中，k是随机而且保密的，如果知道k，可以根据r和s计算出私钥x：

$x = r^{-1}(s\cdot k-H(m))\;(mod\;q)$

同理，如果两个消息使用了相同的k，或者两个k之间有联系，比如使用的是k和k+1，这样的情况下即使k保密，也是危险的，因为这时候我们有：

$s_1 = k^{-1}(H(m_{1})+xr)\;(mod\; q)$

$s_2 = k^{-1}(H(m_{2})+xr)\;(mod\; q)$

相同的k会导致相同的r，以上两个方程恰好2个未知数，只需解出同余方程组即可知道k和x。

最后回到本题，本题给出的message3和message4的签名中$r$是相同的：

也就是说，这两个签名使用了相同的k，可以通过上面所述的方法求解出私钥。但是，本题有个坑，那就是message4被人为修改了，最后签名校验是过不了的：

还真不知道是什么脑洞，后来一直觉得是不是作者文件改错了，实在没办法只能爆破文件内容，不过这样没啥意思了。思路应该就是这个。

最后，如果你想自己想弄个题目尝试一下的话，我自己修订了道题，把坑给去掉了，精华留下给大家学习。可以在我的Jarvis OJ – Challenges – Crypto 分类下找到DSA这题，大家可以自行做个尝试。