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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理