DSA(Digital Signature Algorithm)是Schnorr和ElGamal签名算法的变种,被美国NIST作为DSS(DigitalSignature Standard)
选择一个合适的哈希函数H
选择密钥长度L和N,这两个值决定了签名的安全程度
DSS建议L必须为64的倍数,且$512 \leq L \leq 1024$ ,N 必须不大于哈希函数输出的长度
选择 N 比特的素数 q。
选择 L 比特的素数 p,使得 p-1 是 q 的倍数。
选择满足$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$
选择私钥x,$0<x<q$ ,计算$y \equiv g^x \bmod p$
公钥为(p,q,g,y),私钥为(x)
签名结果为(r,s)
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的大素数因子不可约。
本作品采用知识共享署名-非商业性使用-禁止演绎 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).