随笔-149  评论-223  文章-30  trackbacks-0
背景
 
由于实际使用中RSA公钥通常很短,而私钥和模位长度一样,导致解密(或签名)时大数指数模运算比较慢,故可使用中国剩余定理约简模数和解密指数,以加快运算

描述

 x为密文,n为模,p和q为大素数且满足n=pq,d为私钥,设
   x≡ x mod p,x≡ x mod q                      (1)
   d≡ d mod (p-1),dq ≡ d mod (q-1)          (2)
   yp = xp^dp mod p,yq = xq^dmod q        (3)
 则有 xd ≡ ((qcp)yp + (pcq)yq) mod n,其中 c≡ q-1 mod p , cq ≡ p-1 mod q

证明
 由(1)式可得
   xpd ≡ xd mod p,xqd ≡ xd mod q                (4)
 根据中国剩余定理可得
   xd ≡ ((qcp)xp+ (pcq)xqd) mod n,下面只要证明yp和xpd一样同余于xd模p,yq和xqd一样同余于xd模q
 根据(2)式及费小马定理可得
   xp^d≡ xpd mod p,xq^d≡ xqd mod q, 再结合(4)得
   xp^d≡ xd mod p,xq^d≡ xd mod q,故
   yp = xd mod p,yq = xd mod q 证毕
posted on 2021-10-01 17:32 春秋十二月 阅读(1285) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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