算法描述
【公开密钥】
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
春秋十二月 阅读(5310)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm