随笔-156  评论-223  文章-30  trackbacks-0
算法描述    
   随机选择两个大的素数 p、q ,且p ≠ q,计算n = pq、r = (p-1)(q-1),依欧拉定理,r即为与n互质的素数个数;选择一个小于r的整数e(即加密指数),求得e关于模r的逆元d(即解密指数),则{n,e}为公钥、{n,d}为私钥;根据模的逆元性质有ed ≡ 1 (mod r);设m为明文,则加密运算为m^e ≡ c (mod n), c即为密文;则解密过程 c^d ≡ m (mod n)。
   证明会用到费马小定理,即 若y为素数且x不为y的倍数, 则 x^(y-1) ≡ 1 (mod y)(费马小定理的证明需先证明欧拉定理,此处略)。符号≡表示同余,^表示,|表示整除,*表示相乘。

算法证明
 第一种证明途径   
   因 ed ≡ 1 (mod (p-1)(q-1)),令 ed = k(p-1)(q-1) + 1,其中 k 是整数
   则 c^d = (m^e)^d = m^(ed) = m^(k(p-1)(q-1)+1)
   1.若m不是p的倍数,也不是q的倍数
      则 m^(p-1) ≡ 1 (mod p) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod p)
      m^(q-1) ≡ 1 (mod q) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod q)
      故 p、q 均能整除 m^(k(p-1)(q-1)) - 1
         => pq | m^(k(p-1)(q-1)) - 1
      即 m^(k(p-1)(q-1)) ≡ 1 (mod pq)   
         => m^(k(p-1)(q-1)+1) ≡ m (mod n)   

   2.若m是p的倍数,但不是q的倍数
      则 m^(q-1) ≡ 1 (mod q) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod q)
         => m^(k(p-1)(q-1)+1) ≡ m (mod q)
      因 p | m
         => m^(k(p-1)(q-1)+1) ≡ 0 (mod p)
         => m^(k(p-1)(q-1)+1) ≡ m (mod p)
      故 m^(k(p-1)(q-1)+1) ≡ m (mod pq) 
      即 m^(k(p-1)(q-1)+1) ≡ m (mod n)

   3.若m是q的倍数,但不是p的倍数,证明同上

   4.若m同为p和q的倍数时
      则 pq | m
         => m^(k(p-1)(q-1)+1) ≡ 0 (mod pq)
         => m^(k(p-1)(q-1)+1) ≡ m (mod pq)
      即 m^(k(p-1)(q-1)+1) ≡ m (mod n)

 第二种证明途径
   先证明m^ed ≡ m (mod p)恒成立
   1.若p为m的因子,则p | m^ed - m显然成立,即m^ed ≡ m (mod p)
   2.若p不为m的因子,令ed = k(p-1)(q-1) + 1,则 m^(ed-1) - 1 = m^(k(p-1)(q-1)) - 1
       m^(p-1) ≡ 1 (mod p) (费马小定理)
        => m^(k(p-1)) ≡ 1 (mod p)
        => m^(k(p-1)(q-1)) ≡ 1 (mod p)
        => m^(ed-1) ≡ 1 (mod p)
        => m^ed ≡ m (mod p)
   同理可证m^ed ≡ m (mod q)
   故m^ed ≡ m (mod pq),即m^ed ≡ m (mod n)
   又因 c^d = m^e^d = m^(ed)
   故 c^d ≡ m (mod n),证毕
   
总结
 第二种比第一种简单直观,以上证明途径对RSA私钥签名与验签同样适合。
posted on 2016-11-18 17:05 春秋十二月 阅读(2621) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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