算法描述
【公開密鑰】
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
春秋十二月 閱讀(5363)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm