算法描述
【公开密钥】
p是512到1024位的素数
q是160位长，并与p-1互素的因子
g = h^((p-1)/q) mod p，其中h<p-1且g>1
y = g^x mod p
【私有密钥】
x < q，长160位
【签名】
k为小于q的随机数，k^-1为k模q的逆元，m为消息，H为单向散列函数
r = (g^k mod p) mod q
s = (k^-1(H(m)+xr)) mod q
【验证】
w = s^-1 mod q
u1 = (H(m)w) mod q
u2 = (rw) mod q
v = ((g^u1 * y^u2) mod p) mod q
若v = r，则签名被验证
验签推导
1. 先证明两个中间结论
因(h,p)=1（p为素数且h<p，(a1,a1)是数论中的符号，记为a1与a2的最大公约数），故依费马小定理有h^(p-1)=1 mod p，则对任意整数n，有
g^(nq) mod p = (h^((p-1)/q))^(nq) mod p
= h^(n(p-1)) mod p
= (h^(p-1) mod p)^n mod p
= (1^n) mod p = 1 (1)
对任意整数t、n，可表示为t=nq+z，其中z>0，则有
g^t mod p = g^(nq+z) mod p
= (g^(nq) mod p * (g^z mod p)) mod p
= g^z mod p
= g^(t mod q) mod p (2)
2. 再假设签名{r,s}和消息m均没被修改，令H(m)=h，开始推导v
v = ((g^u1 * y^u2) mod p) mod q
= (g^(hw mod q) * ((g^x mod p)^(rw mod q) mod p)) mod q
= ((g^(hw mod q) mod p * ((g^x mod p)^(rw mod q) mod p)) mod p) mod q
= ((g^(hw mod q) mod p * (g^(x * (rw mod q)) mod p)) mod p) mod q
= ((g^(hw) mod p * ((g^(rw mod q) mod p)^x mod p)) mod p) mod q
= ((g^(hw) mod p * ((g^(rw) mod p)^x mod p)) mod p) mod q
= ((g^(hw) mod p * (g^(rwx) mod p)) mod p) mod q
= (g^(hw+rwx) mod p) mod q
= (g^((h+rx)w) mod p) mod q (3)
又因w = s^-1 mod q
故(sw) mod q = 1
=>(((k^-1(h+xr)) mod q)w) mod q = 1
=>((k^-1(h+xr))w) mod q = 1
=>(h+xr)w = k mod q (4)
将(4)式代入(3)式中得
v = (g^(k mod q) mod p) mod q
= (g^k mod p) mod q
= r
3. 最后由(4)式知，若h、r和s任一个有变化（s变化导致w变化），则v ≠ r
posted on 2016-11-24 19:39
春秋十二月 阅读(5293)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm