19 Aug 2019

DSA从入门到入土

DSA从入门到入土

  • DSA

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

  • 密钥生成

    1. 选择一个合适的哈希函数H

    2. 选择密钥长度L和N,这两个值决定了签名的安全程度

      DSS建议L必须为64的倍数,且$512 \leq L \leq 1024$ ,N 必须不大于哈希函数输出的长度

    3. 选择 N 比特的素数 q。

    4. 选择 L 比特的素数 p,使得 p-1 是 q 的倍数。

    5. 选择满足$g^r \equiv 1 \bmod p$ 的最小正整数r为q的g,即g模p的阶为q

      计算$g=h^{\frac{p-1}{q}} \bmod p$ 来得到g,其中$1< h < p-1$

    6. 选择私钥x,$0<x<q$ ,计算$y \equiv g^x \bmod p$

    公钥为(p,q,g,y),私钥为(x)

  • 签名

    1. 选择随机整数数k作为临时密钥,$0<k<q$ 。
    2. 计算$r\equiv (g^k \bmod p) \bmod q$
    3. 计算$s\equiv (H(m)+xr)k^{-1} \bmod q$

    签名结果为(r,s)

  • 验证

    1. 计算辅助值,$w=s^{-1} \bmod q$
    2. 计算辅助值,$u_1=H(m)w \bmod q$
    3. 计算辅助值,$u_2=rw \bmod q$
    4. 计算$v=(g^{u_1}y^{u_2} \bmod p) \bmod q$
    5. 如果v与r相等,则校验成功。
  • 证明

  • python实现

    def inverse(u, v):
        u3, v3 = long(u), long(v)
        u1, v1 = 1L, 0L
        while v3 > 0:
            q=divmod(u3, v3)[0]
            u1, v1 = v1, u1 - v1*q
            u3, v3 = v3, u3 - v3*q
        while u1<0:
            u1 = u1 + v
        return u1
      
    def sign(m, k):
        inv_k = invert(k, q)
        r = pow(g, k, p) % q 
        s = (inv_k * (m + x * r)) % q
        return (r, s)
      
    def verify(r, s):
        if not (0 < r < q) or not (0 < s < q):
            return False
        w = inverse(s, q)
        u1 = (m*w) % q
        u2 = (r*w) % q
        v = (pow(g, u1, p) * pow(y, u2, p) % p) % q
        return v == r
      
    
  • 安全性

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

    素数P必须足够大,且p-1至少包含一个大素数因子以抵抗Pohlig &Hellman算法的攻击。M一般都应采用信息的HASH值。DSA加密算法的安全性主要依赖于p和g,若选取不当则签名容易伪造,应保证g对于p-1的大素数因子不可约。


Tags:
0 comments



本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议CC BY-NC-ND 4.0)进行许可。

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0).