0%

DSA

简介

DSA(Digital Signature Algorithm)是Schnorr和ElGamal签名算法的变种,被美国NIST作为DSS(DigitalSignature Standard) 数字签名的标准。

DSA是基于整数有限域离散对数难题的。

DSA是一种更高级的验证方式,它是一种公开密钥算法,不能用来加密数据,一般用于数字签名和认证。

发送者使用自己的私钥对文件或消息进行签名,接受者收到消息后使用发送者的公钥来验证签名的真实性,包括数据的完整性以及数据发送者的身份。如果数据和签名不匹配则认为验证失败!数字签名的作用就是校验数据在传输过程中不被修改。

签名过程

密钥生成

  1. 选择合适的哈希函数(一般为SHA)H

  2. 选择密钥长度LN

    • L最好为64的倍数, $512≤L≤1024$
    • $N≤len(H)$
  3. 选择N比特位素数q

  4. 选择L比特位素数p且$q | p-1$

  5. 选择模p下阶为q的最小正整数g($g^q≡1 \mod p$)

    此时,$g≡h^{\frac{p-1}{q}} \mod p, h∈(1,p−1) $

  6. 选择私钥$x∈(0,q) $,计算$y≡g^x \mod p$

  7. 公钥: (p, q, g, y)

    私钥: x

签名

  1. 选$k≡(0,q)作为临时密钥$
  2. $r≡(g^k \mod p) \mod q$
  3. $s≡(H(m)+xr)k^{-1} \mod q$
  4. 签名结果: (r, s)

验证

  1. 记$\omega ≡ s^{-1} \mod q$
  2. 记$u_1≡H(m)*\omega \mod q$
  3. 记$u_2≡r*\omega \mod q$
  4. $v≡(g^{u_1}*y^{u_2} \mod p) \mod q$
  5. 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,进而通过验证

参考