简介
DSA(Digital Signature Algorithm)是Schnorr和ElGamal签名算法的变种,被美国NIST作为DSS(DigitalSignature Standard) 数字签名的标准。
DSA是基于整数有限域离散对数难题的。
DSA是一种更高级的验证方式,它是一种公开密钥算法,不能用来加密数据,一般用于数字签名和认证。
发送者使用自己的私钥对文件或消息进行签名,接受者收到消息后使用发送者的公钥来验证签名的真实性,包括数据的完整性以及数据发送者的身份。如果数据和签名不匹配则认为验证失败!数字签名的作用就是校验数据在传输过程中不被修改。
签名过程
密钥生成
选择合适的哈希函数(一般为SHA)H
选择密钥长度L与N
- L最好为64的倍数, $512≤L≤1024$
- $N≤len(H)$
选择N比特位的素数q
选择L比特位的素数p且$q | p-1$
选择模p下阶为q的最小正整数g($g^q≡1 \mod p$)
此时,$g≡h^{\frac{p-1}{q}} \mod p, h∈(1,p−1) $
选择私钥$x∈(0,q) $,计算$y≡g^x \mod p$
公钥: (p, q, g, y)
私钥: x
签名
- 选$k≡(0,q)作为临时密钥$
- $r≡(g^k \mod p) \mod q$
- $s≡(H(m)+xr)k^{-1} \mod q$
- 签名结果: (r, s)
验证
- 记$\omega ≡ s^{-1} \mod q$
- 记$u_1≡H(m)*\omega \mod q$
- 记$u_2≡r*\omega \mod q$
- $v≡(g^{u_1}*y^{u_2} \mod p) \mod q$
- 若v=r,验证成功
正确性证明
我推了几次,不够完备,这里参考CTF-Wiki
同样的,由于对签名认知过少,这里也试着摸索下它的合理性,以及陷门何在。
由DSA签名过程知,验证需要用到$\omega$也即$s^{-1} \mod q$,而$s$是含有私钥$x$的
简言之,验证需要正确的私钥$x$,$x$泄漏,身份就被窃取了
而不同于ElGamal签名,它(DSA数字签名)算了明文的哈希值
这就使得验证完身份正确后,还可以得到明文的哈希值,与所给出的比对,就实现了证明是这个人要传输这些信息
相关攻击
已知 k
原理
首先,明确k是什么。
k是临时私钥,也是不可泄漏的!
否则,有:$x \equiv r^{-1}(ks-H(m)) \bmod q$
(H(m)一般会给出)
得到了私钥x,验证可过。
总结
值得一提,按我的理解,实际场景就算得到了私钥,但就本次签名而言,H(m)已经固定
所以其意义在于,已知k可以通过本次签名得到x,方便后续签名过程伪造,但对于本次签名内容却不可篡改
K复用(共享k)
原理
在DSA签名时,一次生成的参数L、N、p、q、x、g、y都是可以重复使用的
但临时私钥k不可以重复使用
若k重复使用,有:
$s_1\equiv (H(m_1)+xr)k^{-1} \bmod q$
$s_2\equiv (H(m_2)+xr)k^{-1} \bmod q$
已知参数:
- s1、H(m1)、r、q
- s2、H(m2)、r、q
未知参数:
- $x$
- $k^{-1}$
则:
$s_1k \equiv H(m_1)+xr \mod q$
$s_2k \equiv H(m_2)+xr \mod q$
上下两式相减,得:
$k(s_1-s_2) \equiv H(m_1)-H(m_2) \bmod q$
总结
k复用(r相同)能将k求出,退化为k已知的问题
于是可求出私钥x,进而通过验证