DSA相关知识整理

  • 2016-12-18
  • 1,588
  • 4
  • 1

最近基本都在忙开发,很少玩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这题,大家可以自行做个尝试。

 

评论

  • Mark回复

    你好,请问一下RSA那道题Coppersmith你试过能解出来吗

    • Jarvis回复

      是Wiener Attack,不是coppersmith

  • Assassin回复

    请问这个题目和跑脚本的环境有关系嘛?为什么我在windows下跑怎么都不对呢?必须要用Ubuntu嘛?

    • Jarvis回复

      没关系的,这题我怀疑是题目有问题。

发表评论

*

浙ICP备16016405号-2
浙公网安备 33010602007544号