算法描述
【公開密鑰】
p是512到1024位的素?cái)?shù)
q是160位長(zhǎng)，并與p-1互素的因子
g = h^((p-1)/q) mod p，其中h<p-1且g>1
y = g^x mod p
【私有密鑰】
x < q，長(zhǎng)160位
【簽名】
k為小于q的隨機(jī)數(shù)，k^-1為k模q的逆元，m為消息，H為單向散列函數(shù)
r = (g^k mod p) mod q
s = (k^-1(H(m)+xr)) mod q
【驗(yàn)證】
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，則簽名被驗(yàn)證
驗(yàn)簽推導(dǎo)
1. 先證明兩個(gè)中間結(jié)論
因(h,p)=1（p為素?cái)?shù)且h<p，(a1,a1)是數(shù)論中的符號(hào)，記為a1與a2的最大公約數(shù)），故依費(fèi)馬小定理有h^(p-1)=1 mod p，則對(duì)任意整數(shù)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)
對(duì)任意整數(shù)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. 再假設(shè)簽名{r,s}和消息m均沒被修改，令H(m)=h，開始推導(dǎo)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任一個(gè)有變化（s變化導(dǎo)致w變化），則v ≠ r
posted on 2016-11-24 19:39
春秋十二月 閱讀(5369)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Algorithm