数字签名与DSA算法
数字签名流程
签名过程:将待签名的数据用散列函数加密得到散列值h,得到的散列值h用签名者的私钥加密,得到签名者的签名。将之附加到签名的数据上即可。
签名验证:将数据签名的数据分开,将数据部分用加密时用的散列函数加密,将签名用签名者的公钥解密,若两者相等则数据为原签名者发出。
数字签名性质
1.应该要能够保证签名者发送的数据不能被他人所更改,被更改后的数据和签名无法匹配。
2.签名者的签名无法被伪造,别人无法用签名者的签名发送信息。
3.任何人可以根据电子签名,鉴别是否是签名者发送的消息。
4.不可复制,一份数据上的签名无法用在另外一份数据上。
5.不可抵赖,签名者的签名可以被鉴别,能确定是签名者发送的消息,签名者不可否认自己签名。
DSA算法
DSA算法全称为Digital Signature Algorithm(电子签名算法),被美国NIST选为DSS即Digital Signature Standard(电子签名标准)算法。
密钥生成
1.选择一个合适的哈希函数H,现一般多用SHA1。
2.选择合适的密钥长度L和N,在最初的DSS中建议,L必须是64的倍数且$512\le L \le 1024$,N不能大于H函数输出的长度。
3.选择N比特的素数q
4.选择L比特的素数p,使p和q满足$q|(p-1)$
5.选择满足模p意义下阶数为q的整数g(即选取一个g,使得满足$g^k\equiv 1\ (mod\ p)$的最小正整数k为q),可以通过下式来得到g:
$$g\equiv h^{{p-1 \over q}}\ (mod\ p)$$
其中$1<h<p-1$。
(可以得到g的原因:有原式:$g\equiv h^{{p-1 \over q}}\ (mod\ p)$,两边同时q次方,可以得到:$g^q\equiv h^{p-1}\ (mod\ p)$,又因p为质数,由费马小定理知:$h^{p-1}\equiv 1\ (mod\ p)$,所以有:$g^q\equiv 1\ (mod\ p)$)
6.选择整数$x \in (0,q)$,作为私钥,并计算$y=g^x\ mod\ p$。
最终的公钥为$(p,q,g,y)$,私钥为$x$
签名
1.选择临时密钥k,满足$0<k<q$
2.计算$r\equiv (g^k\ mod\ p)\ (mod\ q)$
3.计算$s\equiv (H(m)+xr)k^{-1}\ (mod\ q)$
验签
1.计算辅助值:
$$w\equiv s^{-1}\ (mod\ q)\\u_1\equiv H(m)w\ (mod\ q)\\u2 \equiv rw\ (mod\ q)$$
2.计算v,$v=g^{u_1}y^{u_2}\ mod\ p\ (mod\ q)$
3.验证v和r是否相同,相同则为有效签名,否则为非法签名。
正确性证明
有原式:$v=g^{u_1}y^{u_2}\ mod\ p\ (mod\ q)$
将y代换得:$v=g^{u_1+xu_2}\ mod\ p\ (mod\ q)$
将$u_1$和$u_2$代换得:$v=g^{H(m)s^{-1}+xrs^{-1}}\ (mod\ q)$
又因为$s\equiv(H(m)+xr)k^{-1}\ (mod\ q)$,所以有$k=s^{-1}(H(m)+xr)\ (mod\ q)$
又因为$g^a\equiv g^{a\ mod\ q}$所以原式可以写为:$v\equiv g^k\equiv r\ (mod\ q)$
得证
了解真相得机缘!
https://bitly.net/x8888
https://dghxuiwem3it4.cloudfront.net/27gj